Papers

We introduce level structures on tropical abelian varieties and give a modular interpretation of $A_g[m]^{\mathrm{trop}}$, the tropicalization of the moduli space $\mathcal{A}_g[m]$ of principally polarized abelian varieties with level $m$ structure. We study the case of abelian surfaces in greater depth. The link of $A_2[m]^{\mathrm{trop}}$ is an explicit simplicial complex whose vertices are the primitive vectors of $(\mathbb{Z}/m\mathbb{Z})^4$ up to sign. As a topological space, this link is homotopic to a wedge sum of closed orientable surfaces and circles; we compute the number of each of these and the genera of the surfaces. We deduce the weight zero compactly supported rational cohomology of $\mathcal{A}_2[m]$, completing a calculation of Oda-Schwermer from 1990.

We study the minimum coefficient degree $N_{k,\F}(G)$ of a Nullstellensatz certificate for Bayer's $k$-coloring equations, where the characteristic of $\F$ does not divide $k$. If $J$ is a \HJ\ join of non-$k$-colorable graphs $G,H$ and $m=\max\{N_{k,\F}(G),N_{k,\F}(H)\}$, then $N_{k,\F}(J)\leq m+k$. When deletion of the selected edge makes each input $k$-colorable, we also have $N_{k,\F}(J)\geq m$; the degree congruence then gives $N_{k,\F}(J)\in\{m,m+k\}$. This partially answers a question of Li, Lowenstein, and Omar. For three-coloring over $\F_2$, we construct an infinite $4$-critical family of exact degree seven, attaining the bound at input degree four. In contrast, every graph constructed from $K_4$ solely by \HJ\ joins has degree $O(\log n)$ and a certificate with polynomially many terms: joins preserve treewidth at most three, and balanced separators yield low-degree certificates. Additional vertex identifications are excluded from this obstruction. We classify all single identifications of the $25$-vertex base graph; exactly $36$ preserve degree seven, producing $24$-vertex $4$-critical graphs of treewidth four. A compressed self-join at adjacent true twins prevents degree loss and gives a repeatable rule adding four vertices per round. The rule does not establish degree amplification or preservation of criticality. Exact witnesses and standalone verification programs accompany the finite results.

We classify the generators of stability-preserving semigroups on polynomial spaces with bounded coordinate degrees. The generators have differential order at most two, with principal coefficients characterized by low-degree nonnegativity conditions. In disk coordinates, positive degree damping gives strict zero-freeness and a sharp spectral gap, extending the Hermitian gap of Bravyi, Gosset, Liu, and Wong to complex generators. The resulting analytic domain yields deterministic classical algorithms for ground energies and stable product-state queries for bounded-degree Suzuki-Fisher Hamiltonians with bounded local strength and fixed positive fields. Field perturbation gives zero-field energy-value approximation schemes for bounded-degree unweighted EPR and bipartite Quantum MaxCut. We also prove that, up to scalars, the Hermitian qubit Hamiltonians whose full Gibbs tensors are Lee-Yang at every temperature in a fixed basis are precisely the edgewise phase-rotated Suzuki-Fisher family. With strictly positive longitudinal fields, these tensors are zero-free on a polydisk of radius greater than one at each positive inverse temperature. These two statements answer questions of Wong, Bravyi, Gosset, and Liu. Degree-preserving, coefficient-positive stability semigroups have concave sector growth rates, yielding token-graph concavity. We also give a counterexample to a proposed explicit ground-state radius.

The binary length function $\ell_2(r,R)$ is the smallest length of a binary linear code with codimension (redundancy) $r$ and covering radius $R$. Let $s_2(N,\rho)$ be the smallest size of a $\rho$-saturating set in the binary projective space $\mathrm{PG}(N,2)$. It is known that the binary length function satisfies $\ell_2(r,R)=s_2(r-1,R-1)$. We obtain the following new upper bounds on $\ell_2(r,R)$, improving the previously known upper bounds by $\Delta(r,R)$: $R=2,r=2t\ge28$, and $r=10,18,20$, $\ell_2(r,2)=s_2(r-1,1)\le51\cdot2^{r/2-5}-1,\Delta(r,2)=2^{r/2-5}$; $R=3,r=3t-1\ge41$ and $r=26$, $\ell_2(r,3)=s_2(r-1,2)\le818\cdot2^{(r-26)/3}-1$, $\Delta(41,3)=63,\Delta(r,3)=2^{(r-26)/3}$ if $r\ge44$. To obtain these bounds, we construct new infinite code families, using distinct versions of the $q^m$-concatenating constructions of covering codes, including new versions proposed in this paper. We also obtain new useful partitions of column sets of parity check matrices of some codes. The new code families provide the asymptotic covering-density bounds $\overline{\mu}(2)\le2601/2048<1.27002$, $\overline{\mu}(3)\le1.35935$, improving the previously known bounds and giving rise to the new upper bounds $f(2)\le2601/2048<1.27002$, $f(3)\le1.35935$ on the constants $f(2),f(3)$ of the Green's Open Problem 40.

We prove that for all $\Delta \geq 2$ and $\gamma > 0$, there exists a constant $C = C(\Delta, \gamma)$ such that for $p\geq C(\log n/n)^{1/\Delta}$, asymptotically almost surely, every spanning subgraph $G$ of $G(n,p)$ with minimum degree at least $(1-1/(2\Delta)+\gamma)pn$ contains every $n$-vertex graph $H$ with maximum degree at most $\Delta$ and with at least $Cp^{-2}$ vertices not in any triangles of $H$. This is a 'sparse local resilience version' of a classical theorem of Sauer and Spencer. The condition that $H$ should contain some vertices not in triangles is necessary, and in fact, the quantity $p^{-2}$ is asymptotically best possible. A key feature of our result is that $H$ is allowed to be an expander graph, distinguishing it from previous results of similar nature, which dealt with, e.g., graphs of sublinear bandwidth. Our proof makes use of regularity arguments, with the sparse blow-up lemma for random graphs being a key tool.

Inspect the vertices of a finite simple graph in uniformly random order, accepting each vertex if none of its neighbors has previously been accepted. Let $X_G$ be the number of accepted vertices. For every triangle-free graph with $n\ge2$ vertices and $e$ edges, we prove $\operatorname{Var}(X_G)\le e((n-2)/n)^2$, with equality precisely for edgeless graphs and connected stars. In particular, among trees of a given order, the star uniquely maximizes the variance, with value $(n-1)(n-2)^2/n^2$. Known expected vertex-deletion stability already yields the elementary baseline $\operatorname{Var}(X_G)\le e$. We obtain the sharp finite-order refinement by combining a stronger centered first-choice estimate with a triangle-free edge-count identity in the law of total variance.

Fox's conjecture famously asserts that the absolute values of the coefficients of the Alexander polynomial of alternating links are trapezoidal. In the setting of MOY graphs, where a different notion of Alexander polynomial appears, the equivalent result to Fox's conjecture is known to hold. In this paper, we relate the two polynomials in the case of special alternating links. More precisely, we show that their degrees, first, and last coefficient agree, and that the MOY polynomial coefficients always dominate the classical Alexander polynomial.

An equilateral set is a set of points in a metric space whose pairwise distances are all equal. Kusner conjectured that the maximum cardinality of an equilateral set in $\mathbb{R}^n$ with the $\ell_p$ metric is $n+1$ for every $1<p<\infty$. We disprove the conjecture for all $p>4$. In particular, for every such $p$, we define $m=m(p)$ and construct an equilateral set of $8m$ points in $\mathbb{R}^{8m-2}$. Previously, Swanepoel disproved the conjecture for $1<p<2$, while Ge, Xu, and Zhou showed that it holds for $2\le p\le 4$. Combining these prior results with the paper's main theorem resolves Kusner's conjecture for all $1<p<\infty$.

In this paper, we introduce and study conformal permutation matrices. In particular, for a permutation $\pi_s\in S_n$, we define the corresponding conformal permutation matrix $H_{\pi_s}$ and show that its $d-$th power, where $d=n/\gcd(s,n)$, is a diagonal block matrix whose blocks are products of certain matrix blocks $h_i$. We further show that these diagonal blocks share a common subset of eigenvalues and prove that $H_{\pi_s}$ is block-diagonalizable. We also introduce the notion of conformal circulant matrix and investigate its eigenvalues. Finally, we establish a necessary and sufficient condition for a rectangular matrix to be conformal circulant.

We prove a dimension-free comparison between the expectation threshold $q(\mathcal F)$ and the fractional expectation threshold $q_f(\mathcal F)$ for any nontrivial increasing family $\mathcal F$ on a finite ground set. Specifically, we show that there is a universal constant $K>0$ such that \[ q_f(\mathcal F)\le Kq(\mathcal F)\max\{1,\log\log(1/q(\mathcal F))\}. \] Combining this comparison with a recent result of Li [arXiv:2609.08967] on the fractional version of Talagrand's discrete Convexity Conjecture, we obtain a dimension-independent bound toward the conjecture.

Finite-dimensional zigzag modules decompose into interval modules. For an ordinary persistence module, every fully supported interval submodule of a restriction splits as a direct summand, whereas this need not hold for a zigzag module. We study this failure of splitting. A breaker pair is a local configuration of two overlapping interval summands with a backward arrow at the left boundary of the second interval and a forward arrow at the right boundary of the first. A single breaker pair gives a local nonsplitting interval submodule, but it need not control a prescribed larger restriction. We therefore introduce breaker chains. Our main result shows that a restriction $V[p,q]$ contains a nonsplitting submodule isomorphic to $I[p,q]$ if and only if its interval decomposition contains a breaker chain spanning $[p,q]$. Equivalently, the proper interval summands $J$ for which $\operatorname{Hom}(I[p,q],J)\ne0$ have supports covering $[p,q]$. This cover formulation gives a constructive description of nonsplitting embeddings, a trichotomy for their splitting behavior, and an $O(m\log m)$ algorithm from an oriented barcode with $m$ intervals.

An oriented graph $H$ is said to be tournament anti-Sidorenko (TAS) if a uniformly random tournament asymptotically maximizes the homomorphism density of $H$ among all tournaments. For an oriented path $P$, a direction flip is a non-leaf source or sink. Sah, Sawhney and Zhao proved that consistently directed paths (paths with no direction flips) are TAS. He, Mani, Nie, Tung and Wei proved that for $3\le k\le 7$, every oriented path of length $k$ with exactly one direction flip is TAS, and Chen, Clemen and Noel recently extended this to every $k\ge 3$. In this paper, we extend these results by proving that for every integer $r\ge 0$, every oriented path of length at least $1665r+1454$ with $r$ direction flips is tournament anti-Sidorenko.

The infinitesimal Stoker conjecture states that an infinitesimal deformation of a convex polytope that preserves all dihedral angles also preserves all normal directions up to isometry. We give a short polyhedral proof, self-contained up to assuming spectral and geometric properties of the Izmestiev matrix.

We prove that the quantum monad in dimension $2n$ admits no natural transformation to the polymorphism clone of linear equations modulo $n$. Consequently, for every $n\geq 2$, there exists an unsatisfiable system of linear equations over $\mathbb{Z}_n$ whose constraint system game admits a perfect finite-dimensional quantum strategy. As a corollary, we completely characterise pseudo-telepathic constraint languages in finite dimension. The proof combines a result of Harding, Jager, and Smith on group-valued measures on subspaces of Hilbert spaces with the polymorphism-minion characterisation of quantum pseudo-telepathy.

Let $G$ be a countable locally finite abelian group, and let \[ G_1\leq G_2\leq\cdots, \qquad \bigcup_{i\geq1}G_i=G, \] be any filtration of $G$ by finite subgroups. For $A\subseteq G$, let $\mathcal P(A)$ denote the set of all finite subset sums of elements of $A$, and let $2G:=\{2g:g\in G\}$. We prove that $|2G|=\infty$ if and only if for every filtration and every interval $[\alpha,\beta]\subseteq[0,1]$, there exists $A\subseteq G$ such that the set of limit points of \[ \left( \frac{|\mathcal P(A)\cap G_i|}{|G_i|} \right)_{i\geq1} \] is exactly $[\alpha,\beta]$. We also prove a positive-density result that does not require $|2G|=\infty$: if $G$ is infinite and $\mathcal P(A)$ has positive upper density along the given filtration, then there is an infinite set $B\subseteq \mathcal P(A)$ such that $B+B\subseteq \mathcal P(A)$. Combining this with the realization theorem, we show that, when $|2G|=\infty$, every interval $[\alpha,\beta]$ with $0\leq\alpha\leq\beta\leq1$ and $\beta>0$ can be realized by a set $A$ with this additional property.

Let $p$ be an odd prime, and write $A\RS B=\{a+b:a\in A,\ b\in B,\ a\ne b\}$. We classify all pairs $A,B\subseteq\Fp$ satisfying $|A|+|B|=p$, $|A|>|B|=\ell\ge1$, and $|A\RS B|=p-2$. After normalizing the two missing sums to $\{0,1\}$, we obtain exactly $\ell+1$ explicit models. The classification forces $B\subseteq A$ and yields, for fixed $p,\ell$, exactly $\binom p2(\ell+1)$ ordered pairs and $1+\lfloor\ell/2\rfloor$ equivalence classes under simultaneous affine transformations. We determine when either set is an arithmetic progression and compute exact difference-set cardinalities. For $\ell\ge3$ and $p\ge4\ell-5$, the cardinality $|B-B|$ determines the equivalence class at fixed $p,\ell$. The proof uses punctured translates and cyclic component counting. We also exhibit a critical pair in $\mathbb F_{13}$, with size gap three and $|A|+|B|=p-2$, that contradicts a proposed inverse statement below the boundary.

Godsil and McKay (1978) showed that the rooted product is a powerful tool for constructing non-isomorphic cospectral pairs of graphs. Despite lacking a convenient tensor product structure, we show that the rooted product is useful for constructing graphs with good quantum state transfer properties. In particular, we prove a simple transference principle: if a graph $X$ has quantum state transfer and $Y$ is a controllable graph, their rooted product $X^Y$ has quantum state transfer (inherited from $X$). This complements a folklore property of Cartesian product which preserves perfect state transfer. However, the rooted product is a significantly sparser graph and, more importantly, can be easily used to construct efficient high-fidelity state transfer even if $X$ has no quantum state transfer. Our proof exploits the fact that a rooted product creates a large number of strongly cospectral pairs of vertices and that its condition number can be controlled by its pendant subgraph.

We study how far a fixed Ramsey upper bound can be improved by descending through blue neighborhoods in one vertex set while keeping a second set fixed. A weighted inequality in the two set sizes determines when the descent can stop. For the source bound specified here, the infimum diagonal exponent over all finite derivations lies in $[1.305,\,1.307]$. A finite derivation gives $R(k,k)\le3.69507^k$ for all sufficiently large $k$; a concave polygon proves the lower bound for every finite depth. We also characterize the infimum as a greatest fixed point and show that every larger exponent has a finite derivation valid uniformly for nearby clique-size ratios.

We classify all smallest sets of edge deletions that destroy every nonnested perfect matching in a complete ordered graph. The vertices have a fixed linear order. A perfect matching selects edges that use each vertex exactly once; it is nonnested when no selected edge has both endpoints strictly between those of another. On $2k$ vertices, exactly $k$ deletions are necessary, and we describe all $2^k+k-2$ minimum deletion sets for every $k\ge2$. Allowing a matching to leave vertices unused changes the extremal problem. Barát, Freschi and Tóth proposed that an $n$-vertex ordered graph avoiding a nonnested $k$-edge matching can have at most $(k-1)n$ edges. We construct counterexamples for every $k\ge5$ and $n\ge2k+1$. For $n\ge3k$, our constructions exceed the proposed value by a number of edges proportional to $k^2$, matching the order of the known upper bound on this excess. The classification follows from cuts between consecutive intervals; the larger constructions coordinate deletions at the two ends of the vertex order. The exact extremal value remains open in general.

The minimum distance and the covering radius are two fundamental properties of the code. Both have been extended: the former to the generalized Hamming weights hierarchy, and the latter to the generalized covering radii hierarchy. In both cases, the lowest level of the hierarchies corresponds to the classical minimum distance and covering radius, respectively. From a geometric point of view, the minimum distance of the code determines the packing radius, which is upper bounded by the covering radius. It was conjectured this relation extends to all other orders of the hierarchy, namely, that the generalized packing radii are upper bounded by the generalized covering radii of the same order. In this paper we prove this conjecture is true for the second order radii. We also prove the conjecture holds for all orders when the code rate is at most $3/5$. Finally, we show that for any code rate in $(0,1)$, for all sufficiently long codes the conjecture holds for all orders.

Assume the Generalised Riemann Hypothesis. If $A\subseteq \{1,...,N\}$ contains no two elements differing by $p+1$, $p$ prime, then $|A|\ll N^{\frac{89}{90} + o(1)}$.

We prove the Erdős–Chvátal simplex conjecture across its entire parameter range. If $2\le d<k$ and $(d+1)k\le dv$, then every $d$-simplex-free family of $k$-subsets of $[v]$ has at most $\binom{v-1}{k-1}$ members, with equality only for a full star.

Two families $\mathcal{F},\mathcal{G}\subseteq S_n$ are cross $t$-intersecting if every $\sigma\in\mathcal{F}$ and $\tau\in\mathcal{G}$ agree on at least $t$ points. A $t$-coset is a coset of the stabilizer of $t$ points. A subset of $S_n$ is non-trivial if it is not contained in any $t$-coset. Let $d_m$ denote the $m$-th derangement number. We prove that, for all $t\geq1$ and $n\geq400t$, every pair of cross $t$-intersecting families $\mathcal{F},\mathcal{G}\subseteq S_n$ satisfies the following: (i) $|\mathcal{F}||\mathcal{G}|\leq((n-t)!-d_{n-t}-d_{n-t-1})((n-t)!+t)$ if $\mathcal{F}\cup\mathcal{G}$ is non-trivial. (ii) $|\mathcal{F}||\mathcal{G}|\leq((n-t)!-d_{n-t}-d_{n-t-1}+t)^2$ if both $\mathcal{F}$ and $\mathcal{G}$ are non-trivial. (iii) $\min\{|\mathcal{F}\setminus\mathcal{C}|,|\mathcal{G}\setminus\mathcal{C}|\}\leq t((n-t-1)!-(n-t-2)!)$ for some $t$-coset $\mathcal{C}$ if $t\geq2$. We also characterize all extremal configurations. The first result extends a theorem of Ellis (2011) to an exponentially wider range and sharpens the stability theorem of Keller, Lifshitz, Minzer and Sheinfeld (2024); the second gives a product version of the classical Hilton–Milner–Frankl theorem for permutations; and the third settles the remaining cases $t\geq2$ of a conjecture of Ellis (2011) in a stronger form. In all three results, the linear dependence on $t$ is essentially optimal. Our proofs are based on the spread approximation method introduced by Kupavskii and Zakharov and on an approach to cross $t$-intersection problems developed by the present authors, with several essential refinements. As an application of our approach, we prove a product version of the Hilton–Milner–Frankl theorem for the alternating group.

We establish Jacobi-type continued fraction expansions for (p,q)-analogues of the bi-Stirling Eulerian polynomials, which refine classical Eulerian statistics on permutations. These polynomials admit equivalent definitions in terms of descents or excedances. The parameters p and q encode refined permutation statistics, including (ldes,rasc) and (cros,nest). Our approach is based on weighted Motzkin path models arising from variants of the bijections of Françon–Viennot and Foata–Zeilberger. As applications, we obtain new results on total positivity and gamma-positivity for several families of enumerative polynomials. Our results unify and extend a number of recent works in the literature.

We introduce a new type of boundary condition for electrical networks by specifying a cohomology class on the underlying cell complex. As special and limiting cases, we recover the Dirichlet boundary condition, multiport condition, and prescribed voltage drops along nontrivial cycles on a surface. In this setting, we obtain a combinatorial formula for minors of the response matrix, generalizing the matrix-tree theorem, the Kenyon-Wilson formula, and a recently discovered formula for networks on surfaces due to Lam et al. To prove this formula, we develop a statistical-physics toolbox, including a new parafermionic observable for the uniform spanning tree model. This is the first parafermionic observable that is intrinsic, in the sense that it does not require an embedding of the graph in the plane or on a surface. Other ingredients are an intrinsic Temperley correspondence and source-synchronized networks, the latter providing a completely elementary reformulation of our results.

A digraph $F$ is avoidable if, for every positive integer $k$, there exists an integer $d$ such that every digraph of minimum out-degree at least $d$ contains an $F$-free subdigraph of minimum out-degree at least $k$. We prove that no digraph admitting a height function is avoidable, where a height function increases by one along every arc. This answers a question of Christoph, Janzer, Petrova, and Steiner and, together with an additional avoidance argument, determines which orientations of $C_4$ are avoidable. Motivated by a further question of Christoph, Janzer, Petrova, and Steiner, we also study Eulerian avoidability, in which the host digraph is required to have equal in-degree and out-degree at every vertex. We show that no one-directed complete bipartite digraph with nonempty parts is Eulerian-avoidable. In contrast, the orientation of $C_4$ consisting of two directed paths of length two with common endpoints is Eulerian-avoidable. Consequently, the one-directed complete bipartite orientation is the only orientation of $C_4$ that is not Eulerian-avoidable, completing the classification of $C_4$-orientations.

We give a finite cover argument for nonnegativity of the ordinary monomial coefficients of every stretched Littlewood-Richardson polynomial with partition lengths at most seven and outer size at most thirty. Explicit reductions leave 358,952 residual triples. The computational part consists of exact finite enumeration, local reduction checks and rational Ehrhart polynomial computations. Its three named dependencies are stated precisely below, separately from the mathematical implication they establish.

For a finite simple graph $G$ of positive order, let $s_k(G)$ be the number of its $k$-vertex tree subgraphs. We prove that, among graphs of a fixed order $n$, the ratios $s_k(G)/s_k(K_n)$ form a nonincreasing sequence in $k$. It follows that the complete graph maximizes the mean subtree order: $\mu(G)\leq\mu(K_n)$, with equality if and only if $G$ is complete. This monotonicity theorem also establishes the $s_{n-1}$-to-$s_n$ ratio conjecture posed in recent work on extremal mean subtree order. The proof lifts a known coupling of rooted Cayley-tree shapes of consecutive orders to uniform labeled tree subgraphs of $K_n$ that are nested at every sample point. Event inclusion gives the count inequalities, and a double-sum identity gives the mean bound.

We prove the Colomo-Pronko conjecture for alternating sign matrices with a prescribed square of zeros at a corner, for all matrix sizes and freezing parameters. A known multiple-integral formula for the frozen-corner count yields determinant representations built from fixed polynomial kernels. We relate these kernels to the conjectured determinant through an inverse identity for the commutator of a signed Pascal matrix with reversal. In odd dimension, the comparison uses the one-dimensional nullspace and projection along it to eliminate the central coordinate. Combined with the asymptotic analysis of Colomo and Pronko, our result removes the conjectural assumption from their GUE Tracy-Widom fluctuation theorem for the intersection of the frozen boundary with the main diagonal in uniformly random alternating sign matrices. The finite-dimensional algebraic core of the proof has been formalized in Lean 4.

For a set $W$ of nonempty words, let $S(W)$ be the flat semiring formed by the nonempty factors of words in $W$, together with an absorbing zero. We prove that $S(W)$ has a finite identity basis whenever every word in $W$ is linear, with no restriction on the size of $W$ or on the lengths of its words. In the bounded case its variety is generated by the interval semiring $A_m\cong S(a_1\cdots a_m)$, where $m$ is the maximum word length and the letters $a_i$ are distinct. In the unbounded case its variety is generated by the interval semiring on all finite intervals of the nonnegative integers. We give explicit finite bases in both cases. The proofs encode nonzero polynomial evaluations by endpoint graphs and derive the required graph identifications using finitely many splicing identities. In particular, the eleven-element semiring $S(abcd)$ is finitely based, providing a counterexample to the length-bound conjectures for $S(W)$ proposed by Gao, Ren and Zhao.