Papers

For a Coxeter system $(W,S)$ of finite rank and an involutive automorphism $\ast:W\to W$ which preserves $S$, we prove that the length-generating function $\sum_{z\in\mathbf{I}_{W,\ast}}q^{\ell(z)}$ of the set of $\ast$-twisted involutions is rational. We derive recurrence relations analogous to the well-known recurrence relations expressing the growth series $W(q):=\sum_{w\in W}q^{\ell(w)}$ in terms of the growth series $W_I(q)$ of the parabolic subgroups of $W$. Our result extends to any subset $\mathcal{C}$ of $\ast$-twisted involutions that is closed under $\ast$-twisted conjugation. We use these recurrence relations to give an alternative proof of a power-series identity for twisted involutions due to Lusztig.

We develop a constructive method for solving semilinear elliptic equations $\Delta u(x)=f(x,u(x))$ on locally finite, connected infinite graphs with layered structure. Using Eidelheit's theorem, we establish coupling criteria ensuring that arbitrary initial-layer data extend to global solutions for every $f$. We apply combinatorial criteria to prove solvability on leafless infinite trees, integer lattices, the triangular and hexagonal lattices, and a Cayley graph of the discrete Heisenberg group. We further establish solvability for a broad class of Cayley graphs of semidirect products $G\cong\mathbb Z\ltimes_\theta H$. In particular, $\Delta u=e^u$ has infinitely many solutions on $\mathbb Z^2$, but none of finite energy. We also extend the method to the bi-Laplacian under two-step coupling conditions, to the $p$-Laplacian under a unique-neighbor condition, and to magnetic Laplacians.

The local clique cover number $lcc(G)$ is the minimum valency of an edge-clique cover of $G$. We prove the conjectured inequality $lcc(G)+\chi(G)\le |V(G)|+1$ for every finite simple graph. The proof gives an independent set improvement of an endpoint-cover estimate and applies the resulting construction to an induced four-vertex path. We further prove that the cover can be chosen so that every nonuniversal vertex has valency at most $|V(G)|-\chi(G)$. Consequently, every graph attaining equality has a universal vertex. The stronger statement follows by reducing a counterexample of minimum order to a prime double-critical graph and refining the induced path extension. We also show that an induced matching of size $m\ge2$ yields $lcc(G)+\chi(G)\le |V(G)|+3-m$, which improves the general bound when $m\ge3$, and determine the restrictions imposed by equality on deletion of an induced $2K_2$.

We prove that the magnitude of the tope graph of a simple oriented matroid is the specialization at $x=-1$ of the motivic zeta function of its underlying matroid. This refines the Las Vergnas–Zaslavsky theorem and defines magnitude for arbitrary matroids. For simple orientable matroids, we compute the order of the pole at $q=-1$ from chains of flats and identify it with the Varchenko–Gelfand degree of the tope parity function. Comparing pole orders, we construct a rank-six real arrangement $\mathcal A$ such that $\operatorname{Mag}(\mathcal A;-t)$ has infinitely many negative coefficients, disproving Koizumi–Liu's eventual sign alternation conjecture. We then construct a canonical multiplicative Varchenko–Gelfand filtration on the mod-$2$ magnitude cohomology of a simple oriented matroid and show that its graded dimensions recover the full motivic zeta function.

Fourier-Motzkin elimination computes an inequality description of the projection of a polyhedron onto a subset of its coordinates by eliminating one variable at a time. It is used in several areas of optimisation and computer science, and it is a standard way of obtaining the entropic constraints of a causal structure, where the marginalisation over the latent variables produces such a projection. Its limitation is the growth of the intermediate systems of inequalities, which can be doubly exponential in the number of eliminated variables even though the projection itself grows only as a single exponential. In practice the computational overload of the method therefore depends on two choices: how the redundant inequalities are removed after each step, and the order in which the variables are eliminated. We consider both. We first show, by an explicit example, that Imbert's redundancy test cannot be interleaved with redundancy removal by linear programming. We show that the two methods, however, can be combined soundly if the derivation records used by Imbert's test are re-initialised after every step at which linear programming is used. We then propose a rule for choosing the elimination order of the variables that gives a significant computational advantage, however, at the cost of increased resource usage. We demonstrate this advantage on some random polytopes, where the rule reduces the running time by factors of between 6 and 25 compared with the same elimination under a fixed order. For entropic descriptions of causal structures, with more than 250 inequalities and more than 100 variables to eliminate, our rule keeps the number of inequalities handled at each step one to two orders of magnitude lower than a fixed order.

We improve the best known lower bound on the integrality gap for weighted unit-demand multicommodity flow on trees from $1/4$ to $2/5$, improving on the long-standing bound of Chekuri, Mydlarz, and Shepherd~\cite{CMS}. We give the proof in two stages. First, a surprisingly simple packing lemma and an inductive coloring argument give an intermediate bound of $4/11$. We then refine the argument to obtain $2/5$.

We obtain tight bounds on the modularity of PPM graphs in the case of equally sized parts. Moreover, we provide a general method that can help in obtaining bounds for various other models.

In this paper we prove new bounds on the second eigenvalue of Johnson graphs. We then apply these bounds to obtain new results on the modularity of Johnson graphs and their random subgraphs, hamiltonicity of Johnson graphs and thresholds of the appearance of the hamilton cycles and giant components. Futhermore, we provide general bounds on vertex connectivity and the stability of the modularity for $(n, d, \lambda)$-graphs.

Majorization is a fundamental tool for comparing how "spread out" the entries of two vectors are. Key majorization results were obtained for the integers by Hardy, Littlewood and Pólya and for $\mathbb{Z}_p$ by Lev. In this paper, we establish a powerful majorization theorem in $\mathbb{Z}_2^n$ that is an analogue of Lev's result in $\mathbb{Z}_p$. Our proof is based on a novel use of a compression argument that optimizes certain sums of additive representation counts. Our majorization theorem has several applications in additive combinatorics. We resolve the question: given subsets $A_1,\ldots,A_k\subseteq\mathbb{Z}_2^n$ of prescribed sizes, when is the function $r_k(A_1,\ldots,A_k)$, which counts the number of additive $k$-tuples in $A_1\times\cdots\times A_k$, maximized? We establish the corresponding minimization result and a characterization of all extremizers for $r_k(A,\ldots,A)$ when $k$ is odd. When $k=3$, this quantity is the number of Schur triples in $A$; as a special case, we recover a theorem of Samotij and Sudakov on Schur triples. We also obtain a convexity inequality and use it to prove an analogue of Pollard's theorem that strengthens and extends a well-known result of Bollobás and Leader in the $\mathbb{Z}_2^n$ setting.

Kanade and Russell conjectured seventeen Rogers–Ramanujan type identities of modulus 12. Eleven of these identities involving triple sums were proved by Bringmann–Jennings-Shaffer–Mahlburg and by Rosengren. Motivated by these works and using similar methods, we settle all the six remaining conjectures including two triple sum identities labeled $I_{5a}$ and $I_{6a}$ originated from Russell's thesis and four quadruple sum identities labeled 7, 7a, 8 and 8a. Our proof of the triple sum identities combines linear recurrences, $q$-difference equations, and $q$-series summation formulas. For the quadruple sum identities, we represent the sums as contour integrals whose integrands are infinite products and evaluate them by residue calculus. The resulting residues reduce to single sum cubic basic hypergeometric series, and we are able to express them as infinite products.

Let $\Gamma=(V,E)$ be a distance-biregular graph with even diameter $d$ and girth $2d-2$. On the edge-set $E$ we define relations that form an association scheme; this is done by considering the linear span of the corresponding adjacency matrices, and, by means of intersection diagrams, we prove that this is an algebra. Furthermore, we describe all the irreducible representations of this algebra, and, by considering the multiplicities of the 2-dimensional ones, we show that there are no such distance-biregular graphs with $28\le d\le 46$ and $d\ge 52$.

Greedy algorithms efficiently approximate combinatorial optimization problems, but their guarantees weaken when feasibility couples combinatorial structure with global physical constraints. We study monotone nondecreasing supermodular minimization over the bases of a graphic greedoid under physics-induced constraints. We model physics-informed selection using a look-ahead oracle that identifies candidates extendable to a feasible basis, yielding the Conditioned Sequential Greedy Algorithm. We derive a closed-form approximation bound, which we call the price of feasibility, based on the variability of oracle-restricted candidate sets and a probabilistic correction for unobserved elements. As a case study, we show that FORWARD, an algorithm for multi-source radial network reconfiguration, instantiates this framework. Numerical results demonstrate the tightness of the bound and quantify the feasibility-optimality trade-off.

Consider an infinite edge-weighted graph satisfying an isoperimetric inequality of the type $\|\partial A\|\geq C|A|^\alpha$ for some $\alpha,C>0$, where $\|\partial A\|$ denotes the weighted size of the edge boundary of $A$. We prove that, for $C$ large enough depending on $\alpha$, if each edge is open independently with probability given by its weight, then any vertex is connected to infinity with positive probability. The result also holds under weaker isoperimetric assumptions and on finite graphs. The proof brings a new perspective on the recent proof of the Benjamini–Schramm conjecture concerning the same problem with homogeneous weights. The crucial novelty in our proof is that, rather than simply counting cutsets, we introduce a new Peierls argument which takes into account internal and external connectivity costs in addition to the cost of the blocking surface. We provide two applications for the above result. First, we show that every non-summable long-range percolation on $\mathbb{Z}^d$, $d\geq 2$, admits a percolating truncation, solving a conjecture of Sidoravicius, Surgailis and Vares and its generalization by Friedli and de Lima. Secondly, we show that there exists a universal constant $C < \infty$ such that $p_{\mathrm{c}} \leq C/\Delta$ for every transitive graph of superlinear growth and vertex degree $\Delta$, thus proving a conjecture of Easo and Hutchcroft.

For a fixed graph F, the F-degree of a vertex v in a host graph H is the number of subgraphs of H isomorphic to F that contain v, and H is F-irregular if its F-degrees are pairwise distinct. We show that every finite connected graph F on at least three vertices admits a finite connected F-irregular host. For noncomplete F, the proof builds the host from a threshold graph with one deleted edge; when the minimum degree is at least two, a small incidence gadget with distinct weighted column sums separates the remaining exceptional vertices. The construction also yields infinitely many pairwise non-isomorphic finite connected F-irregular hosts for every noncomplete F. The complete-pattern case follows from a theorem of Chartrand, Holbert, Oellermann and Swart. A Lean 4 formalization of Theorem 1.1 is described, taking the published complete-pattern theorem as its sole custom axiom.

A block design is a set family, whose members are called blocks, where every pair of points in the universe is covered by exactly one block. Erdős asked the following question: is it true that if the universe is of size $n$ and each block is of size $\Omega(\sqrt{n})$, then there exists a transversal intersecting every block in $O(1)$ points? We provide a negative answer to this question. Indeed, for arbitrarily large $n$, we construct such a block designs where every transversal intersects some block in $\Omega(\frac{\log n}{\log\log n})$ points.

We study the loopy polynomial L_G, a multivariate graph invariant arising from bizonotopal graph algebras and defined by a deletion-loopy-contraction recursion, in which the contracted edge becomes a loop. We show that L_G contains the Tutte polynomial and admits a similar spanning-forest activity expansion. It also determines Stanley's chromatic symmetric function, the degree sequence, the induced edge count profile, and the independence polynomial for loopless graphs, and the clique and matching polynomials for simple graphs. Separating the size and the external activity of each forest component leads to a refined loopy polynomial, which we show to be equivalent to the extended U-polynomial of Noble and Welsh and to the extended polychromate. Different specializations of this common refinement give the ordinary U-polynomial, Tutte's universal V-function, and Stanley's Tutte symmetric function, placing these invariants into a single framework. We conjecture that L_G and the U-polynomial have the same distinguishing power on simple graphs, and verify this for all graphs on at most 11 vertices. Simplicity is essential: we found two loopless multigraphs with equal U-polynomials but distinct loopy polynomials. They also have distinct extended U-polynomials, so the ordinary U-polynomial does not determine the extended one on loopless multigraphs. This solves an open problem by Merino and Noble. For the score polytope P_G of the external bizonotopal algebra, loopy deletion-contraction lifts from the lattice-point enumerator to the polytope itself. This gives forest-indexed geometric parking complexes whose lattice points partition those of P_G, and which are piecewise-linearly parametrized by products of intervals whose lengths are the component weights in the forest expansion of L_G.

Let \(N\ge2\) and let \(p\) be its least prime divisor. We prove that every nonzero polynomial with nonnegative real coefficients divisible by \(\Phi_N\) has support diameter at least \((p-1)N/p\). Equality holds precisely for positive scalar multiples of monomial shifts of the \(p\)-term geometric sum \(\sum_{j=0}^{p-1} X^{jN/p}\), thereby proving a conjecture of Steinberger. The proof turns cyclotomic divisibility into the vanishing of the first \(p-1\) Fourier moments of a positive measure on the circle and then applies a classical extremal trigonometric polynomial. As a consequence, we establish the Coven–Meyerowitz diameter bound under their tiling conditions and determine its equality cases. Longer initial intervals of vanishing Fourier coefficients yield stronger diameter bounds, including an explicit refinement in terms of the prime-power divisor sets. The extremal trigonometric polynomial also yields a quantitative concentration estimate for measures and cyclotomic multiples with near-minimal support diameter.

We prove that the $Z$-polynomial of every sparse paving matroid has only negative real zeros, confirming the real-rootedness conjecture of Proudfoot, Xu, and Young for this class. We also prove that, for each fixed positive corank, the $Z$-polynomials of uniform matroids in consecutive ranks strictly interlace. Our approach is to prove real-rootedness of the corresponding $\gamma$-polynomials for sparse paving matroids and their strict interlacing for uniform matroids, and then transfer both properties to the corresponding $Z$-polynomials.

We identify the rotational symmetry centers in the spectre tiling. We find that both 2-fold and 3-fold symmetry centers are coexisting, with two different types of 3-fold centers. Local and global symmetry operations are distinguished, and characterized in terms of substitution systems. We introduce a decomposition of the spectre tiling in terms of three metatiles named diabolo, 2-arms and 3-arms, valid at any substitution level. We propose geometrical constructions for generating patches of the spectre tiling with 2-fold and 3-fold global rotational symmetry.

Linear complementary dual (LCD) codes form an important class of linear codes with applications in cryptography, classical error correction, and quantum coding theory. In this paper, we study the neighbor relation on LCD codes over finite fields and the graph induced by this relation, where two codes are adjacent whenever they intersect in codimension one. We determine the number of neighbors of an LCD code that are also LCD, and we use this result to analyze the structure of the corresponding neighbor graph. In particular, we prove its regularity over arbitrary finite fields and establish further regularity properties for its main structural subgraphs in the binary and odd-characteristic cases. These results provide a graph-theoretic framework for the study of LCD codes and reveal a strong combinatorial regularity in their neighborhood structure.

Gross, Mansour, and Tucker [European J. Combin., 95 (2021): 103329] introduced the partial Petrial polynomial of a ribbon graph $G$, denoted by $^{\partial}{\varepsilon^{\times}_G}(z)$. For a prime bouquet $B_n$, Yan and Li [Discrete Appl. Math., 375 (2025): 281-289] determined $^{\partial}{\varepsilon^{\times}_{B_n}}(z)$ when the intersection graph $I(B_n)$ is either the complete graph or a path, and provided an equivalent condition under which the lowest degree of the nonzero coefficient in $^{\partial}{\varepsilon^{\times}_{B_n}}(z)$ is $1$. In this paper, we determine $^{\partial}{\varepsilon^{\times}_{B_n}}(z)$ when the intersection graph is a cycle. Moreover, we present a complete characterization of the prime bouquets whose lowest nonzero term in $^{\partial}{\varepsilon^{\times}_{B_n}}(z)$ is of degree $2$ and determine the partial Petrial polynomial for the prime bouquets. As corollaries, we determine $^{\partial}{\varepsilon^{\times}_{B_n}}(z)$ when $I(B_n)$ is the complete bipartite and tripartite graph.

In this short note, we prove that, for any pair of finite groups $G$ and $H$, there exist a finite $T_0$-space $X$ and a semiflow $\varphi\colon [0,\infty)\times X\to X$ such that $\operatorname{Aut}(X)\cong G$, whereas $\operatorname{Aut}(\varphi_t(X))\cong H$ for every $t>0$. Thus, the symmetry group of a finite $T_0$-space and those of all its positive-time images can be prescribed independently.

In this paper, we revisit the work of Berkovich and Paule on variants of the Andrews-Gordon identities. We find a generalization of their principal polynomial identity and, as a consequence, obtain new $\vec M$ versions of the Andrews-Gordon identities. More precisely, for non-negative integers $M_1\ge M_2\ge M_3\ge\ldots\ge M_\nu$, we show that a broad class of multi-sums of the form $$ \sum\limits_{\mathbf n} \frac{ q^{ N_1^2+\cdots+N_\nu^2 - M_1N_1 - M_2N_2 - \cdots - M_\nu N_\nu } }{ (q)_{n_1}(q)_{n_2}\cdots(q)_{n_\nu} } $$ can be expressed as a sum of products. Above, we use standard notations for $q$-Pochhammer symbols and $N_i = \sum\limits_{k=i}^{\nu}n_k$ for $1\le i\le \nu$.

A family $\mathcal F$ of finite subsets of $\mathbb Z$ is packed into $[N]$ if suitable integer translates of its members are pairwise disjoint subsets of $[N]$. We study two prescribed-difference packing problems of Alon, Dębski, Grytczuk and Przybyło for the arithmetic progressions $A_d=\{d,2d,\ldots,\lfloor n/d\rfloor d\}$ and $B_d=\{d,2d,\ldots,nd\}$. Let $m(n)$ and $M(n)$ denote the corresponding minimum packing lengths, with subscripts indicating restrictions on the admissible differences, and let $\mathcal P(x)$ denote the set of primes at most $x$. The key ingredient is a residue-class selection scheme that encodes pairwise intersection constraints by cyclic intervals. A lattice-covering argument yields a simultaneous admissible choice, permitting substantial overlap of the containing intervals and providing the sharp upper bounds needed for the bounded-diameter family and the prime-difference equal-cardinality family. For the bounded-diameter family, we prove $m(n)\sim m_{\mathcal P(\sqrt n)}(n)\sim 4n^{3/2}/(3\log n)$. For the equal-cardinality family with prime differences, we prove $M_{\mathcal P(n)}(n)\sim n^3/(6\log n)$. For the full equal-cardinality family, we show $M(n)\ge \left(\frac{19}{108}-o(1)\right)n^3/\log n$. Together with corresponding estimates for restricted ranges of differences, these results prove several conjectures of Alon–Dębski–Grytczuk–Przybyło and disprove others.

The directed clique number $\vec{\omega}(T)$ of a tournament $T$ is the minimum, over all orderings of the vertices of $T$, of the clique number of the graph whose edges are the arcs that point backward with respect to the ordering. In this paper, we prove that, for every integer $k \geq 3$, deciding whether $\vec{\omega}(T) \leq k$ is NP-complete. This answers a question of Nguyen, Scott, and Seymour, and contrasts with the classical undirected setting, where deciding whether $\omega(G) \leq k$ is polynomial-time solvable for every fixed integer $k$. On the other hand, we give a polynomial-time algorithm distinguishing tournaments with $\vec{\omega}(T) \leq 2$ from those with $\vec{\omega}(T) > 100$. We also study the tournament analogue of the Gyárfás–Sumner conjecture. We construct new $\vec{\chi}$-bounding tournaments and thereby prove a conjecture of Aboulker, Aubian, Charbit, and Lopes stating that every class of tournaments with bounded twin-width is $\vec{\chi}$-bounded. We then exhibit new tournaments that are not $\vec{\chi}$-bounding, disproving another conjecture of Aboulker, Aubian, Charbit, and Lopes, as well as two conjectures of Kim. Finally, we present infinite families of 3-$\vec{\omega}$-critical and 4-$\vec{\omega}$-critical tournaments.

We give direct combinatorial proofs that 1-semi-equational theories satisfy two combinatorial properties that imply the non-interpretability of certain fields. Our main result is that Boolean combinations of 1-semi-equations have almost linear Zarankiewicz bounds, and hence no infinite field is interpretable in a 1-semi-equational theory; this answers a question of Chernikov–Mennen and Chernikov–Starchenko, who had respectively established almost linear Zarankiewicz bounds for Boolean combinations of $(2,1)$-semi-equations and Boolean combinations of weakly normal relations. (This was recently and independently established by Gou, Mirabi, Mittal, Tran, and Yang, using different techniques and producing different bounds.) We also show that $(k,1)$-semi-equations satisfy the $\delta$-strong Erdős–Hajnal property with $\delta=1/6^{k-1}$; this had previously been established by Chernikov–Starchenko for an ineffective constant $\delta>0$.

With help of group characters we enumerate orientably-regular maps of a given type with automorphism group isomorphic to $\PGam(2,2^p)$ for prime $p$.

For a simple graph $G$ with $n$ vertices, write its chromatic polynomial in the rising factorial basis as $$ \chi_G(x)=\sum_{i=0}^{n}(-1)^{n-i}c_i(G)\langle x\rangle_i,$$ where $ \langle x\rangle_i=x(x+1)\cdots(x+i-1).$ The associated $\tau$-polynomial $$ \tau_G(x)=\sum_{i=0}^{n}c_i(G)x^i $$ was defined and systematically investigated by Brenti in 1992. In this paper, we prove that if the $\tau$-polynomials of two vertex-disjoint simple graphs $G$ and $H$ have only real zeros, then the $\tau$-polynomial of their join $G\vee H$ has only real zeros. This settles a conjecture posed by Brenti, Royle and Wagner since 1994.

We prove that join-semidistributive shellable lattices are join-extremal. In particular, every semidistributive shellable lattice is extremal. Together with known results, this gives the equivalence between extremality, left modularity, EL-shellability and shellability for semidistributive lattices. This answers open questions of Mühle and Segovia.

Let $p_j$ be the prime with index $j$. We prove that the ratios $m/n$ for which $p_m+p_n$ is a square are dense in $\mathbb R_{>0}$. The same is true when $|p_m-p_n|$ is a square. In every nonempty open interval, almost every index can be used as a numerator and as a denominator. We also give a quantitative lower bound for the number of possible partners.