Papers

We study continuous-time quantum walks (CTQWs) on cycles. In particular, we prove that the cycle $C_9$ does not admit uniform mixing at any time via algebraic geometry and Gröbner basis techniques to rule out all cyclic 9-roots.

Motivated by Erdős's conjecture on the Turán number of degenerate bipartite graphs, Bradač, Janzer, Sudakov and Tomon proved that $ \ex(n,T \Box P)=\Theta_{T,P}(n^{3/2})$ for every nontrivial tree $T$ and every nontrivial path $P$, and conjectured that the same order of magnitude holds for the Cartesian product of any two nontrivial trees. We prove their conjecture. More generally, for every integer $r\ge2$, we introduce a class of bipartite $r$-degenerate graphs, called $r$-star-flip graphs, that are obtained from a seed tree by a sequence of local vertex-duplication operations. We prove that every fixed $r$-star-flip graph $H$ satisfies $\ex(n,H)=O_H(n^{2-1/r})$. Every Cartesian product of two trees is a $2$-star-flip graph, while the star-flip class also contains graphs that do not arise as such products. As a further application, our framework yields a new proof of Füredi's theorem: if $H$ is a fixed bipartite graph in which at most one vertex in one colour class has degree greater than $r$, then $\ex(n,H)=O_H(n^{2-1/r})$. The key ingredient is a conditional-resampling procedure that extends the tree branching random walk on the seed tree to a random homomorphism of the entire star-flip graph, while preserving the branching-random-walk distribution on every live tree.

In many applications, graphs are observed repeatedly, where the task is to observe and track weak localized structural perturbations under noise, such as vertex-coordinate displacements or edge-weight/attribute changes on a fixed vertex set. One-shot graph distances can miss these localized perturbations or fluctuate too strongly to support reliable monitoring, especially in large graphs where signal dilutes with scale. We propose Robust Order-aware Spectral Amplification (ROSA), a distance-amplification operator that integrates metric evaluations along an order-aware edge-removal filtration. We prove that ROSA cannot reduce the included base distance and conditionally increases it whenever a filtered step exposes additional signal; separately, we prove that it can strictly improve an inverse coefficient of variation stability score (IS$^2$), defined as the mean of a noisy graph distance divided by its standard deviation, under an explicit sufficient condition that can be checked empirically. Experiments on synthetic graphs with localized edits under three noise models, varying graph densities, and three algorithmically selected edit sites show that ROSA can often approximately double the IS$^2$ of the base spectral distance. We show where ROSA works and stops working on real-world use cases including mitochondrial networks, fMRI correlation matrices, tissue networks, protein conformer graphs, and retinal vasculature multiplex graphs. The empirical results across graph, operator, and noise settings are consistent with the theoretical amplification conditions and boundary constructions. Evaluated with empirically estimated operative quantities, the bound agrees with the observed gain in direction and approximate scale.

Let $k>t\ge 1$ be integers and set $d=k-t$. A $k$-uniform hypergraph $\mathcal F$ is called $t$-intersecting if any two edges intersect in at least $t$ vertices, and is called $t$-critical if its minimum $t$-transversal has size $k$. Frankl proved that, for $k\ge d^4$,$|\mathcal F|\le \binom{k+d}{d},$ with equality only for the complete $k$-graph on $k+d$ vertices, and conjectured that the same conclusion should hold when $k>c d^2$ for some constant $c$. In this paper we confirm this conjecture for $c=30$. The proof relies on Frankl's fixed-edge decomposition and Füredi's pseudo-sunflower method.

The chromatic threshold, originating in a question of Erdős and Simonovits, asks when a linear minimum-degree condition forces bounded chromatic number in H-free graphs. Motivated by a question of Thomassen, the homomorphism threshold asks for the stronger conclusion that every such graph admits a homomorphism to an H-free graph of bounded order. Since the work of Goddard and Lyle determined the clique case, exact homomorphism thresholds for individual non-complete forbidden graphs have remained unknown. In this paper, we extend the clique case to a larger family of forbidden graphs, determining the homomorphism threshold exactly for every graph in this family.

Let $\mathbf{x}_{n \times n}$ be an $n \times n$ matrix of variables and let $S = \mathbb{F}[\mathbf{x}_{n \times n}]$ be the polynomial ring over these variables where $\mathbb{F}$ is a field of characteristic zero. Regard $S$ as the coordinate ring of the affine space $\mathbb{F}^{n \times n}$ of $n \times n$ $\mathbb{F}$-matrices. Let $\mathfrak{D}_n \subseteq \mathbb{F}^{n \times n}$ be the locus of derangement permutation matrices. We study the orbit harmonics quotient ring ${\bf R}(\mathfrak{D}_n) = S/\mathrm{gr} \, \mathbf{I}(\mathfrak{D}_n)$ where $\mathrm{gr} \, \mathbf{I}(\mathfrak{D}_n)$ is the associated graded ideal of the vanishing ideal $\mathbf{I}(\mathfrak{D}_n) \subseteq S$. We give an explicit generating set of $\mathrm{gr} \, \mathbf{I}(\mathfrak{D}_n),$ relate the Hilbert series of $\mathbf{R}(\mathfrak{D}_n)$ to the Foata transformation and the longest increasing subsequence statistic on $\mathfrak{S}_n$, and give an alternating sum formula for the graded $\mathfrak{S}_n$-character of $\mathbf{R}(\mathfrak{D}_n)$. Our proofs make heavy use of the mapping cone construction of homological algebra.

The weight distribution bound gives a lower bound on the weight of eigenvectors for eigenvalues of distance-regular graphs. In this note, we study when the weight distribution bound is tight for the negative eigenvalue of collinearity graphs of finite embedded polar spaces, and elliptic and hyperbolic affine polar graphs. We give a complete classification of eigenvectors meeting the weight distribution bound.

The Bier sphere of a simplicial complex $K$ is defined as the deleted join of $K$ and its combinatorial Alexander dual. We focus on the class of Bier spheres of the skeleta of a simplex. Since these Bier spheres are known to be polytopal, they give rise to small covers. We classify small covers over these Bier spheres up to Davis–Januszkiewicz equivalence. As applications, for all $m \geq 4$, we determine the homeomorphism types of small covers over the Bier spheres of the $0$-skeleton and the $(m-3)$-skeleton of an $(m-1)$-simplex. For the remaining cases $0<r<m-3$, we compute their rational Betti numbers.

The game of Hex is one of the most celebrated connection games in combinatorics. Although it is known that the first player always has a winning strategy, very little is understood about the complexity of optimal play. Following Campbell's introduction of the parameters $\lambda(n)$ and $\delta(n)$, measuring respectively the length of the shortest guaranteed winning path and the minimum number of stones required by the first player to force a win, we establish new structural properties of these quantities. Our main result determines the exact value \[ \lambda(5)=7, \] thereby confirming one of Campbell's conjectures. We also show that the corresponding problem on the infinite strip $5\times\infty$ has a markedly different behavior. In this setting we prove that \[ \lambda(5\times\infty)=5, \] which is strictly smaller than $\lambda(5)$. To the best of our knowledge, this paper provides the first solution to one of Campbell's 2004 conjectures and answers a question posed by Stromquist (2006) in the affirmative. Furthermore, it uncovers a fundamental distinction between finite and infinite boards, offering new insights into the nature of optimal winning strategies in Hex.

We prove that every polylogarithmically dense subset of $[N]$ contains a nontrivial configuration $x+b_1m,\ldots,x+b_km$ for almost all choices of the coefficient vector $(b_1,\ldots, b_k)$ in a wide range of scales. We prove the same statement for polylogarithmically relatively dense subsets of the primes, in a shorter range of scales. The main ingredients are a new quantitative generalised von Neumann theorem, degree lowering to the $U^{1+}$ norm, and densification arguments that transfer the result to the primes.

Let $F$ denote the Fano plane, the $3$-uniform hypergraph with $7$ vertices and $7$ edges. Frankl and Füredi, and independently Keevash and Sudakov, proved that the largest $F$-free subhypergraph of $K_n^{(3)}$ is bipartite. In this paper, we determine the sharp threshold for this property in the random setting. We show that for $\hat{p} = \Theta_F \cdot n^{-2/3} \left(\log n\right)^{1/6}$, where $\Theta_F$ is an explicit constant depending on $F$, we have: (i) if $(1+\epsilon) \hat{p} \le p = o(1)$, then with high probability every largest $F$-free subhypergraph of $G_{n,p}^{(3)}$ is bipartite; and (ii) if $\frac{1}{n^2} \ll p \le (1-\epsilon) \hat{p}$, then with high probability every largest $F$-free subhypergraph of $G_{n,p}^{(3)}$ is not bipartite. To the best of our knowledge, this work provides the first sharp threshold result obtained for a Turán-type problem in random hypergraphs.

In 2012, Kaufman and Lubotzky constructed the first family of symmetric LDPC good codes. Their construction used Cayley codes, as originally defined by Kaufman and Wigderson (2016). In this paper we present two generalisations to the Cayley code construction, which we call graph codes and digraph codes. We investigate both the algebraic, and combinatorial properties of these constructions and show that they possess the same desirable attributes as Cayley codes, but with added freedom. We analyse the relationship between the expansion properties of the ingredient (di)graphs and the parameters of the constructed codes; our analysis offers an improvement to the results of Kaufman and Lubotzky. As an application, we construct an infinite family of good digraph codes, and we propose a series of open problems.

We investigate Full Support (FS), a Partizan Subtraction game in which the players can remove any number of pebbles from the heap up to certain bounds that are typically different for Left and Right. The player with the richer move set always wins for all but finitely many heap sizes. We confirm this advantage by finding the general canonical form and the atomic weights of this game. To restore fairness (and peace), we introduce Truncated Support (TS), which essentially trims the larger subtraction set from below. If the truncation is shallow, the unfairness persists above a certain heap size, and one player continues ruling. If the truncation is deep, another player starts ruling. Interestingly, there is one more balanced truncation level in the middle, for which a non-trivial periodicity emerges, and where it has infinitely many $\mathcal P$ and $\mathcal N$-positions. We also explore the atomic weights for the lightly trimmed scenarios.

For an $n$-vertex graph $G$, let $N(H_3,G)$ be the number of injective labeled copies of the red-blue path $H_3$ for which the two blue pairs are mapped to non-edges of $G$ and the red pair is mapped to an edge of $G$. We determine the maximum limiting value of $N(H_3,G)/n^4$ and give an extremal construction, which is the disjoint union of a clique and an asymptotically regular graph. The proof uses weighted vertex quotients and degree-square tie-breaking. We thereby resolve the exceptional four-vertex case left open in the recent classification of non-complete red-blue graphs.

A binary operation $\cdot$ which satisfies the identity $(x \cdot y) \cdot x = y$ is called a semisymmetric quasigroup. We show that the nucleus of a semisymmetric quasigroup is either empty or an elementary abelian 2-group coinciding with the centre, and that a semisymmetric quasigroup with a non-empty nucleus is necessarily a Mendelsohn loop, i.e. the loop associated with a Mendelsohn triple system. We derive necessary and sufficient conditions for the existence of a semisymmetric quasigroup of order $n$ with nucleus of order $m$. Furthermore, we characterize the nuclear elements of a Mendelsohn loop in terms of a particular orientation of the Pasch configuration in the associated triple system.

Let $F$ be an $r$-vertex graph. In this paper, we study the $F$-factor problem in random induced subgraphs of dense graphs. We show that for any $r$-vertex graph $F$ and $\gamma>0$, if $H$ is an $n$-vertex graph with minimum degree at least $(1-1/\chi_{cr}(F)+\gamma)n$, then for every fixed $p \in (0,1)$, the random induced subgraph $H[p]$ contains an $F$-factor with probability at least $1/(rq)-o_n(1)$, where $q\in \mathbb{N}$ is the order of certain coset group defined from $H$. The probability is asymptotically best possible for infinitely many $F$ and $H$ and yields that a $1/(rq)-o_n(1)$ proportion of the subsets of $H$ induce $F$-factors, interestingly, regardless of whether $H$ itself admits an $F$-factor. Similar results are obtained for perfect matchings in hypergraphs under minimum degree conditions. Our proof combines concentration inequalities, lattice point counting in $\mathbb{Z}^d$ and structural theorems for $F$-factors in dense (hyper)graphs.

We give a recursive reformulation and extension of the independent set of size $134753$ in $C_7^{10}$ constructed by N. Itty, C. D. Rosin, C. Carstensen, and D. Reichman (arXiv:2607.21517v1). We prove a product lemma that combines gadgets of different dimensions while preserving the required independence conditions. Starting from the size-$367$ independent set in $C_7^5$ of S. C. Polak and A. Schrijver (Information Processing Letters 143 (2019), 37-40), the construction gives an explicitly specified independent set in $C_7^{200}$. Consequently, \[ \Theta(C_7)\geq 3.2587891539086910161967650155\ldots . \] An accompanying program verifies the finite assertions about the five-dimensional base gadget and performs the exact integer computations used in the recursion.

A hole in a graph is an induced cycle of length at least $4$. A cap is a hole together with a vertex adjacent to exactly two consecutive vertices of it. Chen, Xu and Xu conjectured that if $q\ge2$ and $G$ is a $(\mathrm{cap},\mathrm{even\ hole})$-free graph with no odd hole of length at most $2q-1$, then $\chi(G)\le \left\lceil \frac{2q+1}{2q}\omega(G)\right\rceil.$ They confirmed the conjecture for $q \le 3$. In this paper, we prove the conjecture for all $q \ge 3$. As a corollary, we prove that for such a graph $G$, $\chi_f(G)\le \frac{2q+1}{2q}\omega(G).$

Let $g(n,k)$ be the maximum number of distinct sizes of maximal cliques in an $n$-vertex $k$-uniform hypergraph, and let $f(n,k)=n-g(n,k)$. We determine the asymptotic order of $f(n,k)$ for every fixed integer $k\ge 3$. Define $L_2(x)=\max\{2,\log_2(\max\{1,x\})\}$, and, for $j\ge 3$, let $L_j(x)$ be the least number of iterations of $L_{j-1}$ needed to reach a value at most $16$. We prove that $$ f(n,k)=\Theta_k(L_k(n)).$$ In particular, $f(n,3)=\Theta(\log^{*}n)$, where $\log^{*}n$ denotes the iterated logarithm. We also determine the asymptotic behaviour of the layered-tree threshold $c(n,k)$ arising from Gao's insertion-tree method: $$ c(n,k)=\log_2 L_k(n)+O_k(1). $$ Consequently, $f(n,k)=\Theta_k\!\left(2^{c(n,k)}\right)$. Our result gives a negative answer to Gao's question in the case $k=3$.

A connected graph G is said to be a bisplit graph if the vertex set of G can be partitioned into a stable set and a complete bipartite graph. We establish the following dichotomy with chordality being the parameter; for chordal bisplit graphs, Hamiltonian cycle (HCYCLE) and Hamiltonian path (HPATH) problems are polynomial-time solvable, and for chordal bipartite bisplit graphs, HCYCLE (HPATH) is NP-complete. We further strengthen the result of [1] and show that HCYCLE (HPATH) is polynomial-time solvable on P5-free chordal bipartite graphs (bipartite chain graphs) and NP-complete on P10-free chordal bipartite graphs. By using our polynomial results on HCYCLE (HPATH) as a framework, we solve many variants and generalizations of HCYCLE (HPATH), which are also reported in this paper.

We show that some classical identities valid for ordinary partitions have precise analogues for $n$-color partitions, that is partitions in which a part of size $n\geq 1$ can occur in colors $1, 2, \ldots, n$. For $r \ge 2$ and $j \ge 0$, we write $\mathcal{O}_{j,r}(m)$ and $\mathcal{D}_{j,r}(m)$ for the sets of $n$-color partitions of $m$ with, respectively, exactly $j$ different parts whose size and color are divisible by $r$, and exactly $j$ different parts occurring at least $r$ times. We prove an $n$-color version of Franklin's theorem, $|\mathcal{O}_{j,r}(m)| = |\mathcal{D}_{j,r}(m)|$, along with two Beck-type identities. We give both analytic and combinatorial proofs for all theorems.

Let $\Gamma_n(q)$ be the graph whose vertices are the invertible matrices in $\Mat_n(\F_q)$, with two distinct matrices adjacent whenever their sum is singular. A dissociation set is a vertex set inducing a graph of maximum degree at most one. We study the dissociation number of $\Gamma_n(q)$ by embedding it as an induced subgraph of the total graph $T_n(q)$ on all of $\Mat_n(\F_q)$. A general Laplacian inequality for $k$-independent sets, together with an explicit character computation for the additive group of the matrix ring, gives parity-sensitive upper bounds. For fixed $n$, the resulting bound is of order at most $q^{n^2-n+1}$ for odd $q$ and at most $q^{n^2-2n+2}$ for even $q$. In particular, \[ \diss(\Gamma_n(q))\le q^{n^2-n+1}-1. \] In the other direction, the regular representation of the extension field $\F_{q^n}$ gives $\diss(\Gamma_n(q))\ge q^n-1$. We give complete proofs, including a self-contained derivation of the required matrix character sum, and determine the smallest case: $\diss(\Gamma_2(2))=3$.

We introduce and study two partition-indexed families of quasimodular forms obtained from Schur functions: Schur Eisenstein series and Schur MacMahon series. An explicit transition between them can be interpreted as a convolution in a Faà di Bruno Hopf algebra of symmetric functions. We discuss the classical sl2-action and prove that Schur Eisenstein series for partitions with parts of size at most 3 give a basis for quasimodular forms. Further, we conjecture that the Schur MacMahon series span all quasimodular forms with integral coefficients.

We show that every planar graph has a tree-decomposition with optimal width such that the subgraph induced by each bag has pathwidth at most 3. This bound is best possible, and for tree-decompositions that satisfy a certain minimality condition, we in fact give a precise description of the possible structures in each bag. Moreover, we show that the union of any $k$ bags has pathwidth $O(k)$. We also show that graphs excluding a fixed double-apex-forest minor have a tree-decomposition with optimal width such that the subgraph induced by each bag has bounded pathwidth. This includes graphs embeddable on any fixed surface. As a byproduct of our machinery, we give a new proof of the linear grid minor theorem for planar graphs.

We show that for a $2$-connected graph $G$ which is not a cycle, the mixed metric dimension of $G$ is at most $2c(G)$, where $c(G)$ is the cyclomatic number of $G$. As an immediate application, we prove a conjecture proposed by Sedlar and Škrekovski (2021).

We prove that the full spectrum of the graph $p$-Laplacian is finite for every finite graph and every real $p>1$. This resolves the problem of finiteness of the full graph spectrum posed by Amghibech (2003). More generally, for signed weighted graph $p$-Schrödinger operators with arbitrary real potentials, we obtain bounds in terms of the numbers of vertices and positive-weight edges, uniform in all coefficients and in $p$. On $n$ vertices with $m$ positive-weight edges, the logarithms of the spectral cardinality and of the total number of connected components of the normalised eigenvector sets are $O((n+m)^2)$; the sum over the full spectrum of their rational Betti numbers is at most $\exp(C(n+m)^2)$ for an absolute constant $C$. These topological bounds extend to homogeneous eigenproblems built from arbitrary finite families of linear forms, including generalised $p$-eigenvalue problems for matrix pairs. For the uniformly weighted $K_n$ and $p\ne2$, we identify the nonconstant eigenlines with the barycentres of the coordinate-hyperplane cell decomposition of $\mathbb RP^{n-2}$ and determine their local Morse data on either side of $p=2$. A renormalised logarithmic limit describes the transition at $p=2$. Positive integer weights then separate these critical values, giving at least $(3^n-2^{n+1}+3)/2$ distinct spectral values for every fixed $p\ne2$ and every $n\geq2$. By contrast, the maximal spectral cardinality at $p=2$ is $n$; at $p=4$, the maximal spectral cardinalities in the unsigned and general classes both have exponential growth rate exactly $3$. For $n\geq3$ the same examples resolve Amghibech's extremal question. The proof combines o-minimal and Pfaffian geometry with projective $L^p$-duality, Morse theory, critical groups, and tensor eigenvalue bounds.

For $x\ge1$, let $G_3(x)$ be the maximum sum of the side lengths of three pairwise interior-disjoint, arbitrarily rotated squares contained in a $1\times x$ rectangle. We determine this function exactly: $G_3(x)=x+\tfrac12$ for $1\le x\le\tfrac32$, $G_3(x)=2$ for $\tfrac32\le x\le2$, $G_3(x)=x$ for $2\le x\le3$, and $G_3(x)=3$ for $x\ge3$. This completes the $n=3$ case of the rectangular square-packing question posed by Richard Stanley in a 2021 MathOverflow comment. The values for $\tfrac32\le x\le3$ follow from a strip theorem stating that three squares in $[0,1]\times[0,H]$, $H\ge2$, have total side length at most $H$. For $x\ge3$, the formula is immediate because each square has side length at most $1$. The range $1\le x\le\tfrac32$ is handled by combining the two-square theorem with an additional semi-perimeter estimate for a triangle whose two nonhorizontal sides have opposite slopes. In particular, the special case $x=2$ answers the question asked in the MathOverflow post. In connection with Erdős problem #106, we also prove that every five-square packing in the unit square with an axis-parallel guillotine cut has total side length at most $2$.

Consider read-once polynomial functions over a finite field of order $k$, i.e., functions defined by expressions built from field addition, multiplication, and constants, in which every variable occurs at most once. Let $p=(p_1,\dots,p_k)$ be the distribution of the values of a read-once function on independent uniform inputs. We prove that for every $k\ge4$ all such distributions belong to a body $\mathcal{B}_k$, defined by the following relation on the sorted atoms $p_1^\downarrow\geq\cdots\geq p_k^\downarrow$ of the distribution: \[ \mathcal{B}_k=\left\{p:p_k^\downarrow\ge \frac{1-p_2^\downarrow-(1-p_2^\downarrow)^k}{k-1}\right\}, \] or equivalently, $\mathcal{B}_k = \{ p \colon 1-p_2^\downarrow-(k-1)p_k^\downarrow\le(1-p_2^\downarrow)^k\}$. Our main theorem is that this body is stable under the convolutions corresponding to both field operations. More generally, convolution for any quasigroup operation on $k$ points preserves $\mathcal{B}_k$; the multiplicative conclusion needs only an absorbing zero and a quasigroup operation on the nonzero elements. The body is full-dimensional and contains the uniform law and every point mass; its normalized volume is given by an exact one-dimensional integral, and the $k$th root of that volume tends to $0.2183305369\ldots$. The complete development, including the two stability theorems, the exact volume formula, and its sharp exponential rate, has been formalized in Lean 4.

We extend the vertex polynomial to graphs of arbitrary degree and prove local relations that hold when a graph contains a digon, triangle, quadrilateral or pentagon.

WOW-284 asserts that the minimum dual degree of every connected graph of order at least three and girth at least five does not exceed the negative of its least distance eigenvalue. We refute it with exact counterexamples of orders $38,39,40,42$, and $50$, and develop a structural theory of the failure. For a connected $k$-regular graph of girth at least five and diameter three, we prove $\delta^*(G)+\lambda_{\min}(D(G))=2k-2-\max_{\theta\ne k}(\theta+1)^2$. Here $\theta$ ranges over the nonprincipal adjacency eigenvalues. We further prove that every regular strict counterexample has degree at least six and diameter at most four, while diameter four forces degree at least ten. We solve the associated one-variable nonbacktracking linear program exactly, including optimizer rigidity. For regular strict counterexamples of diameter three, the optimizer yields a positive-semidefinite slack matrix whose integral excess gives the stronger bound $|V(G)|\le\left\lfloor 3(k+2)^2(k^2+3)/(18k+41)\right\rfloor$; this follows from a three-to-one quantization theorem for the integral excess. The slack matrix's principal minors also recover local cycle constraints. In particular, regular degree-six counterexamples have order at most $50$, and at the degree-six, order-$50$ boundary the associated signed complement is necessarily disconnected. We determine the distance spectra of one- and two-vertex punctures of Moore graphs and establish a uniform deletion-stability bound: every deletion of at most five vertices from the Hoffman–Singleton graph remains a strict counterexample, whereas an explicit six-vertex deletion does not. All theorem-level computations use exact arithmetic. Lean 4.31 kernel-checks the explicit $50$-vertex Hoffman–Singleton counterexample at graph level, finite spectral certificates at orders $38,39,40,42$, and the analytic LP optimum and rigidity for every integer $k\ge4$.