Browse

Combinatorics

math.CO — Combinatorics

Works in math.CO

14 works

math.MG — Metric Geometry

A Fourier Consequence for Lattice Kissing Numbers and Average Contacts

Contributed by Scott Kominers

We deduce a new asymptotic upper bound $K_{\mathrm{lat}}(n)\leq\left(\sqrt{2e/\pi}+o(1)\right)^n$ on the maximal lattice kissing number $K_{\mathrm{lat}}(n)$ in dimension $n$ , using the explicit auxiliary functions constructed in OpenAI's "Ten Advances" preprint. The same bound holds for the average contact degree of a finite packing of congruent balls. The bound's base- $2$ exponential rate rounds to $0.3956$ , matching the value extrapolated empirically by Afkhami-Jeddi, Cohn, Hartman, de Laat, and Tajdini in 2020.

A mix of human-written and AI-generated textHuman understanding: all partsContact numbersDiscrete geometryEuclidean latticesFourier linear programming boundsGeometry of numbersKissing numbersSphere packing

Oct 02, 2026PDF ↗View work →

hexagon:2610.00016v1

math.CO — Combinatorics

An Exponent of 1.04273 for the Unit Distance Problem

Contributed by Eric Naslund

Let $u(U)$ count the unordered pairs at distance one in a finite planar set $U$ . We construct finite sets $U_j$ with $|U_j|\to\infty$ and $u(U_j)/|U_j|^{1.04273}\to\infty$ . The largest exponent previously claimed, $1.0358$ , is in the author's unpublished manuscript. The method is the number-field construction of OpenAI and Sawin: unit distances come from elements of relative norm one in quadratic extensions, and the fields come from an infinite pro- $2$ class field tower. The new ingredients are quadratic extensions of mixed signature, with an exact average over their norm-one units, and a tower over the real quadratic field $\Q(\sqrt{241})$, in which $2$ , $3$ and $5$ split. Its Golod--Shafarevich function contains two copies of the local conditions at these primes but only one constant term, and the extra room lets the tower be ramified only above $2$ , $3$ and $5$ ; the root discriminant of its fields is about $286$ . The relative zeta value is bounded through the zeta function of the degree- $512$ field generated over $\Q(\sqrt{241})$ by the square roots of its $\{2,3,5\}$ -units, which is the product of the Dedekind zeta function of $\Q(\sqrt{241})$ and $255$ quadratic Hecke $L$ -functions. Finite facts and numerical inequalities are certified by exact computation and interval arithmetic. A significant portion of this work was verified in Lean, reducing the result with exponent $1.0427$ to an explicit zeta function inequality (Palomar registry, PALOMAR-2026-10-01-000018, version 1).

Primarily AI-generated textHuman understanding: some parts

Oct 02, 2026PDF ↗View work →

hexagon:2610.00015v1

math.CO — Combinatorics

Tilings of an equilateral triangle by at most five lattice trapezoids with 60° base angles: a complete structural classification

Contributed by Gonzalo Barria

We study tilings of an equilateral triangle of side n in the triangular grid by k lattice trapezoids with base angles 60°, the objects behind the OEIS sequences A389392 (k = 4) and A391498 (k = 5). We prove two angle identities valid for every such tiling and a lemma relating the number of boundary vertices to the number of pieces having a side on the boundary. With these tools we show that there are exactly 1, 2 and 13 combinatorial types of tilings for k = 3, 4, 5. For k = 3 every tiling is a pinwheel. For k = 4 every tiling belongs to one of the two categories used in A389392, a fact that had previously been taken for granted. For k = 5 the thirteen types refine the eight categories of A391498; in three of them a piece has no side on the boundary. As a consistency check, the volumes of the parameter polytopes together with the generic multiplicities reproduce the leading coefficient 7/36 of the conjectured quasi-polynomial for A391498. All lemmas were checked against an exhaustive enumeration of the tilings with pairwise distinct pieces for n ≤ 15. Finally, the classification turns the thirteen types into eight explicit families of sets of shapes, and an inclusion–exclusion over them reduces the conjectured generating function of A391498 to twelve elementary counting statements, and we settle all twelve: the resulting closed formula reproduces the sequence for every n ≤ 127.

A mix of human-written and AI-generated textHuman understanding: all partsOEIS A391498lattice trapezoidsquasi-polynomialrational generating functiontilings of an equilateral triangle

Oct 01, 2026PDF ↗View work →

hexagon:2610.00012v1

math.RA — Rings and Algebras

A finite criterion for total sign skew symmetry in order three

Contributed by 琪越唐

We give a finite criterion for total sign skew symmetry of integer matrices of order three.

A mix of human-written and AI-generated textHuman understanding: some partsCluster Algebra

Oct 01, 2026PDF ↗View work →

hexagon:2609.00142v1

math.CO — Combinatorics

Collapsibility of Alexander duals for shade maps

Contributed by Darij Grinberg

Let $E$ be a nonempty finite set. A shade map on $E$ is a map $T:\mathcal{P}(E)\rightarrow\mathcal{P}(E)$ such that toggling an element $u\notin T(F)$ in the input $F$ does not change $T(F)$ . We prove that, if $T$ is an inclusion-reversing shade map and $G\subseteq E$ , then the simplicial complex \[ \{F\subseteq E\mid G\subseteq T(F)\} \] is collapsible. Equivalently, if $S$ is an inclusion-preserving shade map, then the Alexander dual of \[ \{F\subseteq E\mid G\not \subseteq S(F)\} \] is collapsible. This is an Alexander-dual companion to the shade-map collapsibility theorem in \emph{The Elser nuclei sum revisited}. The proof first matches all faces on which $T(F)\neq E$ by a toggle. The remaining faces, characterized by $T(F)=E$ , form the free convex set complex of an associated antimatroidal quasi-closure operator. We give a self-contained recursive acyclic matching on this complex. For ordinary convex geometries, Korte--Lovász--Schrader prove the stronger fact that the free convex set system is non-evasive.

A mix of human-written and AI-generated textHuman understanding: all partsantimatroidsconvex geometriesdiscrete Morse theorygraphssimplicial complexes

Sep 30, 2026PDF ↗View work →

hexagon:2609.00140v1

math.CO — Combinatorics

Coefficientwise positivity for alternating sums of $q$ -factorials

Contributed by David Anderson

We prove that the alternating sum $\sum_{i=0}^{k}(-1)^i\binom ki[m-i]!_q$ has nonnegative coefficients whenever $m\ge 2k-1$ . For $k\ge3$ , this range is exact. The case $m=2k$ proves a conjecture of Lewis and Morales arising from the enumeration of invertible matrices with prescribed zero entries. After removing a common $q$ -factorial, we express the sum in a Gaussian-binomial basis whose coefficients are independent of the ambient size. Their positivity follows from a coefficientwise domination argument using convexity of ordinary binomial coefficients.

Primarily AI-generated textHuman understanding: all parts

Sep 30, 2026PDF ↗View work →

hexagon:2609.00138v1

math.CO — Combinatorics

Signed seeds and G-gradings on cluster algebras

Contributed by Lauren Williams, Alan Yan

The theory of cluster algebras is closely connected to the theory of total positivity; indeed, the desire to better understand total positivity was one of the main motivations for Fomin and Zelevinsky’s introduction of cluster algebras [FZ02]. In particular, any cluster variety whose coordinate ring has a cluster structure has a natural notion of positive part: the subset of the variety where all cluster variables are positive. In this paper, we explain that there are other signed cells contained in cluster varieties that are equally natural from a cluster-theoretic point of view. These come from signed seeds, which can be thought of as a Z/2Z-grading on cluster variables, and which were introduced in [EZLP+ 23] in the context of the amplituhedron. More generally, given any abelian group G, we introduce the notion of a G-graded seed for a cluster algebra, which is a way of assigning elements of G to each cluster variable which is compatible with the cluster structure. When G is the multiplicative group {−1, 1}, this recovers the above notion of signed seed; when G = C∗ , this recovers the notion of cluster automorphism group [GSV10] or cluster dilation group [NS26]; and when G = Zd , this recovers the notion of graded cluster algebra studied by Grabowski-Launois [GL14], Grabowski [Gra15] and Gekhtman-Shapiro-Vainshtein [GSV10, Section 5.2] (which had previously appeared in special cases in work of Fomin-Zelevinsky [FZ07]). The examples we study include the space of square matrices, symmetric matrices, skew-symmetric matrices, positroid varieties, and amplituhedron tiles. We also connect this notion to tropical mutation when G = R or Z.

Primarily human-written textHuman understanding: all partsGrassmanniansamplituhedroncluster algebras

Sep 30, 2026PDF ↗View work →

hexagon:2609.00137v1

math.CO — Combinatorics

On a non-basis of the coinvariant algebra

Contributed by Darij Grinberg

A conjecture arising from a question of Procesi proposes a basis of the coinvariant algebra of $S_n$ consisting of column-antisymmetrized monomials indexed by pairs of standard Young tableaux. We show that the proposed family need not even span an $S_n$ -subrepresentation: for $n=8$ , a generator of degree $15$ is sent outside the span by the adjacent transposition $(4,5)$ . The proof is an exact finite computation with an explicit separating functional, requiring neither a rank computation nor Gr\"obner reduction. We also retain an explicit relation for $n=7$ , where the basis assertion first fails, although the span is still invariant.

A mix of human-written and AI-generated textHuman understanding: all partsSpecht modulesYoung tableauxcoinvariant algebrahigher Specht polynomialsrepresentations of the symmetric group

Sep 29, 2026PDF ↗View work →

hexagon:2609.00133v1

math.RA — Rings and Algebras

A Universal Noncommutative Splitting Algebra for Polynomials

Contributed by Darij Grinberg

Let $R$ be a commutative ring. We show that every homogeneous polynomial $f\in R[x_{1},\ldots,x_{m}]$ of degree $n$ splits into a product of $n$ homogeneous linear forms over a suitable noncommutative ring extension $S$ of $R$ (that is, over a noncommutative $R$ -algebra $S$ whose structure morphism $R\rightarrow S$ is injective). The algebra $S$ is universal for such factorizations and is free as an $R$ -module. The proof uses Bergman's Diamond Lemma: we define $S$ by generators and relations, and the relations form a terminating reduction system that has no ambiguities and thus is confluent. An analogous result is also shown for inhomogeneous polynomials (with inhomogeneous factors). This easily follows from the homogeneous case by homogenizing and then setting the homogenizing variable equal to $1$ .

A mix of human-written and AI-generated textHuman understanding: all partsBergman's diamond lemmaGröbner basescombinatorial algebranoncommutative polynomials

Sep 29, 2026PDF ↗View work →

hexagon:2609.00135v1

math.CO — Combinatorics

A counterexample to the Burman--Kulishov conjecture on Lie elements

Contributed by Darij Grinberg

Burman and Kulishov defined Lie elements in the group algebra $\mathbf k[S_n]$ by comparing, on every exterior power of the reflection representation $V$ , the usual action of $\mathbf k[S_n]$ with the infinitesimal action induced by its action on $V$ . They conjectured that the Lie algebra $\mathcal L_n$ of all Lie elements is generated by the Kirchhoff differences $1-(ij)$ . We disprove this conjecture for $n=4$ by exhibiting an explicit counterexample arising from the $(2,2)$ -block of $\mathbf k[S_4]$ . More generally, we describe $\mathcal L_n$ in terms of the Artin--Wedderburn decomposition of $\mathbf k[S_n]$ : its hook blocks are determined by the action on $V$ , whereas its non-hook blocks are arbitrary. Consequently, the primitive central idempotents of the non-hook blocks yield linearly independent obstructions to the conjecture. We also identify the Lie algebra generated by the Kirchhoff differences in terms of the derived algebra of the Lie algebra generated by transpositions. Along the way, we give an integral, and hence characteristic-free, proof that the exterior powers of $V$ are the hook-shaped Specht modules.

A mix of human-written and AI-generated textHuman understanding: all partsLie algebrasymmetric group algebrasymmetric group representations

Sep 29, 2026PDF ↗View work →

hexagon:2609.00121v1

math.AC — Commutative Algebra

Polynomials over Symmetric Polynomials

Contributed by Darij Grinberg

Let $\mathbf{k}$ be a commutative ring, and let the symmetric group $\mathfrak{S}_{n}$ act on $P=\mathbf{k}\left[ x_{1} ,x_{2},\ldots,x_{n} \right] $ by permuting the variables. We prove four results that are known (at least in the case when $\mathbf{k}$ is a field) but not easily found in the literature. First, the coinvariant algebra (the quotient of $P$ by the ideal generated by the symmetric polynomials with constant term $0$ ) is a free $\mathbf{k}$ -module of rank $n!$ , with the residue classes of the Artin monomials as a basis. Second, $P$ is a free module of rank $n!$ over the ring $P^{\mathfrak{S}_{n}}$ of symmetric polynomials, again with the Artin monomials as a basis. Third, if $n!$ is invertible in $\mathbf{k}$ , the coinvariant algebra is the regular $\mathbf{k}\left[ \mathfrak{S}_{n} \right] $-module. Fourth, under the same hypothesis, $P$ is a free left $P^{\mathfrak{S}_{n}}\left[ \mathfrak{S}_{n} \right]$ -module of rank $1$ . The first result follows from an elementary normal-form lemma for monic polynomials with pairwise relatively prime leading monomials. The second is proved by lifting the Artin basis. For the third, we use orbit harmonics with a strongly discrete point orbit, and the fourth follows by equivariantly lifting a regular basis of the coinvariant algebra.

A mix of human-written and AI-generated textHuman understanding: all partsArtin basisGröbner basescoinvariant algebraorbit harmonicssymmetric polynomials

Sep 28, 2026PDF ↗View work →

hexagon:2609.00118v1

math.CO — Combinatorics

A counterexample to ordering-independence for chromatic operators

Contributed by Darij Grinberg

We give a $10$ -vertex counterexample to a conjecture of Pawlowski asserting that the characteristic polynomial of a chromatic operator associated with a forest is independent of the ordering of its edges. The two operators already have different traces of fifth powers.

Primarily AI-generated textHuman understanding: all partsGraph coloringSpecht modulessymmetric group algebra

Sep 28, 2026PDF ↗View work →

hexagon:2609.00117v1

math.AC — Commutative Algebra

Splitting a Polynomial into Linear Factors after an Injective Ring Extension

Contributed by Darij Grinberg

We show that each univariate polynomial $P = p_0 + p_1 X + \cdots + p_m X^m \in R[X]$ over a commutative ring $R$ can be factored into linear factors over a suitable commutative ring extension $S$ of $R$ . The proof proceeds by universal construction: $S$ is defined as the tensor product $R \otimes_{C_m} B_m$ , where $B_m$ is the polynomial ring $\ZZ[a_1, b_1, a_2, b_2, \ldots, a_m, b_m]$, and where $C_m$ is its subring generated by its ``homogenized elementary symmetric polynomials'' $E_r=\sum_{\substack{I\subseteq [m];\\ |I|=r}} \prod_{i\in I}a_i\prod_{i\notin I}b_i$ for all $0 \leq r \leq m$ . The injectivity of the structure homomorphism $R \to S$ is deduced from a combinatorial study of the diagonal subring of $B_m$ . In the process, a homogeneous variant of the Garsia--Stanton basis is constructed, and some classical properties of symmetric polynomials are recovered.

A mix of human-written and AI-generated textHuman understanding: all parts

Sep 28, 2026PDF ↗View work →

hexagon:2609.00116v1

math.CO — Combinatorics

A Counterexample to a Conjecture on Fused Specht Polynomials

Contributed by Darij Grinberg

Lafay, Peltola and Roussillon conjectured that their realization of simple modules of the fused Hecke algebra by fused Specht polynomials extends from Young diagrams with two columns to Young diagrams of arbitrary shape. We give a counterexample for \[ n=8,\qquad \lambda=(3,2,2,1),\qquad \varsigma=(2,2,2,2). \] More precisely, we exhibit an explicit linear dependence among three fused Specht polynomials indexed by row-strict Young tableaux. The same example also yields an infinite family of counterexamples.

Primarily AI-generated textHuman understanding: some partsSpecht modulesSpecht polynomialsYoung tableaux

Sep 28, 2026PDF ↗View work →