Papers

We study graph systems generated by $\Delta$-Y and Y-$\Delta$ moves and prove that, for initial graphs of minimum degree at least $7$, $\Delta$-Y moves alone generate every reachable graph. As a consequence, for $n\ge 8$, the $\Delta$-Y system generated from the complete graph of $n$ vertices is canonically isomorphic as graded directed graphs to the space of partial Steiner systems on $n$ points.

We construct an explicit infinite family of simple two-dimensional Cayley complexes over $\mathbb{F}_2^n$ whose degree is polynomial in $n$ and whose nontrivial vertex-link eigenvalues lie in $[-\lambda,\lambda]$ for every fixed $\lambda>0$. For every fixed $d\ge2$, we also obtain an explicit infinite family of weighted $d$-dimensional Cayley complexes over $\mathbb{F}_2^n$ with codimension-two local spectral norm at most $1/d$ and Cayley degree $\Theta_d(n)$. Our two-dimensional construction uses evaluation at rational points of algebraic curves to produce projective direction sets and many functions affine along these directions, which may be useful for further constructions and improvements.

Motivated by a log-convexity question of Bennett and Tao, we consider Gowers-type functionals defined by $L^p$ norms of multiple autocorrelations. We prove sharp bounds in terms of $L^q$ norms and characterise the near-extremisers on Euclidean spaces as well as locally compact abelian groups. We also establish two families of degree-lowering inequalities and study their near-extremisers. As a byproduct of this broader theory, we show that the constant in the log-convexity estimate for Gowers norms is strictly less than unity, confirming the aforementioned conjecture of Bennett and Tao. Finally, we characterise the $p$ for which the Gowers-type functionals necessarily satisfy the triangle inequality on nonnegative measurable functions.

We ask how small an increasing integer model of a finite real set can be while preserving all equalities between equal-length sums of at most $q$ elements, with repetitions allowed. The increasing correspondence must preserve exactly which sums are equal; the signs of unequal comparisons may change. Let $H_m(q)$ be the least diameter sufficient for every ordered real set of size $m$. For every integer $q\ge2$ we prove $H_4(q)=q(q+1)$ and $H_5(q)=q^2(q+1)$, and we determine $H_6(2)=24$. The proofs use the linear space determined by the additive equalities and the inequalities prescribing the order of the elements. They also give bounds for larger sets, determine the first two asymptotic terms for each fixed $m\ge4$, and yield further families of sharp examples. An application bounds the integer alphabets needed to realize finite additive-square-free spectra. The supplementary data support the finite six-element classification.

We prove several new structural and classification results about $d$-regular graphs with positive Lin–Lu–Yau (LLY) curvature. We show that any positively curved $d$-regular graph has diameter at most $2d-2$, which improves the previously best known diameter bound obtained from the Bonnet-Myers-type theorem for positively curved graphs. We further show that every positively curved $d$-regular graph with $d\ge 3$ is $3$-connected. We classify all positively curved $3$-regular graphs, as well as all positively curved regular planar graphs.

We consider a random subgraph $G_p(n,r,<s)$ of the complete distance graph $G(n,r,<s)$ whose vertices are the $r$-element subsets of the set $\{1,\dots,n\}$ and whose edges join pairs of subsets that intersect in fewer than $s$ elements; each edge survives independently of the others with probability $p$. The independence number of the graph $G(n,r,<s)$ equals $C_{n-s}^{r-s}$ – this is the classical Erdos-Ko-Rado theorem. We prove that, for $r=r(n)\to\infty$, $s=s(n)\to\infty$, $s=o(r)$, $r^2=o(n)$ and $p\ge 16\,sr^2\ln(n/r)/n$, with probability tending to 1 the independence number of the random graph $G_p(n,r,<s)$ also equals $C_{n-s}^{r-s}$, i.e., the Erdos-Ko-Rado result is stable under random sparsification of the graph. Thereby, in the range of parameters $s\to\infty$, $s=o(r)$, a recent result of Raigorodskii and Karas is strengthened: the lower bound on the probability $p$ that guarantees stability is lowered by a factor of about $r/s$.

An intrinsically knotted graph is one for which every spatial embedding contains a nontrivially knotted cycle. Classifying such graphs is a central problem in spatial graph theory. It is known that every intrinsically knotted graph has at least 21 edges, and the case of 21 edges has been completely resolved. For 22 edges, however, the classification remains incomplete. In particular, exactly eight triangle-free examples with a vertex of degree at least 5 are known, leaving only the case in which all vertices have degree 3 or 4. In this paper, we introduce a method for detecting intrinsic knottedness based on induced subgraphs obtained by deleting pairs of vertices. Using this method, we classify all triangle-free intrinsically knotted graphs with 22 edges having eight vertices of degree~4 and four of degree~3. We prove that there are exactly four: Cousins 43, 105, and 109 in the $E_9\!+\!e$ family and the graph $H_{12}\! +\! e$ in the $H_9\!+\!e$ family.

Let $A\in\mathbb{R}^{m\times n}$ have columns of Euclidean norm at most one. We prove that $\operatorname{disc}(A)\le2395\left(1+\log_+\frac n9\right)^{1/4}+2\sqrt2$. Here $\log_+t=\max\{0,\log t\}$. Building on Bansal and Jiang's affine spectral independence framework, we remove the $(\log\log n)^{7/4}$ factor from their bound. The fourth root comes from balancing the logarithmic decrease in the alive dimension against the fourth power of the row thresholds. Historical exponential sums control the covariance budget across size classes with summable thresholds. An exact threshold-sum certificate gives the coefficient $2395$, and rounding at most eight remaining fractional coordinates costs $2\sqrt2$. The finite construction also gives partial colourings from any prescribed starting point and at any prescribed depth, preserving existing signs. We formalize the partial- and full-colouring theorems in Lean, including the finite trajectory, exact threshold sum and final rounding, with Bansal–Jiang Theorem A.4 as the sole external research theorem assumption.

We study Turán-type extremal problems for cancellative and locally thin uniform hypergraphs. An $r$-uniform hypergraph is $t$-cancellative if $(\cup_{i=1}^t A_i)\cup B\ne (\cup_{i=1}^t A_i)\cup C$ whenever $A_1,\ldots,A_t,B,C$ are distinct edges. Let $C_t(n,r)$ denote the maximum number of edges in such a hypergraph on $n$ vertices. For all fixed integers $t,k\ge2$, we prove that $C_{2(t-1)}(n,tk)=(1+o(1))\frac{\binom{n}{k}}{\binom{tk-1}{k-1}}$ as $n\to\infty$. In the case $t=2$, this shows that Füredi's 2012 upper bound for $C_2(n,2k)$ is asymptotically sharp. The lower bound uses locally sparse induced packings, while the upper bound follows from double counting and a matching argument. More generally, for integers $s\ge t\ge1$, an $r$-uniform hypergraph is locally $(s,t)$-thin if among any $s$ distinct edges, at least $t$ contain a vertex that lies in none of the other $s-1$ edges. This notion includes cancellative hypergraphs as special cases. We establish general upper and lower bounds for the corresponding extremal numbers and determine their polynomial order of growth under suitable divisibility assumptions.

Let $(a_n)_{n\geq0}$ be a sequence of complex numbers, and define \[ b_n=\sum_{k=0}^n \binom{n}{k} a_k, \qquad c_n=\sum_{k=0}^n \binom{n}{k}(-1)^{n-k}a_k. \] Let $\beta>1$, put $\alpha=\sqrt{\beta^2-1}$, and suppose that $b_n,c_n=O(\beta^n)$. Mashreghi and Ransford proved that \[ \limsup_{n\to\infty}\frac{|a_n|}{\alpha^n} \leq \kappa \left(\limsup_{n\to\infty}\frac{|b_n|}{\beta^n}\right)^{\!1/2}\! \left(\limsup_{n\to\infty}\frac{|c_n|}{\beta^n}\right)^{\!1/2} \] with a universal constant satisfying $2/\sqrt{3} \leq \kappa\leq2$. We prove that the optimal constant is indeed $\kappa=2/\sqrt{3}$. The proof, which uses exponential generating functions, Phragmén-Lindelöf estimates, and Cauchy's formula, is compared to the classical one of Mashreghi and Ransford.

Let $P_t$ denote the induced path on $t$ vertices. Let $\omega(G)$ denote the maximum number of vertices in a clique of a graph $G$. Gyárfás (1987) proved that every $P_t$-free graph $G$ satisfies $\chi(G)\le(t-1)^{\omega(G)-1}$, and Gravier, Hoàng, and Maffray (2003) improved this to $\chi(G)\le (t-2)^{\omega(G)-1}$ for $t\ge4$. We lower the base of the exponential by one: for every $t\ge5$, every $P_t$-free graph $G$ satisfies \[ \chi(G)\le 3\,(t-3)^{\omega(G)+4}. \] The proof combines two refinements of the Gyárfás path argument and was developed with the assistance of Claude Fable 5.1 of Anthropic and GPT Pro of OpenAI.

We study the Longest Edge Bisection (LEB) process as a dynamical system on the projective shape space of simplices. A long-standing conjecture going back to Adler and Rivara-Levin and motivated by finite-element mesh refinement, often taken as a standing assumption, is that this procedure is non-degenerate and, in fact, in a certain way periodic. We prove: \begin{itemize} \item There are 3-dimensional simplices such that the longest edge-bisection algorithm degenerates. \item There is an open set of 4-dimensional simplices on which the longest edge-bisection algorithm degenerates. \item If parametrizing the space of $d$-dimensional simplices by independent standard Gaussian vectors, then as $d$ increases, a random simplex degenerates asymptotically almost surely. \end{itemize} This is realized through exhibiting hyperbolic behaviour of the LEB process. We also exhibit elliptic behaviour that is nonperiodic.

We study graph-based automata: nondeterministic finite automata obtained from edge-colored or oriented graphs by taking every vertex as both initial and accepting, and every edge as a pair of opposite transitions. The language of these automata corresponds to the set of edge-colored or oriented paths mapping to their corresponding graphs. We develop an analogous notion for trees and characterise the languages recognised by these models. For tree languages we prove the existence of a unique size- minimal graph and, more generally, a homomorphism-minimal graph for both word and tree languages using duality methods. In order to further motivate these models, we showcase a few results at the inter- section between graph theory and automata theory: We relate graph-based automata to reversible automata, give a decomposition of graph-based languages into reversible languages, and introduce the remanent language of an undirected graph as the inter- section of all its orientations. This remanent language captures structural information on the graph such as chromatic number.

Let \(p(n)\) denote the ordinary partition function. Motivated by analogous questions concerning Euler's totient function and its complementary counting function, we study the range of the partition-derived sequence \(p(n)-n\). We give combinatorial interpretations of this sequence and investigate both the attained and omitted positive integers. We obtain exact and asymptotic information about the gaps between consecutive attained values and show that the range is remarkably sparse: its counting function has order \((\log x)^2\), and consequently the range has natural density zero. We also extend the discussion to partitions whose Durfee square has side at least a fixed positive integer.

Kanade and Russell initiated a family of conjectural Rogers–Ramanujan type identities of moduli $9$ and $12$, which ultimately comprised five modulo $9$ identities and eleven modulo $12$ identities. The eleven modulo $12$ conjectures were subsequently settled through the work of Bringmann, Jennings-Shaffer, and Mahlburg and of Rosengren. In this paper, we prove all five modulo $9$ Kanade–Russell sum-product identities, four individual generalized Nahm-sum dual identities, and a product formula for the natural dual companion of the fifth Kanade–Russell identity, which is expressed as a linear combination of two negative-mixed-term generalized Nahm sums. The first three individual dual identities settle Conjecture~3.6 of Wang and Wang, while the fourth proves the corresponding conjecture of Li and Wang. Our results also connect directly with the recent Dynkin-diagram framework of Sun and Wang for generalized Nahm sums. They identified the rank-two pairs $(T_1,G_2)$ and $(G_2,T_1)$ as unresolved cases whose modularity would follow, respectively, from the first modulo $9$ Kanade–Russell identity and its Wang-Wang dual. The present results prove precisely these two required identities and hence establish the corresponding modularity statements unconditionally.

Given a simple graph $G = (V, E)$ on $v$ vertices and two distinct vertices $x, y \in V$, the co-degree $c_{x,y}$ associated to the pair $\{x, y\}$ is the number of their common neighbors in the graph $G$. The co-degree sequence of $G$, denoted by $\gamma(G)$, is the list of all the co-degrees associated to all the possible pairs of distinct vertices, arranged in non-increasing order. In this paper we consider the following problem, which can be viewed as a generalization of a result by Erdős and Gallai as well as of the Erdős, Rényi and Sós' friendship theorem: given an integer $v\geqslant 2$ and a sequence $\gamma$ of nonnegative integers arranged in non-increasing order, establish if there exists a simple graph on $v$ vertices having $\gamma$ as its co-degree sequence and, in case of positive answer, provide such a graph. We provide a full answer to this problem for the class of planar $C_4$-free graphs.

While people have studied $m$-ary partitions of an integer $n$ and studied conjugation of partitions of $n$, these topics are rarely mixed because the $m$-ary property is almost always lost after conjugation. In a previous work, Flowers and Lockard investigated $m$-ary partitions of $n$ whose conjugates were also $m$-ary. We generalize that previous work by studying $m$-ary partitions whose conjugates are $q$-ary, where $m$ and $q$ may be distinct. We provide a family of operators on these partitions that can be used to generate all such partitions uniquely and associate a unique polynomial with each partition based on the sequence of operators used to generate it. Using the generating operators and modular arithmetic we explore many examples and families of $m$-ary partitions whose conjugates are $q$-ary.

Symmetric powers of matroids were introduced by Lovász and Mason. The subject has recently attracted renewed interest through its connection with the realizability of tropical linear spaces by tropical ideals. Anderson proved that the tropical linear space associated with a matroid $M$ is the variety of a tropical ideal if and only if $M$ has a $d$th symmetric power for every positive integer $d$. He also asked whether the Vámos matroid $V_8$ has a second symmetric power. We answer this question in the negative by proving that $V_8$ has no second symmetric power. By Anderson's characterization, the associated tropical linear space cannot be realized as the variety of a tropical ideal.

The $F$-invariant in cluster algebras is a combinatorial invariant that unifies the $E$-invariant from additive categorification and the $\mathfrak{d}$-invariant from monoidal categorification. In this paper, we study its refinement, the partial $F$-invariant, and establish its mutation formula under changes of the initial seed. As an application, we prove a conjecture of Reading, which asserts that the non-compatible cluster variables can be separated by sign-coherence of $g$-vectors upon varying the initial seed. We further show that, for cluster monomials, the partial $F$-invariants coincide with both the partial $E$-invariants for reachable decorated representations of quivers with potentials and the pole orders of normalized $R$-matrices (or partial $\mathfrak{d}$-invariants) for finite-dimensional reachable simple modules over quantum affine algebras. As consequences, we obtain a combinatorial formula for the pole orders for reachable simple modules in terms of $q$-characters; we verify the conjectural explicit formula for the pole orders between Kirillov–Reshetikhin modules.

Two combinatorial rules are known for the Grassmannian Grothendieck polynomial $G^{(\beta)}_\lambda$: a sum over set-valued tableaux of shape $\lambda$, due to Buch, and a sum over the efficient cells of a cellular decomposition of the Gelfand-Zetlin polytope $GZ(\lambda)$, due to E. Presnova and the author. All coefficients in both sums equal $1$. We construct an explicit bijection between the two indexing sets which matches the summands term by term, carrying the number of excess entries of a tableau to the dimension of the corresponding cell; in particular the two rules are equivalent, either being deducible from the other. The efficiency condition on cells turns out to be the column-strictness of tableaux. We then transport Yu's square-root crystal operators to the cells and find that they respect dimension, along a double $i$-string the cells alternate between two consecutive dimensions, but not incidence: consecutive cells of such a string need not share a point, already for $\lambda=(2,1,0)$.

An orthogonal signed graph is a connected signed graph whose signed adjacency matrix has pairwise orthogonal rows. They are closely related to Hadamard matrices, maximal arrangements of equiangular lines, bipartite Ramanujan graphs, and the remarkable resolution of the Sensitivity Conjecture. Orthogonal signed graphs of degree at most 4 have been completely classified, and partial results were known for degree 5. We complete the classification of orthogonal signed graphs of maximum degree 5. We also provide several new infinite families of 6- and 8-regular orthogonal signed graphs.

Delcourt and Postle proved that every $K_t$-minor-free graph is $O(t\log\log t)$-colorable and reduced the Linear Hadwiger Conjecture to coloring $K_t$-minor-free graphs on $O(t\log^4 t)$ vertices. In this paper, we use the star contraction technique to improve their bound for small graphs and use their reduction to extend this improvement to all $K_t$-minor-free graphs. Thus we improve their $O(t\log\log t)$ bound to $O(t\sqrt{\log\log t})$.

Fix two positive braid words $\beta_+,\beta_-$, and let $\text{Conf}(\beta_+,\beta_-)$ be the corresponding (type A) double Bott-Samelson variety. Let $\beta$ be a double braid word containing $\beta_+,\beta_-$ as the top, bottom words. We consider the open cluster torus $T(C_\beta)$ associated to a triangulation $C_\beta$ in $\text{Conf}(\beta_+,\beta_-)$ from arXiv:1904.07992, and we identify these with weighted plabic fences, where the usual local moves on planar bipartite graphs naturally correspond to change of torus coordinates in double Bott-Samelson variety. Moreover, $T(C_\beta)$ can be parametrized explicitly by certain matrix products, and also has monomial coordinates given by the cluster variables, which are matrix minors. We interpret these minors as a generalized notion of perfect matchings on weighted plabic fences, which may not be reduced plabic graphs. Using this interpretation, we show that the cluster variables are given by "generalized minimal matchings", extending the minimal matchings from arXiv:1606.08383. Lastly, we derive a Chamber Ansatz formula for double Bott-Samelson varieties via face alternating products from dimer theory. In general, plabic fences are not reduced plabic graphs, yet we are able to extend and apply the standard tools such as local moves on plabic graphs, trips, and minimal matchings to them.

We develop a variational framework for extremal Lin–Lu–Yau curvature under positive edge reweighting with the combinatorial metric fixed. For a connected locally finite graph $G$, define \[ \Kmax(G) := \sup_{w>0}\inf_{e\in E(G)}\kappa_{\LLY}^w(e). \] This invariant relates edgewise discrete curvature to global combinatorial and topological data. In the high-girth regime, we prove for every connected locally finite graph the exact identity \[ \Kmax(G)=\frac4{\mad(G)}-2, \] with the convention $1/\infty=0$. The formula is also equivalent to a normalized Euler-characteristic density: \[ \Kmax(G) = \inf_{\substack{H\subseteq G\text{ finite}\\E(H)\ne\varnothing}} \frac{2(c(H)-\beta(H))}{|E(H)|}. \] For arbitrary locally finite graphs, a nonnegative short-cycle surplus yields girth-dependent density bounds, with rigidity results in the finite case. We also classify the locally finite graphs of girth at least $6$ admitting a positive edge weight with nonnegative curvature on every edge: they are precisely the trees and the finite cycles.

We derive linear programming (LP) bounds on the minimum distance of binary and ternary linear complementary dual (LCD) codes by imposing arithmetic constraints on their weight enumerators. Special values of the weight enumerator give finitely many Gauss phases, each of which yields linear equations in the ordinary weight-distribution variables. The resulting bounds strengthen the real-valued LCD counting LP without introducing additional variables; both the number of branches and the number of added equations per branch are bounded independently of the code length. Exact certificates establish strict improvements for 62 binary parameter pairs of length at most 20 and 39 ternary pairs of length at most 14. For four binary pairs, the bounds also improve the joint-weight-enumerator LP while using fewer variables per branch. These comparisons show that Gauss-phase information provides a compact strengthening of existing LP relaxations for LCD codes.

For a tournament $T$, let $\omega(T)$ be the minimum clique number among the backedge graphs of $T$, and let $\chi(T)$ be its dichromatic number. We give a template-lifting construction. It turns a $k$-template into a regular, vertex-transitive Cayley tournament that is simultaneously $(k+1)$-$\omega$-critical and $(k+1)$-$\chi$-critical. The output is also a $(k+1)$-template. Iterating the construction, we prove that for every $k\geq3$, there is a positive even integer $m_k$ with the following property. Every $N>1$ with $N\equiv1\pmod{m_k}$ is the order of a regular, vertex-transitive Cayley tournament that is simultaneously $k$-$\omega$-critical and $k$-$\chi$-critical. This proves a conjecture of Aboulker, Aubian, Charbit, and Lopes and gives a negative answer to their bounded-certificate question when the hypothesis is $\omega(T)\geq k$. We also find the clique number of a cyclic substitution when each block satisfies $\omega=\chi$. We then describe exactly when this substitution is $\omega$-critical if the blocks are $\chi$-critical and satisfy $\omega=\chi$.

An influential 1989 result of Naddef shows that the diameters of $0/1$-polytopes are at most their dimension. This was extended shortly after by Kleinschmidt and Onn to any lattice polytope in $[0,k]^{d}$, where they showed a bound of at most $dk$. Naddef's argument easily extends to the monotone setting motivated by the simplex method, where one requires paths to increase with respect to a linear objective function. However, the Kleinschmidt-Onn argument does not. In fact, no argument in the 30 years since has managed to fill that gap. Prior to this work, it remained open whether the monotone diameter is bounded by a polynomial in $d$ and $k$ with no lower bounds suggesting any separation between the worst-case diameter and worst-case monotone diameter. Linear upper bounds hold for $k=1$ and $k=2$. However, we exhibit a sharp threshold for this question at $k = 3$ by constructing for each $d \geq 1$ a lattice polytope in $[0,3]^{6d}$ with monotone diameter at least $2^{d}-1$. In particular, the polynomial bound does not hold. Furthermore, we show that Naddef's result does not extend to the unbounded setting by exhibiting a family of unbounded polyhedra with $0/1$-vertices and diameter exponential in their dimension.

Let $t(n)$ denote the minimum number of transversals in a Latin square of odd order $n$. Improving upon a recent bound of Dai, Divoux and Kelly, we prove that for every $n$ such that $n \equiv 3 \pmod 6$, \[ t(n) \leq \left( \left(1+o(1)\right) \frac{2n}{3e^2}\right)^n . \] Our proof is based on a family of $3 \times 3$ block Latin squares whose transversals are constrained to either lie entirely in the diagonal blocks or avoid them altogether.

We prove an asymptotic Chvátal-type codegree criterion for tight Hamiltonian cycles in $k$-uniform hypergraphs for every fixed $k\ge3$. The criterion allows small degrees to be compensated by large degrees in the link graphs of $(k-2)$-tuples. It strengthens the asymptotic Dirac-type theorem by Rödl, Ruciński and Szemerédi and implies a Pósa-type criterion conjectured by Schülke.

Dunshee and Ellingham recently showed that seven natural properties of a cellularly embedded graph form a Fano-plane framework. We establish an analogous framework for binary delta-matroids. For a binary delta-matroid $D$ and $\tau$, let $Z_3(D,\tau)$ denote its associated binary tight $3$-matroid. The six outer points are represented by evenness or bipartiteness of $D$ and its global vertex-flip transforms. For the seventh point, we call $D$ $Z_3$-bipartite when every circuit of $Z_3(D,\tau)$ has even cardinality. We show that the satisfied properties are precisely the nonzero vectors of a subspace of $\Ftwo^3$. For ribbon-graphic delta-matroids, $Z_3$-bipartiteness is equivalent to bipartiteness of the medial graph, so the construction recovers the Fano-plane framework for embedded graphs.