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 continue the enumeration of plane lattice walks with small steps avoiding the negative quadrant, initiated by the first author in 2016. We solve in detail a new case, namely the king model where ...all eight nearest neighbour steps are allowed. The associated generating function is proved to be the sum of a simple, explicit D-finite series (related to the number of walks confined to the first quadrant), and an algebraic one. This was already the case for the two models solved by the first author in 2016. The principle of the approach is also the same, but challenging theoretical and computational difficulties arise as we now handle algebraic series of larger degree.
We expect a similar algebraicity phenomenon to hold for the seven Weyl step sets, which are those for which walks confined to the first quadrant can be counted using the reflection principle. With this paper, this is now proved for three of them. For the remaining four, we predict the D-finite part of the solution, and in three of the four cases, give evidence for the algebraicity of the remaining part.
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.
Parabolic Tamari Lattices in Linear Type B Fang, Wenjie; Mühle, Henri; Novelli, Jean-Christophe
The Electronic journal of combinatorics,
03/2024, Letnik:
31, Številka:
1
Journal Article
Recenzirano
We study parabolic aligned elements associated with the type-$B$ Coxeter group and the so-called linear Coxeter element. These elements were introduced algebraically in (Mühle and Williams, 2019) for ...parabolic quotients of finite Coxeter groups and were characterized by a certain forcing condition on inversions. We focus on the type-$B$ case and give a combinatorial model for these elements in terms of pattern avoidance. Moreover, we describe an equivalence relation on parabolic quotients of the type-$B$ Coxeter group whose equivalence classes are indexed by the aligned elements. We prove that this equivalence relation extends to a congruence relation for the weak order. The resulting quotient lattice is the type-$B$ analogue of the parabolic Tamari lattice introduced for type $A$ in (Mühle and Williams, 2019).
Given a mixed hypergraph $\mathcal{F}=(V,\mathcal{A}\cup \mathcal{E})$, a non-negative integer $k$ and functions $f,g:V\rightarrow \mathbb{Z}_{\geq 0}$, a packing of $k$ spanning mixed ...hyperarborescences of $\mathcal{F}$ is called $(k,f,g)$-flexible if every $v \in V$ is the root of at least $f(v)$ and at most $g(v)$ of the mixed hyperarborescences. We give a characterization of the mixed hypergraphs admitting such packings. This generalizes results of Frank and, more recently, Gao and Yang. Our approach is based on matroid intersection, generalizing a construction of Edmonds. We also obtain an algorithm for finding a minimum weight solution to the problem mentioned above.
PDF
