Interval branch-and-bound solvers provide reliable algorithms for handling non-convex optimization problems by ensuring the feasibility and the optimality of the computed solutions, i.e. ...independently from the floating-point rounding errors. Moreover, these solvers deal with a wide variety of mathematical operators. However, these solvers are not dedicated to quadratic optimization and do not exploit nonlinear convex relaxations in their framework. We present an interval branch-andbound method that can efficiently solve quadratic optimization problems. At each node explored by the algorithm, our solver uses a quadratic convex relaxation which is as strong as a semi-definite programming relaxation, and a variable selection strategy dedicated to quadratic problems. The interval features can then propagate efficiently this information for contracting all variable domains. We also propose to make our algorithm rigorous by certifying firstly the convexity of the objective function of our relaxation, and secondly the validity of the lower bound calculated at each node. In the non-rigorous case, our experiments show significant speedups on general integer quadratic instances, and when reliability is required, our first results show that we are able to handle medium-sized instances in a reasonable running time.
Abstract
We compute the expansion of the cohomology class of the permutahedral variety in the basis of Schubert classes. The resulting structure constants $a_w$ are expressed as a sum of normalized ...mixed Eulerian numbers indexed naturally by reduced words of $w$. The description implies that the $a_w$ are positive for all permutations $w\in S_n$ of length $n-1$, thereby answering a question of Harada, Horiguchi, Masuda, and Park. We use the same expression to establish the invariance of $a_w$ under taking inverses and conjugation by the longest word and subsequently establish an intriguing cyclic sum rule for the numbers. We then move toward a deeper combinatorial understanding for the $a_w$ by exploiting in addition the relation to Postnikov’s divided symmetrization. Finally, we are able to give a combinatorial interpretation for $a_w$ when $w$ is vexillary, in terms of certain tableau descents. It is based in part on a relation between the $a_w$ and principal specializations of Schubert polynomials. Along the way, we prove results and raise questions of independent interest about the combinatorics of permutations, Schubert polynomials, and related objects. We also sketch how to extend our approach to other Lie types, highlighting an identity of Klyachko in particular.
We show that plane bipolar posets (i.e., plane bipolar orientations with no transitive edge) and transversal structures can be set in correspondence to certain (weighted) models of quadrant walks, ...via suitable specializations of a bijection due to Kenyon, Miller, Sheffield and Wilson. We then derive exact and asymptotic counting results. In particular we prove (computationally and then bijectively) that the number of plane bipolar posets on n + 2 vertices equals the number of plane permutations (i.e., avoiding the vincular pattern 2 14 3) of size n. Regarding transversal structures, for each v ≥ 0 we consider tn(v) the number of such structures with n + 4 vertices and weight v per quadrangular inner face (the case v = 0 corresponds to having only triangular inner faces). We obtain a recurrence to compute tn(v), and an asymptotic formula that for v = 0 gives tn(0) ∼ c (27/2) n n −1−π/arccos(7/8) for some c > 0, which also ensures that the associated generating function is not D-finite.
The adjacency matrix of a symplectic dual polar graph restricted to the eigenspaces of an abelian automorphism subgroup is shown to act as the adjacency matrix of a weighted subspace lattice. The ...connection between the latter and Uq(sl2) is used to find the irreducible components of the standard module of the Terwilliger algebra of symplectic dual polar graphs. The multiplicities of the isomorphic submodules are given.
Given a graph H, a graph G is called H-critical if G does not admit a homomorphism to H, but any proper subgraph of G does. Observe that K k−1-critical graphs are the standard k-(colour)-critical ...graphs. We consider questions of extremal nature previously studied for k-critical graphs and generalize them to H-critical graphs. After complete graphs, the next natural case to consider for H is that of the odd-cycles. Thus, given integers and k, ≥ k, we ask: what is the smallest order of a C 2 +1-critical graph of odd-girth at least 2k + 1? Denoting this value by η(k, C 2 +1), we show that η(k, C 2 +1) = 4k for 1 ≤ ≤ k ≤ 3 +i−3 2 (2k = i mod 3) and that η(3, C 5) = 15. The latter means that a smallest graph of odd-girth 7 not admitting a homomorphism to the 5-cycle is of order 15. Computational work shows that there are exactly eleven such graphs on 15 vertices.
In this paper we prove the following new sufficient condition for a digraph to be Hamiltonian: {\it Let $D$ be a 2-strong digraph of order $n\geq 9$. If $n-1$ vertices of $D$ have degrees at least ...$n+k$ and the remaining vertex has degree at least $n-k-4$, where $k$ is a non-negative integer, then $D$ is Hamiltonian}. This is an extension of Ghouila-Houri's theorem for 2-strong digraphs and is a generalization of an early result of the author (DAN Arm. SSR (91(2):6-8, 1990). The obtained result is best possible in the sense that for $k=0$ there is a digraph of order $n=8$ (respectively, $n=9$) with the minimum degree $n-4=4$ (respectively, with the minimum $n-5=4$) whose $n-1$ vertices have degrees at least $n-1$, but it is not Hamiltonian. We also give a new sufficient condition for a 3-strong digraph to be Hamiltonian-connected.
A note on removable edges in near-bricks Wu, Deyu; Zhang, Yipei; Wang, Xiumei
Discrete mathematics and theoretical computer science,
06/2024, Volume:
26:2, Issue:
Graph Theory
Journal Article
Peer reviewed
Open access
An edge $e$ of a matching covered graph $G$ is removable if $G-e$ is also matching covered. Carvalho, Lucchesi, and Murty showed that every brick $G$ different from $K_4$ and $\overline{C_6}$ has at ...least $\Delta-2$ removable edges, where $\Delta$ is the maximum degree of $G$. In this paper, we generalize the result to irreducible near-bricks, where a graph is irreducible if it contains no single ear of length three or more.
PDF
