Combinatorics
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Wednesday 12 August
We introduce a natural generalization of the Bell numbers: the $m$-Bell numbers $B^{(m)}_{n}$, characterized by the property that $m$ applications of the binomial transform reproduce the original sequence shifted $m$ places to the left. Their exponential generating functions satisfy $m$-th order ordinary differential equations whose solutions are hypergeometric (hyper-Bessel) functions, specializing to the exponential function when $m=1$ (classical Bell numbers) and to modified Bessel functions when $m=2$ (yielding "Bessel-Bell" numbers). Mirroring the Bell-Stirling correspondence, we construct $m$-Stirling triangular arrays from the two-term recurrence $S_m (n+1,k) = m \left\lfloor k/m \right\rfloor S_m(n,k)+S_m(n,k-1)$ and prove an elementary shift identity from which the central structure theorem follows: the row sums of the $m$-Stirling triangle reproduce $B^{(m)}_{n}$, and, more finely, the residue-class row sums are precisely the $m$ primitive $m$-Bell sequences. The $m$-Stirling numbers come in dual pairs (with first-kind partners, generalized falling factorials, and Lah-type companions), serve as conversion operators between polynomial bases, admit Dobiński-like formulas, and count congruence-constrained partitions in an urn model as well as restricted permutation insertion histories. Finally, we show that the $m$-Bell numbers govern the moments of the Conway-Maxwell-Poisson distribution with integer dispersion parameter $\nu=m$: the scaled moments are combinations of fixed hyper-Bessel carrier ratios whose integer coefficients are precisely the primitive $m$-Bell sequences, recovering for $m=1$ the classical fact that the moments of the Poisson distribution are the Bell numbers.
Combinatorics · Cross-listed from quant-ph
Perfect State Transfer on Oriented Circulant Graphs: A Complete Classification
The continuous-time quantum walk on an oriented circulant graph is determined by the Fourier eigenvalues of its Hermitian adjacency matrix. We classify perfect state transfer (PST) between distinct vertices in every nonempty oriented circulant graph. We show that each such graph is described by an odd primitive quadratic Dirichlet character of conductor $\Delta$, a set of gcd-classes, and a choice between the two orientations of each selected class. For a graph of order $n$, we derive an explicit formula for every Fourier eigenvalue without assuming that $n/\Delta$ is coprime to $\Delta$. We prove that PST occurs only for $\Delta\in\{3,4,8\}$ and give necessary and sufficient conditions on the connection set for each conductor. Equivalently, the square-free radicands of oriented circulant graphs with PST are exactly $1$, $2$, and $3$. More generally, when $\lambda_j=\sqrt{D}\eta_j$ with $\eta_j\in\mathbb{Z}$, congruences satisfied by the integers $\eta_j$ determine all PST pairs and times, the minimum period, and the largest vertex sets supporting multiple state transfer (MST). In this class, pretty good state transfer is equivalent to PST. We also determine the connected orders and enumerate the resulting graphs.
Read the full abstract
Combinatorics
On spanning trees whose degrees are congruent to one modulo $\ell$
An $\ell$-congruent spanning tree of a nontrivial connected graph is a spanning tree in which every vertex has degree congruent to one modulo $\ell$. This notion provides a common generalization of classical spanning trees and odd spanning trees. We show, via a constructive greedy algorithm, that every $n$-vertex graph $G$ satisfying $n\equiv2\pmod{\ell}$ and $\delta(G)>\frac{(\ell-1)n}{\ell}$ has an $\ell$-congruent spanning tree. For the special case of odd spanning trees ($\ell=2$), our algorithmic approach simplifies the original proof by Zheng and Wu. We also derive formulas for the numbers of $\ell$-congruent spanning trees in complete graphs and complete bipartite graphs. These formulas specialize to the classical spanning-tree formulas when $\ell=1$ and to the corresponding odd-spanning-tree formulas when $\ell=2$.
Read the full abstract
Combinatorics
Standard morphisms and Pythagorean triples
Let $m\geq 1$, let $f:\mathbb N\to\mathbb Z/m\mathbb Z$ be a standard morphism and let $T(m)$ be the least integer $N$ such that every such $f$ admits a primitive monochromatic Pythagorean triple with hypotenuse at most $N$. The aim of this note is to prove that every standard morphism has infinitely many identity-valued Pythagorean triples and infinitely many primitive monochromatic Pythagorean triples. Thus the qualitative part of Problem~4.3 of Eliahou, Fromentin, Marion-Poty and Robilliard is solved for every $m$. Moreover, $T(m)$ is finite, the morphism $n\mapsto v_3(n)\pmod m$ has least possible hypotenuse $(9^m+1)/2$ and $T(d)\leq T(m)$ when $d\mid m$.
Read the full abstract
Combinatorics
Nonisomorphic Graphs Can Share an Arbitrarily Large Fraction of Their Vertex-Deleted Cards
For a graph $G$, its vertex deck is the multiset of graphs obtained by deleting one vertex. Bowler, Brown, and Fenner (BBF) proposed $2\lfloor(n-1)/3\rfloor$ as the maximum possible overlap between the decks of two nonisomorphic $n$-vertex graphs, for all sufficiently large $n$. We first give an explicit pair of connected nonisomorphic graphs on $78$ vertices with at least $51$ common cards, exceeding BBF's predicted value of $50$. We then construct, for every even $r\ge4$, families at arbitrarily large orders whose overlap fraction is asymptotically at least $1-1/r$. Consequently, for every $\alpha<1$, infinitely many pairs have more than $\alpha n$ common cards, so the attainable fraction is arbitrarily close to the full deck. For representative instances, the predicted overlaps were also checked by complete deck generation and isomorphism testing with Brendan McKay's nauty tools.
Read the full abstract
Combinatorics
Products of Two Integers Avoiding Perfect Powers
For integers $d\geq 3$, let $F_{2,d}(n)$ be the largest size of a subset of $[n]$ containing no two distinct elements whose product is a perfect $d$-th power, and let $f_{2,d}(n)$ denote the analogous quantity when the two elements need not be distinct. Fleiner, Juhász, Kövér, Pach, and Sándor proved that both complements have order $n^{2/3}$ when $d=3$, and asked for a leading constant. They also asked whether, more generally, $n-F_{k,d}(n)$ and $n-f_{k,d}(n)$ have order $n^{k/d}$ for $1<k<d$. We establish asymptotic formula in the case $k=2$ for every fixed $d\geq3$, \[ n-F_{2,d}(n)\sim n-f_{2,d}(n) \sim C_d\, n^{2/d}(\log n)^{d-3}, \] where $C_d>0$ is given explicitly by an Euler product and a polytope volume. In particular, the extra logarithmic factor gives a negative answer to the second question for every $d\geq4$. For $d=3$ we obtain \[ C_3=\frac{\pi^2}{4} \prod_p\left(1-\frac3{p^2}+\frac2{p^3}\right), \] which answers the first question. The proof uses an exact decomposition into complementary $d$-free kernel classes, a squarefree sieve in multiplicative boxes, and a two-height polytope calculation.
Read the full abstract
Combinatorics
On Arithmetic Cordial Labeling of Product Graphs
Let $\eta$ be a fixed positive integer. Let $S$ be a subset of $\mathbb{Z}$, $\star:S\times S\to \mathbb{Z}$ be a binary function, and $\zeta_{\eta}:\{\xi\in \mathbb{Z}:\gcd(\xi,\eta)=1\}\to \{0,1\}$ be a function. For a simple graph $G$ of order $n$, a bijective function $f:V(G)\to S$ (where $|S|=n$) is called an arithmetic cordial labeling modulo $\eta$ under the arithmetic structure $\langle S,\zeta_\eta,\star\rangle$ if the induced function $f_\eta^*:E(G)\to \{0,1\}$, defined by $f_\eta^*(ab)=1$ whenever $\gcd(f(a)\star f(b),\eta)= 1$ and $\zeta_\eta(f(a)\star f(b))=1$; otherwise, $f_\eta^*(ab)=0$, satisfies the condition $|e_{f_\eta^*}(0)-e_{f_\eta^*}(1)|\leq 1$, where $e_{f_\eta^*}(i)$ is the number of edges with label $i$ ($i=0,1$). In this paper, the arithmetic cordial labeling of product graphs, namely, corona, lexicographic, cartesian, tensor, and strong, is explored under the operation of addition.
Read the full abstract
Combinatorics
Bijective proofs of several conjectures on Jacobi permutations
Jacobi permutations, invented by Viennot in the context of the Jacobi elliptic functions, are counted by the Euler numbers. Recently, Henke, Hoffman, Stephens, Yuan, and Zhuang studied refined enumerations of Jacobi permutations and proposed three conjectures concerning the distribution of several statistics on Jacobi permutations. In this paper, we prove these conjectures by establishing explicit bijections involving increasing even trees, increasing binary trees, alternating permutations, and André permutations. One highlight of our results is a bijection between Jacobi permutations and André I permutations that transforms the pair of statistics $(\Ascbot, \last)$ to the pair of statistics $(\Desbot, \first)$. Here the statistic $\Ascbot$ (resp., $\Desbot$) denotes the set of ascent bottoms (resp., descent bottoms) of permutations, and the statistic $\first$ (resp., $\last$) denotes the first (resp., $\last$) letter of permutations. Furthermore, we investigate pairs of statistics on André permutations and simsun permutations that are equidistributed with the pair $(\asc, \last)$ on Jacobi permutations, where $\asc$ denotes the number of ascents of permutations. Finally, we obtain a closed-form formula for the trivariate exponential generating function of Jacobi permutations with respect to the number of ascents and the numbers of letters smaller and larger than the last letter.
Read the full abstract
Combinatorics
One-point extensions of Euclidean Ramsey sets
Let $X$ be a finite Euclidean Ramsey set. We prove that adjoining any point outside the affine hull of $X$ gives another Euclidean Ramsey set, answering a conjecture of Ivan, Leader, and Walters. We first give an elementary product proof under the additional assumptions that the orthogonal projection of the new point lies in $conv(X)$ and that its distance from $aff(X)$ is sufficiently large. We then prove the general case by combining the product theorem for $E$-Ramsey configurations and Kříž's orbit-gluing theorem with a cyclic construction. No transitivity assumption on $X$ is needed.
Read the full abstract
Combinatorics
Average hitting times and recurrence structures II: Cartesian products of powers of cycles and regular graphs
In our previous work \cite{MiezakiTamura2026}, we clarified the second-order linear recurrence structures appearing in the average hitting times on the $k$-th power graph $C_N^k$ of the cycle graph. In this paper, for a connected $r$-regular graph $G$ on $m$ vertices, we investigate the average hitting times of the simple random walk on the Cartesian product graph $C_N^k \square G$. By using discrete Fourier analysis in the $C_N^k$ direction and the Laplacian spectral decomposition of $G$, we decompose the average hitting time into a component proportional to the average hitting time on $C_N^k$ and correction terms arising from the nonzero Laplacian eigenspaces of $G$. For each nonzero Laplacian eigenvalue, we introduce a Chebyshev-type polynomial, and when all of its roots are simple, we express the correction term as a finite Green-type sum. Furthermore, for two vertices having the same $G$-coordinate, we transform this expression into a second-order linear recurrence representation of the form $V_\ell V_{N-\ell}/V_N$. When $G$ is a walk-regular graph, the average hitting time between two vertices having the same $G$-coordinate depends only on the Laplacian eigenvalues of $G$ and their multiplicities. We also derive formulas for the number of spanning trees and the number of two-component spanning forests of $C_N^k \square G$, and give several explicit examples.
Read the full abstract
Combinatorics
Every 2-Subdivision of a Cubic Graph Is Antimagic
Let G be a finite simple cubic graph, not necessarily connected, and let S_2(G) be obtained by subdividing every edge of G twice. Li (2025) developed general constructions for antimagic labelings of repeated subdivisions, but the cubic case G(3) = S_2(G) is not covered by those methods. Our first proof constructs an edge labeling of G in which every vertex sum is sufficiently large and occurs at most twice, and then uses an orientation after subdivision to separate the remaining equal sums. A second, direct construction uses the same path decomposition to make the internal contribution at each original vertex constant, while a unique endpoint contribution distinguishes the resulting sums. The direct construction further shows that S_2(G) is strongly antimagic whenever every vertex of G has odd degree at least three.
Read the full abstract
Combinatorics
Polynomial-Time Lattice-Point Counting without Barvinok Decomposition
By using constant term manipulations, we present the first polynomial-time algorithm for lattice-point counting in fixed dimension that does not rely on Barvinok's unimodular decomposition. Our method starts from partial fraction decompositions and root-of-unity formulas for the lattice-point generating function of a rational simplicial cone. By means of a residue-lattice argument based on Minkowski's theorem, we construct a short multiplier that enables an exact recursive reduction. Smith normal form is then used to normalize the resulting child terms and restore the recursive structure. These transformations are justified by algebraic identities involving roots of binomial equations, while the algorithm itself works with integer exponent data and requires no explicit root computations. More precisely, for a rational simplicial cone \(\mathcal K\) in fixed dimension \(d\), with dual cone \(\mathcal K^*\), the algorithm achieves recursion depth \(O_d(1+\log\log(2+\ind(\mathcal K^*)))\) and produces a signed sum of at most \((1+\log\ind(\mathcal K^*))^{O_d(1)}\) unimodular cone generating functions. The framework uniformly handles numerators that are Laurent polynomials, not merely monomials, thereby giving a polynomial-time algorithm for MacMahon's partition analysis when the dimension is fixed.
Read the full abstract
Combinatorics
A Proof of a Conjecture on Fixed Perimeter Partitions
Finding fixed perimeter analogues of various partition theoretic identities and inequalities has recently emerged as an active area of research. Gray, Payne, Swisher, and Watson [Discrete Math., 2026] established several fixed perimeter analogues of partition theoretic results inspired by Euler's celebrated partition identity. Very recently, in a separate work [\textit{ar{X}iv:2608.00421}, 2026], they explored fixed perimeter analogues of inequalities related to parity biases. Introducing the concept of parity bias, Kim, Kim, and Lovejoy [Eur. J. Comb., 2020] conjectured that $pd_o(n)>pd_e(n)$ for all $n\ge 20$, where $pd_o(n)$ (respectively, $pd_e(n)$) denote the number of partitions of $n$ into distinct parts having more odd parts (respectively, even parts) than even parts (respectively, odd parts). The author, together with Banerjee, Bhattacharjee, Dastidar, and Saikia [Eur. J. Comb., 2022], proved this conjecture. Gray, Payne, Swisher, and Watson conjectured that a fixed perimeter analogue of this inequality holds for all $n\ge 9$. In this paper, we confirm their conjecture.
Read the full abstract
Combinatorics
An improved finite bound for oriented trees in tournaments
Sumner's universal tournament conjecture asserts that every tournament on $2n-2$ vertices contains every oriented tree on $n$ vertices. Let $f(n)$ be the least integer $N$ such that every tournament on $N$ vertices contains every oriented tree on $n$ vertices. Havet and Thomassé proved that $f(n)\le \lceil(7n-5)/2\rceil$, El Sahili improved this to $f(n)\le3n-3$, and Dross and Havet subsequently obtained $f(n)\le\lceil21n/8-47/16\rceil$. We refine their median-order method. More precisely, every non-bi-arborescence on $n$ vertices with $k$ leaves is $(4n-2k-4)$-unavoidable, which strictly improves their many-leaf estimate; bi-arborescences satisfy the stronger bound $2n-2$. Combining this refinement with their few-leaf bound gives $f(n)\le\lceil(18n-23)/7\rceil$ for every $n\ge2$. Thus the coefficient in the previously best general bound valid uniformly for all $n$ is reduced from $21/8$ to $18/7$.
Read the full abstract
Combinatorics
Forbidden-Total-Size Nim
We consider a variant of Nim in which, for a fixed set $S$ of nonnegative integers, a move is forbidden if the total number of remaining stones belongs to $S$. This game coincides with normal-play Nim when $S=\emptyset$, and with misère Nim when $S=\{0\}$. In this paper, we focus in particular on the case where $S$ is the set of multiples of $d$, and show that simple criteria for determining the outcome can be obtained for $d=2,3,4$.
Read the full abstract
Combinatorics
Sparse spanning $k$-strong oriented subdigraphs in split digraphs
Jackson and Thomassen conjectured that every $2k$-strong digraph admits a spanning $k$-strong oriented subdigraph [Ann. N. Y. Acad. Sci. 555 (1989) 402-412]. The conjecture holds for $k=1$ but other than some partial results that have been obtained for general $k$ in some special families of digraphs, including symmetric digraphs, the conjecture remains wide open in general. Even the existence of an integer $K$ such that every $K$-strong digraph has a 2-strong spanning oriented subdigraph is open. As a natural optimization counterpart, the minimum spanning $k$-strong subdigraph (MSSS$_k$) problem, is to find the minimum number of arcs in a spanning $k$-strong subdigraph of a $k$-strong digraph. This problem is NP-hard already for $k=1$ as it generalizes the hamiltonian cycle problem. In this paper, we address both problems simultaneously for the class of split digraphs, by constructing sparse spanning $k$-strong oriented subdigraphs. Specifically, we prove that every $k$-strong split digraph $D = (V_1, V_2; A)$ with minimum semi-degree {$\delta^0(D)\geq 26k+15$} contains a spanning $k$-strong oriented subdigraph with no more than $kn+k|V_1|+98k^2+38k+3$ arcs, where $kn + k|V_1|$ is tight and the $k^{2}$ term is tight up to a constant factor. For the class of $k$-strong tournaments with minimum semi-degree at least $26k+15$ our results improve the bound obtained by Kang in [Combin. Probab. Comput., 27:892-907, 2018].
Read the full abstract
Combinatorics
Tripartite Zarankiewicz numbers and norm graphs
For fixed integers $s\ge t\ge2$, let $\operatorname{ex}(n,n,n,K_{s,t})$ denote the maximum number of edges in a tripartite $K_{s,t}$-free graph with $n$ vertices in each part. When $s\ge(t-1)!+1$, let $r$ be the largest integer satisfying $s\ge(t-1)!r^{t-1}+1$. Using the quotient norm graphs of Alon, Rónyai and Szabó, we prove that \[ \operatorname{ex}(n,n,n,K_{s,t}) \ge \left(\frac{3}{2^{1/t}}r^{1-1/t}+o(1)\right)n^{2-1/t}. \] Improving an upper bound of Tait and Timmons, we prove that, for all $s\ge t\ge 2$, \[ \operatorname{ex}(n,n,n,K_{s,t})\le \left(\frac{3}{2^{1/t}}(s-t+1)^{1/t}+o(1)\right)n^{2-1/t}. \] Together, these bounds recover the results for $t=2$, and give the new asymptotic formula \[ \operatorname{ex}(n,n,n,K_{3,3}) =\left(\frac{3}{\sqrt[3]{2}}+o(1)\right)n^{5/3}. \] Analogous results extend to $k$-partite graphs containing no $K_{s, t}$ whose $s$-vertex or $t$-vertex side lies in a single part. As an application of our tripartite construction, we determine the tripartite multicolor Ramsey number of $K_{3,3}$ asymptotically.
Read the full abstract
Combinatorics
A solution to Butler's positivity conjecture
Let $\lambda, \mu, \nu$ be distinct partitions such that $\lambda, \mu\subset \nu$ and $|\nu/\lambda|=|\nu/\mu|=1$. We prove Butler's positivity conjecture posed in 1994: the expansion of the Macdonald intersection polynomial \[ \frac{T_\lambda\widetilde{H}_\mu(X;q,t)-T_\mu\widetilde{H}_\lambda(X;q,t)}{T_\lambda-T_\mu} \] in terms of the Schur function basis has coefficients in $\mathbb{Z}_{\geq 0}[q,t]$.
Read the full abstract
Combinatorics
On the difference between clique partition and clique covering numbers of graphs
For a graph $G$, let $\cpn(G)$ and $\ccn(G)$ denote the minimum numbers of cliques whose edge sets partition and cover $E(G)$, respectively, and put $f(n)=\max_{|V(G)|=n}\bigl(\cpn(G)-\ccn(G)\bigr).$ In 1983, Erdős, Faudree, and Ordman asked whether there is a sequence of graphs $G_n$ such that $|V(G_n)|=n$ and $\cpn(G_n)-\ccn(G_n)=n^2/4+O(n)$. The question appears as Problem 66 in Chung's survey \cite{ChungProblems} and is also listed on the UCSD Erdős Problems website. Caccetta, Erdős, Ordman, and Pullman proved that $f(n)=n^2/4-o(n^2)$. We prove that $f(n)=\left\lfloor\frac{n^2}{4}\right\rfloor-\Theta(n^{4/3}),$ and hence answer the question in the negative.
Read the full abstract
Combinatorics
A dense-case theorem for Seymour's second neighborhood conjecture
Seymour's second neighborhood conjecture asserts that every finite oriented graph has a vertex with at least as many exact second outneighbors as outneighbors. Established cases include tournaments, proved by Fisher (1996), and oriented graphs of minimum outdegree at most six, proved by Kaneko and Locke (2001); a recent preprint of Sadhukhan, Sandeep, and Sen (2026) treats minimum outdegree seven. For dense incomplete graphs, Fidler and Yuster (2007) proved the conjecture when the missing edges form a matching, a star, or a clique, Ghazal (2012) extended this direction to generalized stars, and Dara, Francis, Jacob, and Narayanan (2022) proved it when the missing edges can be partitioned into a matching and a star. We give a short counting proof of the conjecture for every oriented graph of order $n=2\delta+2$, where $\delta$ is the minimum outdegree, with no prescribed structure on the missing edges. Together with Fisher's tournament theorem, this implies the conjecture for every oriented graph satisfying $n\le2\delta+2$. Combined with the known minimum-outdegree results, this raises the best lower bound known to us on the order of a counterexample from $16$ to $17$ and, conditional on the preprint of Sadhukhan, Sandeep, and Sen (2026), from $18$ to $19$.
Read the full abstract
Tuesday 11 August
Combinatorics · Cross-listed from math.PR
The Scaling Window of Random $k$-SAT
We prove a general upper bound for scaling windows of sparse monotone covering problems. From that, we deduce that for every fixed value $k\geq 3$, the window of random $k$-SAT is $O(n/\log n)$, improving the Friedgut-Bourgain bound of $O(n/\log\log n)$. We also show that random signed Not-All-Equal-$k$-SAT and hypergraph non-two-colourability (Property B) have windows of the same order. Our upper bound for scaling windows of sparse monotone covering problems follows from a general strategy combining the strengthening of Bourgain's sharp threshold theorem by Keevash, Lifshitz, Long, and Minzer with a local-to-random replacement principle. This provides a systematic method for proving scaling-window bounds, addressing a question of Perkins.
Read the full abstract
Combinatorics
A Sharp Product Bound for Disjoint Cross-Intersecting 3-Graphs with Covering Number Three
Lin, Frankl, and Wu proved that the product of the sizes of two cross-intersecting 3-uniform hypergraphs with covering number three is at most 121. They conjectured that requiring the families to be disjoint lowers the sharp bound to 100. We prove this conjecture. The smaller family has at most eleven edges; after fixing it, the other family may be enlarged to its external family of 3-transversals. Splitting by matching number leaves an elementary intersecting case and two finite kernels. We prove the correctness of both encodings and every pruning rule, and exhaustive C++20 computations give the external-blocker maxima 21, 19, 16, 14, 12, 11, 10, 9 for family sizes 4 through 11. Concrete witnesses are checked independently in Python. A pair of ten-edge families on six vertices attains product 100.
Read the full abstract
Combinatorics · Cross-listed from math.NT
Finding all cospectral mates over a number field
We investigate a notion of cospectrality for integer matrices that is parameterized by algebraic number fields. Given a number field and a symmetric integer matrix, we wonder when conjugating the integer matrix by an orthogonal matrix with entries in the given field can produce new integer matrices. Our results concern sufficient conditions for the associated notion of spectral determination, and we give constraints on the orthogonal matrices when the conditions are not applicable. The results use the discriminant of the characteristic polynomial and properties of Krylov subspaces. We leverage the theory to develop an algorithm to find all cospectral mates over a given (small) field. An implementation of the algorithm is made available.
Read the full abstract
Combinatorics · Cross-listed from math.MG
The Five Distance Theorem For An Arbitrary Norm
The three gap theorem states that the points of the Kronecker sequence $\alpha,2\alpha,\ldots,N\alpha$, considered modulo one, divide the circle into intervals of at most three distinct lengths. In a two-dimensional nearest-neighbour analogue, Haynes and Marklof proved that the Kronecker sequence modulo an arbitrary unimodular lattice determines at most five distinct nearest-neighbour distances in the Euclidean norm, and that this bound is sharp. Dettmann subsequently constructed examples attaining five distinct distances for every $\ell_p$-norm, $1\leq p\leq\infty$. We prove the corresponding upper bound for every norm on $\mathbb R^2$: for every full-rank lattice $L$, every $\alpha\in\mathbb R^2$, and every $N\in\mathbb N$, the number of distinct nearest-neighbour distances is at most five. For every norm, this bound is attained for some $L$ and $\alpha$. For strictly convex norms, the proof extends the lattice-theoretic argument of Haynes and Marklof by replacing the Euclidean angular estimates with a cone lemma based on a proper Brass angular measure. The result for arbitrary norms is then obtained by a strictly convex perturbation and a limiting argument.
Read the full abstract
Combinatorics · Cross-listed from math.AG
Deletion-contraction properties of graphically stable spaces
Graphically stable spaces $\overline{\mathcal{M}}_{g,G}$ parametrize marked nodal curves whose permitted collisions of markings are determined by a graph. We study intersection numbers of $\psi$-classes on $\overline{\mathcal{M}}_{g,G}$, as well as the classes $[M_{g,G}]$ in the Grothendieck ring of varieties. In both settings, we show that the geometry is governed by an underlying graphical structure, expressed through deletion-contraction relations. As consequences, we derive string and dilaton equations and express several families of $\psi$-class integrals in terms of the chromatic polynomial. We also express the Grothendieck class of $M_{0,G}$ over an arbitrary field in terms of the chromatic polynomial and identify various Euler characteristics with combinatorial quantities. Along the way, we obtain a new formula for Crapo's $\beta$-invariant of graphs. Finally, we extend these relations to genus one and, under a chromatic condition, to higher genus.
Read the full abstract
Combinatorics
Submodular and strongly submodular functions and diversities
Submodular functions and their close relatives play a key role in combinatorial optimization, decision theory and potential theory. Part of their importance and usefulness stems from the connections with convex functions and polytopes. Here we explore connections between these functions and metric theory, with the bridge provided by diversities, a recently developed generalization of metric spaces to (finite) sets rather than just pairs. Both submodular functions and strongly submodular functions correspond to natural classes of diversities. Submodular diversities, as we define them here, are essentially non-decreasing, intersecting submodular functions which vanish on singletons. We prove new geometric embedding results for these diversities. In particular we show that submodular, strongly submodular, and XOS functions can be represented by the generalized circumradius, a set function in convex analysis equal to the amount a given convex body needs to be stretched to cover a set of points.
Read the full abstract
Combinatorics
Optimal lower bounds for epsilon-nets for lines in the plane
We prove that, for arbitrarily small positive $\varepsilon$, there is a finite planar point set $P$ such that every $\varepsilon$-net for the range space induced on $P$ by straight lines has cardinality $\Omega\bigl(1/\varepsilon \cdot \log(1/\varepsilon)\bigr)$. This matches the classical upper bound for range spaces with bounded VC-dimension due to Haussler and Welzl and confirms a prediction of Alon.
Read the full abstract
Combinatorics
Unit Actions on Homometric Five-Point Subsets of Cyclic Groups: Orbit and fixed-point refinement of the seven-family classification
Erickson and Jones classified the nontrivial homometry classes of five-point binary bracelets into seven families, Types A-G, and conjectured that each family is invariant under multiplication by units modulo sign. We prove this conjecture and show that the induced actions are diagonal for Type A, multiplicative for Types B-E, affine for Type F, and regular through $U_{20}/\{\pm1\}\cong C_4$ for Type G. We derive closed arithmetic formulas for the numbers of unit orbits and classes fixed by every unit, and determine the orbit-size distributions in all seven types, including explicit stabilizer descriptions for Types A and F.
Read the full abstract
Combinatorics · Cross-listed from cs.CC
An FKN Theorem for the Binary Grassmann Scheme
A classical theorem due to Friedgut, Kalai and Naor asserts that if a function $f\colon \{0,1\}^n\to\{-1,1\}$ close to a degree $1$ function, then either $f$ or $-f$ is close to either the all $1$ function, or to $(-1)^{x_i}$ for some $i\in [n]$. We prove a version of their theorem for the Grassmann scheme over $\mathbb{F}_2$. More precisely, we prove if a function $f\colon \genfrac{[}{]}{0pt}{}{\mathbb{F}_2^n}{\ell}\to\{0,1\}$ is close to a degree $1$ function, then either $f$ or $1-f$ must be close to a function of the form $g(L) = \sum_{x\in\mathcal{X}}1_{x\in L}+\sum_{W\in\mathcal{W}}1_{L\subseteq W}$, where $\mathcal{X}\subseteq\mathbb{F}_2^n$ is a set of points and $\mathcal{W}$ is a set of hyperplanes in $\mathbb{F}_2^n$.
Read the full abstract
Combinatorics
Solutions to Five Challenge Problems in Enumerative and Algorithmic Combinatorics, with an Account of the Human-Machine Methodology Employed
We report solutions to five challenge problems posed by Doron Zeilberger and his collaborators, together with substantial partial progress on two further problems, and we describe the method by which they were obtained. The solved problems are: the Second Computational Chomp Challenge of Ekhad and Zeilberger, for which we exhibit a bar with three winning opening moves; the third challenge of Spahn and Zeilberger, asking whether the restricted permutation counts a_{r,s} and b_{r,s} are holonomic for all r,s>1, answered affirmatively; the First Rigorous Solid Standard Young Tableaux Challenge, for which we prove the conjectured second-order recurrence; the five-dimensional Geode Challenge of Amdeberhan, Kauers and Zeilberger; and Conjectures 2a and 2b of Kauers and Zeilberger, which we obtain from a local limit theorem for excursions of Markov-modulated random walks in cones. Several results of independent interest arise along the way: a staircase theorem constraining the winning opening moves of any Chomp bar, together with a parity theorem for square bars; an explicit algebraic generating function for reverse-Kreweras diagonal walks and a closed form for their diagonal-endpoint counts; a one-dimensional integral representation for diagonal Geode coefficients; and the identity that each Kauers-Zeilberger constant is a universal factor times the square of the apex value of a discrete cone-harmonic function. All of the work reported here was carried out in collaboration with a large language model. The paper sets out the division of labour, records the verification protocol this mode of work required, and documents the failures, which we regard as an essential part of the report.