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.
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.
A tight map is a map with some of its vertices marked, such that every vertex of degree 1 is marked. We give an explicit formula for the number $N_{0,n}(d_1,…,d_n)$ of planar tight maps with $n$ ...labeled faces of prescribed degrees $d_1,…,d_n$, where a marked vertex is seen as a face of degree 0. It is a quasi-polynomial in $(d_1,…,d_n)$, as shown previously by Norbury. Our derivation is bijective and based on the slice decomposition of planar maps. In the non-bipartite case, we also rely on enumeration results for two-type forests. We discuss the connection with the enumeration of non necessarily tight maps. In particular, we provide a generalization of Tutte's classical slicings formula to all non-bipartite maps.
PDF
