Papers

In this paper, we prove the continued fraction conjecture posed by Han, Mao and Zeng for the generating function of permutations with respect to the number of descents of type $2$ and the number of cycles, thereby settling their reformulation of a conjecture originally due to Baril and Kirgizov. We further establish the symmetry of the bistatistic $(\des_2, \ear)$ over $\mathfrak{S}_n$ as conjectured by Han, Mao and Zeng and strengthen this result by exhibiting five equidistributed companions for $(\des_2, \ear)$. Here the statistic $\des_2$ denotes the number of descents of type $2$, and the statistic $\ear$ denotes the number of exclusive antirecord cycle peaks originally introduced by Sokal and Zeng.

Let $F$ be a graph. A graph $G$ is called $F$-free if $G$ does not contain $F$ as a subgraph. Let ${\rm EX}(n,F)$ denote the set of $F$-free graphs of order $n$ with the maximum edges. In this paper, we characterize the graphs in ${\rm EX}(n,F)$ for large $n$, where $F$ is the disjoint union of paths and stars. This generalizes a result in \cite{LLP}.

We obtain asymptotic formulas for additive congruences \[ \sum_{i=1}^r m_i x_i^{-s}\equiv \lambda \pmod p, \] where the \(m_i\) range over arbitrary subsets of \(\mathbb F_p^\ast\) and the \(x_i\) over shifted intervals. For five terms, in the balanced case of common cardinality \(N\), the asymptotic holds uniformly in \(\lambda\) whenever \[ N>p^{14/29+\varepsilon}, \] giving a genuine sub-square-root range. The main input is a centered fourth-moment estimate for the associated double exponential sums. The same method yields sub-square-root thresholds for every fixed \(r\ge 5\), including \(N>p^{8/17+\varepsilon}\) for six terms, with \[ \alpha_r=\frac13+\frac{4}{9\sqrt r}+O(r^{-1}) \] as \(r\to\infty\).

A $k$-irregular graph is a graph with maximum degree $k$ such that vertices of degree $k$ are not adjacent. A $2$-distance $k$-coloring of a graph is a coloring of the vertices using $k$ colors in which any two vertices at distance at most $2$ receive distinct colors. The $2$-distance chromatic number of $G$, denoted by $\chi_{2}(G)$, is the minimum integer $k$ such that $G$ admits a $2$-distance $k$-coloring. Zhu \cite{zhu} proved that $\chi_2(G)\leq 13$ for planar graphs with maximum degree at most $4$. We prove that for a 4-irregular planar graph $G$, we have $\chi_2(G) \leq 10$.

In this paper we study Borel graphs generated by finitely many commuting Borel functions. We give a geometric analysis of the free part of such graphs based on marker sets and marker regions. Assuming the existence of $r$-forward-independent hitting sets with bounded syndeticity, we obtain marker decompositions of the free part into rootless and rooted regions with controlled geometry. As applications, we derive finite Borel asymptotic dimension and hyperfiniteness, and obtain upper bounds for Borel edge chromatic numbers which improve previously known results. For the case in which each of the commuting Borel functions is bounded-to-one, we verify the existence of $r$-forward-independent hitting sets with syndeticity $Cr$ for some constant $C$. This gives another proof of a recent theorem of Shinko-Weilacher-Yu, and is used to show that if one of the commuting Borel functions is injective and another one is bounded-to-one and exactly even-to-one, then the graph has a Borel perfect matching.

The generalized pancake graph $P(m,n)$ is the Cayley graph of the group of colored permutations $\mathbb{Z}_m\wr S_n=(\mathbb{Z}_m)^n\rtimes S_n$ generated by generalized prefix reversals. In this paper, we establish that, for all $m,n\geq2$, the spectral gap $\gamma(P(m,n))$ of the normalized Laplacian satisfies $\alpha_m/n\leq\gamma(P(m,n))\leq1/n$, where $\alpha_m$ is a positive constant that depends only on $m$. As a consequence, for every fixed $m\geq2$, $\gamma(P(m,n))$ is $\Theta_m(1/n)$ as $n\to\infty$. The proof combines Cesi's semi-recursive spectral-gap inequality with a Fourier decomposition of the appropriate operators associated with a coset Schreier graph of color-position pairs. For fixed $n\geq2$, we also establish that $\gamma(P(m,n))$ is $\Theta_n(m^{-2})$ as $m\to\infty$. This disproves a conjecture of Blanco and Buehrle asserting that, for fixed $n$, the corresponding undirected generalized pancake graphs form an expander family. Additionally, we present a counterexample to a recent conjecture of Greaves and Zhu concerning equality between the spectral gaps of the full Cayley graph and the associated coset Schreier graph.

Let $K$ be a finite pure $k$-dimensional simplicial complex, with $k\ge1$, on the vertex set $[n]$ and with facet family $K_k$. Let $\lambda_1(K)\ge\lambda_2(K)\ge\cdots>0$ be the nonzero eigenvalues of its $(k-1)$-dimensional up-Laplacian, and, after ordering the vertices so that $\deg_K(1)\ge\cdots\ge\deg_K(n)$, let $\dvT{r}(K)$ be the number of vertices contained in at least $r$ facets. A complex is shifted if replacing a vertex of a face by a smaller vertex outside the face always yields another face. We prove that there is a shifted family $\HH$ of $(k+1)$-element subsets of $[n]$, with the same number of members as $K_k$, such that \[ \tfrac12\bigl|K_k\,\triangle\,\HH\bigr| \;\le\; \tfrac12\left[\sum_{r\ge1}\bigl(\dvT{r}(K)\bigr)^{2}-\sum_{r}\lambda_r(K)^{2}\right]. \] The left-hand side counts the facets that have to be exchanged to reach $\HH$; thus one half of the gap between the second power sums of the two sequences bounds the distance of $K_k$ to a shifted family. The characterization $\lambda(K)=\dv(K)^{\mathsf T}\iff K$ is isomorphic to a shifted complex was established in \cite{Gupta} from the identity that this gap equals twice the number of failed elementary shifts. The present paper converts that identity into a quantitative stability statement and recovers the equality characterization at zero defect. For $k=1$ this bounds the number of edge exchanges needed to reach a threshold graph with the same number of edges.

Kühn, Sauermann, Steiner and Wigderson recently disproved the Odd Hadwiger Conjecture, even for graphs with independence number 2. For this class of graphs the conjecture is known to be equivalent to the following: every $n$-vertex graph $G$ with independence number 2 contains $K_{\lceil \frac n2 \rceil}$ as an odd minor. While this does not hold, we prove that every graph $G$ with independence number 2 contains $K_{\lceil \frac n2 \rceil}$ as an odd minor or as a totally odd immersion.

For $1\leq k<n$, let $P(n,k)$ be the directed overlap graph whose vertices are the $k$-permutations of $[n]$ and whose arcs are the $(k+1)$-permutations. Isaak proved that $P(n,n-2)$ has no directed Hamiltonian cycle for $n\geq4$ and asked whether it nevertheless has a directed Hamiltonian path. We answer this question affirmatively by showing that $P(n,n-2)$ has a Hamiltonian path.

Mizzi conjectured that every nontrivially unstable graph contains cycles C_k and C_{2k} for some odd k. We give a connected, nonbipartite, vertex-determining counterexample on ten vertices. Its instability is certified by an explicit nontrivial two-fold automorphism, and its complete set of simple-cycle lengths is {5,5,6}.

For every integer $k\ge2$, Chen and Raspaud conjectured that each graph $G$ with odd girth $\og(G)\ge2k+1$ and maximum average degree $\mad(G)<2+1/k$ has a $(2k+1:k)$-coloring. In this paper, we prove the conjecture.

We study a variant of Cops and Robbers in which the robber attempts to visit as many vertices of the graph as possible without being captured, while the cop aims to keep the robber confined to a small set of vertices. The damage number of a graph $G$, introduced by Cox and Sanaei in 2019, is the maximum number of vertices the robber can visit in a game of Cops and Robbers on $G$. In this paper, we determine damage numbers for several classes of graphs, including hypercubes, Hamming graphs, Johnson graphs, incidence graphs of projective planes, and Erdős-Rényi random graph $G(n,p)$, for $p \gg \log^{2/5}(n) / n^{1/5}$. We also show that the problem of determining the damage number of a graph is PSPACE-complete.

The Rogers–Ramanujan identities equate a $q$-series whose exponents are governed by a quadratic form with an infinite product supported on two residue classes modulo~$5$. Identities of this shape are scarce, and a central problem is to identify the structures that produce them in families. Huang, Jiang, and Oblomkov have proposed a source of a new kind: to each pair of coprime integers $a,b>1$ they attach an infinite-rank $q$-series $Z_{a,b}(q)$, assembled from counts of commuting nilpotent matrix pairs $(A,B)$ with $A^a=B^b$ over finite fields, and they conjecture that it equals an explicit product of $(a-1)(b-1)/2$ modular units of level $a+b$. The $a=2$ cases are the Andrews–Gordon identities; no case with $a>2$ was known. We prove the conjecture for $(a,b)=(3,4)$, $(3,5)$, $(3,7)$, and $(3,8)$. Our proofs pass through a finer sum-to-sum identity, which we conjecture for all $b$ coprime to $3$ and establish for all $b$ when $q=1$. Lau and Ono have since proved that identity in general, and with it the full $a=3$ case. These identities have been formalized and verified in Lean by AxiomProver.

In the study of the generating series of Demazure characters, Lascoux used isobaric divided differences to define a family of polynomials $\mathcal{E}_{\sigma}(t)$ indexed by permutations $\sigma$, and asked for a satisfactory expression of these polynomials. In this paper we obtain a combinatorial interpretation of $\mathcal{E}_{\sigma}(t)$ for the permutation $\sigma=[2,3,\ldots,n,1]$ or its inverse in terms of the descent statistic of parking functions of length $n-1$. Based on this progress on Lascoux's open problem, we find that the polynomial $\mathcal{E}_{\sigma}(t)$ for this special case coincides with the $h$-polynomial $h(\Delta(\mathrm{NC}_W),t)$ of the order complex of the noncrossing partition lattice associated to the irreducible Coxeter group $W$ of type $A_{n-1}$. We are inspired by this coincidence to give an operator approach to $h(\Delta(\mathrm{NC}_W),t)$ for any finite Coxeter group $W$. As an application, we completely solve an open problem on $h(\Delta(\mathrm{NC}_W),t)$ which was proposed by Athanasiadis, Douvropoulos and Kalampogia-Evangelinou. For any $k$-divisible noncrossing partition poset $\mathrm{NC}^{(k)}_W$, we also obtain the interlacing symmetric decomposition property of the $h$-polynomial $h(\Delta(\mathrm{NC}^{(k)}_W),t)$.

Let $G$ be an $r$-partite graph such that the edge density between any two parts is at least $\alpha$. We consider the problem of determining how large $\alpha$ must be in order to guarantee that $G$ has a Hamiltonian traversal (an $r$-cycle subgraph containing exactly one vertex from each part), and show that this critical density tends to $\frac 1 2$ as $r$ increases. This resolves a conjecture of Badakhshian, Falgas-Ravry, and Sharifzadeh. We also study the critical densities necessary to guarantee the existence of other spanning structures in traversals, particularly subgraph factors, and obtain asymptotically the critical densities for traversal $F$-factor subgraphs for several classes of graphs $F$. The proofs of our results involve the absorption method.

We prove an analogue of a theorem of Berget and Rhoades about extending the parking space $\mathrm{Park}_n$ to an $S_{n+1}$-module $\mathrm{Slim}_n$. Specifically, we show that the bipartite parking space $\mathrm{Park}_{K_{n,m}}$, which naturally comes with an $S_{n-1} \times S_m$ action, extends to an $S_n \times S_m$-representation $\mathrm{Slim}_{n,m}$. We then formulate a conjecture generalizing this statement to any simple graph.

Sylvester's denumerant $d(t; \boldsymbol{A})$ counts the number of nonnegative integer solutions to $\sum_{i=1}^{N} a_i x_i = t$, where $\boldsymbol{A} = (a_1, \dots, a_N)$ is a sequence of positive integers with $\gcd(\boldsymbol{A}) = 1$. In 2025, Xin and Zhang gave a polynomial time algorithm in $N$ for computing $d(t; \boldsymbol{A})$ when the entries of $\boldsymbol{A}$ are bounded by a constant. In this paper, we extend this algorithm by incorporating Barvinok's algorithm, enabling it to handle the case where a fixed number of entries of $\boldsymbol{A}$ are allowed to be unbounded.

Bradač, Sudakov, and Wigderson characterized $p$-locally dense graphons by a quadratic inequality for all bounded nonnegative functions. Their proof uses Reiher's finite lemma and graphon approximation, and they asked for a direct proof. We give one by rounding simple functions. Divide each level set into $m$ equal-measure pieces and retain each piece independently with probability equal to its level. Off-diagonal terms agree in expectation; the diagonal error is at most $\norminf{W-p}/(4m)$. Letting $m\to\infty$ and then approximating in $L^1$ proves the inequality. A three-atom example shows that atomlessness is necessary if arbitrary probability spaces are allowed.

Let $F$ be a field, let $0\le \ell\le k-2$, and suppose that $n\ge k-1$. We determine the minimum degree of a polynomial in $F[x_1,\ldots,x_n]$ that vanishes to order at least $k$ at every nonzero vertex of the Boolean cube and to order exactly $\ell$ at the origin. The answer is \[ n+2k-2-\rho_F(k-\ell), \] where $\rho_F(s)$ is the least number of positive integers summing to $s-1$ whose corresponding Catalan numbers are nonzero in $F$. The proof gives an explicit basis of the reduced vanishing space. In this basis the top-degree map is diagonal, with Catalan numbers on the diagonal; a refinement using block coordinates shows that the basis is compatible with polynomial degree. In odd characteristic the degree is either $n+2k-3$ or $n+2k-4$, according as $C_{k-\ell-2}$ is nonzero or zero. In characteristic $2$ it is \[ n+2k-2-s_2(k-\ell-1), \] where $s_2$ denotes binary digit sum. Thus the first characteristic drop, and all later drops, are determined exactly.

A coefficient duality first encountered for formal Bernoulli series is shown to be equivalent to a general Möbius covariance law for formal power series. We obtain a structural characterization, an eigenspace interpretation, and a weighted form of this duality. The Catalan convolution and Chebyshev identities from the motivating Bernoulli setting extend to arbitrary Möbius-covariant families and yield a general Ramanujan-type summation formula encompassing consecutive half-integer powers. The framework also recovers classical Bernoulli and Euler recurrences and produces recurrence families for colored matchings and generalized central trinomial coefficients, with further realizations from reflection-symmetric Appell sequences and Gorenstein Hilbert series.

Let $\mathfrak{X}_k\subseteq{\sf Mat}_{m, n}$ denote the variety of $m\times n$ complex matrices with rank at most $k$. The power series and rational expressions for the Hilbert series of $\mathfrak{X}_k$ are known by geometric arguments, and equating these expressions yields a family of formulas generalizing the classical Cauchy and dual Cauchy identities. We pose the problem of giving a direct combinatorial proof of these formulas for $0 < k < \min\{m, n\}$. When $k=1$ or $k=\min\{m, n\}-1$, we give such a proof via an explicit sign-reversing involution on certain sets of Littlewood–Richardson tableaux.

We prove a log-submodularity-type inequality for zonoids in $\mathbb{R}^4$, extending the three-dimensional result of Fradelizi, Madiman, Meyer, and Zvavitch. More generally, we conjecture a log-submodularity-type inequality for zonoids in arbitrary dimension. This inequality admits several equivalent formulations in terms of volumes of coordinate projections as well as in terms of mixed volumes, thereby unifying several geometric perspectives. We reduce the conjectured inequality to a polynomial inequality whose variables are associated with the vertices of a hypercube and whose coefficients encode the volumes of 0/1 simplices. This reduction reveals unexpected connections between mixed volumes of zonoids, matroid theory, and real algebraic geometry.

We give an effective algorithm for determining the transportation distance between two given probability density functions defined on the vertices of a graph $G=(V,E)$ by analyzing an associated polytope. The vertices of the polytope correspond to feasible flows on spanning trees in $G$, and the $1$-skeleton of the polytope is a projection of the spanning tree state graph associated with the Glauber dynamics on $G$. The optimal value of this transportation problem, known as the $1$-Wasserstein distance, can be computed by tracing the transportation cost along the vertices of this polytope. We show that a local minimum of the transportation cost is also a global minimum, and this leads to a steepest descent algorithm for solving the transportation problem. If the probability density functions take discrete values in $\delta \mathbb{Z}$ for some $\delta>0$, then the optimal transport cost can be reached in at most $\frac{|V|-1}{\delta}$ steps. As an application, we give an efficient algorithm for computing the Ollivier–Ricci curvature of a graph.

Recent major breakthroughs in $q,t$-combinatorics include the introduction of the Dyck path algebra $\mathbb{A}_{q,t}$ by Carlsson and Mellit and of the Catalanimals by Blasiak et al., both of which led, among other things, to independent proofs of different extensions of the rational shuffle conjecture of Bergeron et al. The first main contribution of this paper is a simple, explicit formula inside the algebra $\mathbb{A}_{q,t}$ for the Negut operators, yielding a direct, elementary connection between the original operators of the rational shuffle conjecture and the corresponding Catalanimals. Our formula bypasses the elliptic Hall algebra, turning these operators into transparent, workable tools whose action we can compute exactly and efficiently on any symmetric function, not just constants. Our second main contribution consists of a series of explicit formulas relating the Negut operators to the Theta operators introduced by D'Adderio et al. To prove these formulas, we provide an extension of the aforementioned Theta operators to the entire algebra $\mathbb{A}_{q,t}$, allowing us to obtain a series of new combinatorial results. The algebraic computations underlying this extension have been formalized in Lean. To showcase the power of our results, we give a proof, also partially formalized in Lean, of the Theta conjecture of D'Adderio et al., first stated in 2019.

We give a complete proof of the 2011 Tu–Deng conjecture. We begin from its original modular pair-count formulation, prove an equivalent cyclic Hamming weight-drop formulation, and establish the exact transfer identity that connects this count with a two-variable matrix polynomial. The proof then reduces the conjecture to normalized inequalities for the coefficients of that polynomial. A 2011 conjecture by the author which came to be called the Cusick Conjecture (it is a consequence of the Tu–Deng Conjecture) was proved by K. Cheng in 2026. The proof in the present paper extends the cyclic deletion ideas of Cheng. The new ideas might be applicable to other problems.

We study conditions for a countable group acting on a connected locally finite hyperbolic graph to induce a hyperfinite orbit equivalence relation on the Gromov boundary of the graph in terms of tree-decompositions of the graph. We prove that for a connected locally finite hyperbolic graph $X$ equipped with an action of a countable group $G$, if $(T, \beta)$ is a $G$-invariant tree-decomposition of $X$ such that each bag induces a connected subgraph $X_t$ of $X$ for each $t \in V(T)$, each adhesion set is finite and such that there are only finitely many $G$-orbits of edges of $T$, then the orbit equivalence relation of $G$ acting on the Gromov boundary $\partial X$ is hyperfinite provided the orbit equivalence relation of $G$ acting on $\partial T$ is hyperfinite and the orbit equivalence relations of the bag stabilizers acting on $\partial X_t$ are all hyperfinite. We show that the converse also holds if $(T, \beta)$ satisfies the additional property that each adhesion set distinguishes at least two ends of $X$.

A graph is perfectly divisible if every induced subgraph with at least one edge admits a partition into a perfect induced subgraph and an induced subgraph with smaller clique number. Every perfectly divisible graph $G$ satisfies $\chi(H)\leq\binom{\omega(H)+1}{2}$ for every induced subgraph $H$ of $G$. We show that the converse fails: for every non-negative integer $t$, the graph $P(17)\vee K_t$ satisfies this bound for every induced subgraph but is not perfectly divisible, yielding an infinite family of counterexamples. Motivated by this distinction, we introduce $(k,\ell)$-linear divisibility and prove that every $(k,\ell)$-linearly divisible graph $G$ satisfies $\chi(G)\leq k\binom{\omega(G)+1}{2}$. As an application of this framework, we give a direct structural decomposition showing that every chair-free graph is $(2,2)$-linearly divisible, where a chair is obtained from $K_{1,3}$ by subdividing one edge once. This chair-free result was obtained independently before we became aware of a recent preprint of Liu, Sun, Wang, Wu, and Zeng [arXiv:2608.13519], who prove the stronger statement that every chair-free graph is perfectly weight divisible and hence satisfies $\chi(G)\leq\binom{\omega(G)+1}{2}$.

For a graph $G$, let $L(G)=\max\{\omega(G),\lceil (|V(G)|+1)/(\alpha_{\min}(G)+1)\rceil\}$, where $\omega(G)$ is the clique number and $\alpha_{\min}(G)$ is the minimum, over all vertices $v$, of the largest size of an independent set containing $v$. Dybizbański, Furmańczyk, and Mkrtchyan (Discrete Appl. Math. 354 (2024), 15–28) conjectured that every block graph $G$ satisfies $L(G)\leq\chi_{=}(G)\leq L(G)+1$, where $\chi_{=}(G)$ is the equitable chromatic number of $G$. We disprove this conjecture in a strong form. For every pair of integers $d\geq 2$ and $k\geq 4d-1$, we construct a connected block graph $G_{d,k}$ such that $L(G_{d,k})=k$ and $\chi_{=}(G_{d,k})=k+d$. Thus the difference $\chi_{=}(G)-L(G)$ is unbounded on connected block graphs.

Let $\Gamma$ be a finite group of order $k\ge2$, and label the edges of a simple loopless $d$-regular digraph $D$ by elements of $\Gamma$. A directed cycle is zero-sum if the ordered product of its labels is the identity of $\Gamma$. We prove that a zero-sum cycle exists whenever $d\ge e^3(k-1)$. We also prove that every labelled $d$-regular digraph contains $\Omega(d/k)$ pairwise vertex-disjoint zero-sum cycles. When $d\ge50k$, it contains $\Omega(d^2/k)$ pairwise edge-disjoint zero-sum cycles. All three results are asymptotically optimal. The existence and packing results extend to Eulerian digraphs whose minimum and maximum common degrees $\delta$ and $\Delta$ satisfy $\delta^3/\Delta^2=\Omega(k)$. The techniques extend a determinant–permanent argument of Friedland for even directed cycles.

By work of Enomoto, Jackson, Katerinis, and Saito from 1985, every $2$-tough graph has a $2$-factor, and this toughness bound is best possible: for every $\varepsilon>0$, there exist $(2-\varepsilon)$-tough graphs with no $2$-factor. It is natural to ask whether the latter statement remains true for triangle-free graphs. Bauer, van den Heuvel, and Schmeichel conjectured this in 1996. In the same paper, they proposed an infinite family of triangle-free graphs with no $2$-factor whose toughness they believed approaches $2$, but the required toughness bound was not established. In this paper, we confirm their conjecture. For every even integer $q\ge 6$, we construct a triangle-free graph $G_q$ with no $2$-factor and with toughness \[ \tau(G_q) =\frac{2q^2-q-2}{q^2+q} =2-\frac{3q+2}{q^2+q}. \] In particular, $\tau(G_q)\to 2$ as $q\to\infty$, showing that the threshold $2$ for the existence of a $2$-factor remains best possible even within the class of triangle-free graphs.