Combinatorics
See recent articles
Showing new listings for Friday, 20 November 2026
- [1] arXiv:2611.24958 [pdf, html, other]
-
Title: Thirteen Improved Binary Constant-Weight Codes with Explicit Cyclic Orbit CertificatesComments: 2 pages; 13 explicit constant-weight code constructions with cyclic orbit certificates; ancillary codeword lists and verification softwareSubjects: Combinatorics (math.CO); Information Theory (cs.IT)
We exhibit thirteen explicit binary constant-weight codes improving lower bounds recorded in Brouwer's table, including $A(29,6,5)\geq 333$, $A(55,4,5)\geq 66144$, and $A(62,4,5)\geq 107360$. Their 408,729 codewords are specified by 11,386 orbit representatives under explicitly given cyclic coordinate permutations, together with a standalone reconstruction and distance verifier. All thirteen orbit expansions were checked to agree exactly with the full codeword lists.
- [2] arXiv:2611.24973 [pdf, html, other]
-
Title: Star decomposition of complete multipartite graphsComments: 16 pages, 3 figures, 3 tablesSubjects: Combinatorics (math.CO)
We study minimum degree-sum conditions for decompositions into stars of sizes $k$ and $k+1$, where $k\ge3$. Write $\sigma(G)=\min_{uv\in E(G)}(d(u)+d(v))$, and let $c_k$ be the least integer threshold guaranteeing a $\{K_{1,k},K_{1,k+1}\}$-decomposition for every finite simple graph. Using Tarsi's sufficient condition, we prove that $K_n$ admits such a decomposition whenever $n\ge2k$. Together with the obstruction $K_{2k-1}$ of Zhao and Wu, this gives the optimal integer threshold $4k-3$ for complete graphs. For complete multipartite graphs, we establish the sufficiency of $\sigma(G)\ge9$ when $k=3$ by a finite computational verification and an extension argument. For every $k\ge3$, the complete tripartite graph $G_k=K_{k^2-k-1,k-2,1}$ satisfies $\sigma(G_k)=k^2-1$ and has no such decomposition. Consequently, $c_k\ge k^2$, even when the class is restricted to complete multipartite graphs. The optimal integer threshold in this class is therefore $9$ for $k=3$. Sufficiency of $\sigma(G)\ge k^2$ for complete multipartite graphs with $k\ge4$, and the exact values of $c_k$ for general graphs, remain open in this study.
- [3] arXiv:2611.24974 [pdf, html, other]
-
Title: The chromatic-AT choosability of Pseudo-Halin graphsSubjects: Combinatorics (math.CO)
The \emph{Alon-Tarsi number} $AT(G)$ of a graph $G$ is the smallest integer $k$ such that $G$ admits an orientation $D$ with maximum outdegree at most $k-1$ in which the number of even Eulerian subdigraphs differs from the number of odd Eulerian subdigraphs. A 2-connected planar graph $G$ with minimum degree at least 3 is called a \emph{pseudo-Halin graph} if deleting the edges on the boundary of a single face $f_0$ yields a tree. Let $\mathcal{A}$ denote the class of pseudo-Halin graphs in which no two interior vertices are adjacent and every interior vertex has odd degree (equivalently, graphs obtained by iterated Hajós sums of wheels with an odd number of exterior vertices). In this paper, we completely determine the chromatic number and the Alon-Tarsi number of all pseudo-Halin graphs. Specifically, by structural induction and the method of $AT$-orientations, we prove that $AT(G)=\chi(G)=4$ if $G\in\mathcal{A}$, and $AT(G)=\chi(G)=3$ otherwise. Consequently, every pseudo-Halin graph is chromatic-AT choosable.
- [4] arXiv:2611.25050 [pdf, html, other]
-
Title: On the Erdős--Ginzburg--Ziv problem for $\mathbb Z_n^3$Subjects: Combinatorics (math.CO); Number Theory (math.NT)
The Erdős--Ginzburg--Ziv constant $\mathsf s(\mathbb Z_n^r)$ is the least positive integer $t$ such that every sequence of $t$ elements of $\mathbb Z_n^r$ contains $n$ terms whose sum is zero. In this paper, we prove that $$\mathsf s(\mathbb Z_n^3)=9n+o(n)$$ for odd $n$. For every fixed $r\ge 4$, we also show that $\mathsf s(\mathbb Z_n^r)\le\bigl(\binom{2r-1}{r}+1\bigr)n+o_r(n).$ Our approach combines Alon--Dubiner-type spectral expansion, Zakharov's convex-geometric framework, and restricted-sum ideas developed by Han and Ren.
- [5] arXiv:2611.25099 [pdf, html, other]
-
Title: Flatness and Tightness in HypertopesComments: 16 pagesSubjects: Combinatorics (math.CO)
A hypertope is a thin, residually connected incidence geometry. For each pair of types $\{i,j\}$, the residues of that type must be polygons, and if all residues of that type are the same type of polygon, then we can record this information in a diagram $D$. Given such a diagram, we prove a lower bound on the number of chambers of a hypertope with that diagram. A hypertope that achieves this bound is called \emph{tight}. We prove that a hypertope is tight if and only if its diagram $D$ is a forest and, for every pair of types $\{i,j\}$ that is not an edge of $D$, every $i$-element is incident to every $j$-element. This generalizes a previously known result about abstract polytopes. Finally, we describe a combinatorial method and an algebraic method for constructing tight hypertopes.
- [6] arXiv:2611.25115 [pdf, html, other]
-
Title: A Density Bound for Muñiz's List ReversalSubjects: Combinatorics (math.CO)
Muñiz described the problem of reversing a list of positive integers under the following rules: given a list of distinct positive integers, at each step, one can combine two adjacent entries into their sum or break an entry into two entries with the same sum, under the constraints that after each step the list must contain distinct entries no larger than the original largest entry. The question of what lists are and are not reversible under these rules is studied and an asymptotic upper bound on the density of an irreversible list is established.
- [7] arXiv:2611.25137 [pdf, html, other]
-
Title: Labeled Chip-Firing on Ordered Directed GraphsComments: 29 pages, 6 figures, 1 tableSubjects: Combinatorics (math.CO)
We study labeled chip-firing on rooted directed graphs where for each vertex $v$, the children of $v$ are linearly ordered. When a vertex fires, the selected chips are sent to its children in increasing order. We show that homomorphisms preserving these child choices transport legal firing sequences. We then consider the directed lattice $\mathbb Z_{\geq0}^2$ and ask which chips can reach a given vertex. We give a recurrence for the smallest reachable label when sufficiently many chips are present and show that consecutive pairing attains this minimum. Finally, we determine the largest reachable label by symmetry and prove that the reachable labels form an interval when the number of initial chips is sufficiently large.
- [8] arXiv:2611.25143 [pdf, html, other]
-
Title: New lower bounds for six small hypergraph Ramsey numbersComments: 13 pages, 3 tables. The colourings and the programs that verify them are included as ancillary filesSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
Let $R(k,l;t)$ denote the least $n$ such that every colouring of the $t$-subsets of an $n$-set with two colours has $k$ points all of whose $t$-subsets have the first colour, or $l$ points all of whose $t$-subsets have the second. We give explicit colourings proving $R(4,5;3)\ge 38$, $R(4,6;3)\ge 71$, $R(5,5;3)\ge 99$, $R(5,6;4)\ge 201$, $R(6,6;4)\ge 601$ and $R(6,6;5)\ge 84$. The first three improve the bounds 35, 63 and 88 listed in Radziszowski's dynamic survey. The last three improve the listed bounds 67, 133 and 72, and for the two 4-uniform numbers also the values 159 and 317 of a recent data deposit. The colourings of 3-subsets are invariant under groups of affine maps $x\mapsto ax+b$ of $\mathbb{Z}_n$, for $n=37$, 69 and 97, in the last two cases with one further fixed point. Those of 4-subsets live on the projective line over $\mathbb{F}_q$, for $q=199$ and $q=599$, and are invariant under $\mathrm{PSL}(2,q)$ or $\mathrm{PGL}(2,q)$, so each is given by a table of $q$ entries. For 5-subsets we show that, for every prime $q\ge 5$, invariance under $\mathrm{PGL}(2,q)$ forces six points all of whose 5-subsets have the same colour; our colouring is invariant under all affine maps of $\mathbb{Z}_{83}$. By known constructions the bounds give $R(5,5,5;3)\ge 9605$ and $R_k(5;3)\ge 98^{2^{k-2}}+1$, and $R(6,7;4)\ge 2001$, $R(7,7;4)\ge 12001$ and $R(8,8;4)\ge 588001$. The colourings, and programs that verify them, accompany the paper as ancillary files.
- [9] arXiv:2611.25148 [pdf, html, other]
-
Title: A refinement of Szemerédi's distinct-distance bound for points in general positionComments: 6 pagesSubjects: Combinatorics (math.CO)
We prove that every collinear triple free set of $n\ge4$ points in the Euclidean plane determines at least $\lfloor n/3\rfloor+1$ distinct distances. This refines the classical bound $\lceil(n-1)/3\rceil$ of Szemerédi that is based on counting isosceles triangles. The refinement is based on treating the diameters separately: they only appear on the convex hull, so for them, we can use the planar diameter theorem and Altman's theorem on distances in convex polygons.
- [10] arXiv:2611.25153 [pdf, html, other]
-
Title: \textsc{Max-Cut} on Token GraphsJosé Angel Alejandro-Soto, Paulo T. Araujo, Ruy Fabila-Monroy, Sergio Gerardo Gómez-Galicia, Mohamed Hibat-Allah, Md Moshiur Rahman Raj, Mahmud Ashraf Shamim, Ana Laura Trujillo-NegreteSubjects: Combinatorics (math.CO); Strongly Correlated Electrons (cond-mat.str-el)
Let $G$ be a graph on $n$ vertices, with a positive weight assigned to each edge. A cut of $G$ is a partition of its vertices into two sets $X$ and $Y$; the weight of $(X,Y)$ is the sum of the weight of the edges of $G$ with one endpoint in $X$ and the other endpoint in $Y$. The Max-Cut problem asks for the maximum weight, $m(G)$, of a cut of $G$. The $k$-token graph of $G$, is the graph, $F_k(G)$, whose vertices are the $k$-subsets of vertices of $G$, two of them being adjacent when their symmetric difference is an edge of $G$. The phase-reconstruction problem for Heisenberg antiferromagnets in physics can be rephrased as a Max-Cut problem on token graphs. Motivated by this, we study the Max-Cut problem on token graphs, mainly when all edges are assigned the same weight. Our main focus is to bound $m(F_k(G))$ in terms of $m(G)$. We prove that $m(F_k(G))\geq\binom{n-2}{k-1}m(G)$, and that this bound is tight up to a multiplicative factor of $1+O(k/n)$; in the case when $k=c \cdot n$ for some constant $0 < c < 1$, we provide an example where this bound is off by a multiplicative constant factor. We also show bounds for $m(F_k(G))$ for various classes of graphs $G$. Finally, we consider the algorithmic complexity of finding $m(F_k(G))$, showing it to be NP-complete for a constant $k$, and giving evidence that, when the weights take finitely many values, it is not NP-hard for $k\geq n^{\delta}$ for any constant $\delta>0$.
- [11] arXiv:2611.25182 [pdf, html, other]
-
Title: Iterative constructions of semifields 2-dimensional over a nucleusSubjects: Combinatorics (math.CO); Rings and Algebras (math.RA)
The construction of finite semifields dates back to Dickson's work in 1906. To the best of our knowledge, only two iterative constructions were previously known: those of Hiramine, Matsumoto and Oyama in 1987, and of Kantor and Williams in 2004. The latter yields, for suitable even orders, superpolynomially many pairwise non-isotopic semifields. In this paper, we use skew-polynomial rings to give a new iterative construction of finite semifields. This construction produces large families of pairwise non-isotopic semifields, each of which is $2$-dimensional over one of its nuclei. In particular, we show that this construction method yields semifields not contained in any family of semifields known so far.
- [12] arXiv:2611.25244 [pdf, html, other]
-
Title: A note on Turán densities of daisies and hypergraph productsComments: 14 pagesSubjects: Combinatorics (math.CO)
The Turán density of an $r$-uniform hypergraph $\mathcal H$ is defined as ${\pi}(\mathcal{H})=\lim_{n\rightarrow\infty} \operatorname{ex}(n,\mathcal{H})/\binom{n}{r}$, where $\operatorname{ex}(n,\mathcal H)$ denotes the largest number of edges in an $\mathcal H$-free $r$-uniform hypergraph on $n$ vertices. For integers $r\geq s\geq2$ and $t\geq s$, an $(r,s,t)$-daisy $\mathcal D_r(s,t)$ is the $r$-uniform hypergraph consisting of all unions of a fixed $(r-s)$-set with the $s$-subsets of a disjoint $t$-set. We show that for every fixed $s\geq3$, \[
\lim_{r\rightarrow\infty}{\pi}(\mathcal D_r(s,t))=1-O_s(t^{-(s-1)}) \] as $t\rightarrow\infty$. This bound is best possible up to the implicit constant by a classical result of de Caen, and it answers, in a stronger form, a question of Ellis, Ivan and Leader, who asked for the case $s=3$. Moreover, we show a related result for matroid basis hypergraphs. We also consider Turán densities of hypergraph products, of which daisies are a special case. The product of two hypergraphs on disjoint vertex sets consists of all unions of an edge of the first with an edge of the second. For the product $\mathcal H^d$ of $d$ disjoint copies of a fixed $r$-uniform hypergraph $\mathcal H$ that is not $r$-partite, we show that $1-\pi(\mathcal H^d) \rightarrow 0$ exponentially fast as $d\rightarrow\infty$, and we determine the exponential rate in terms of the minimum number of edges in a homomorphic image of $\mathcal H$. This answers a question of Bollobás, Leader and Malvenuto up to a polynomial factor in $d$, and we further address a related question of theirs for products of two different hypergraphs. - [13] arXiv:2611.25266 [pdf, html, other]
-
Title: Nilpotent skew-symmetric tridiagonal Bohemian matrices: a proof of Corless's conjectureSubjects: Combinatorics (math.CO); Rings and Algebras (math.RA)
Corless studied the skew-symmetric tridiagonal matrices $T_m(u)$ with superdiagonal $u \in \{1, i\}^{m-1}$. He showed that $T_m(u)$ can be nilpotent only if $m = 2^K - 1$ and that the $2^{K-1}$ vectors $u$ obtained from the empty vector by repeated application of $u \mapsto (u, 1, i, \rev u)$ and $u \mapsto (u, i, 1, \rev u)$ give nilpotent matrices, and he conjectured that there are no others. We prove this conjecture. Reducing the characteristic polynomial modulo $4$ gives a necessary condition for nilpotency that is linear over $\F$. For $m > 1$ it forces $u = (v, 1, i, \rev v)$ or $u = (v, i, 1, \rev v)$, and an identity implicit in Corless's proof then reduces the problem to $v$. Since $T_m(u)$ is diagonally similar to a finite section of the Feinberg--Zee hopping matrix, the theorem also determines the nilpotent tridiagonal sign matrices. We further show that the $(1,1)$ entry of the resolvent of a nilpotent $T_m(u)$ is $\lambda^{-1} \pm \lambda^{-3} \pm \lambda^{-7} \pm \dots \pm \lambda^{-(2^K - 1)}$, with signs that determine $u$. The proof of the main theorem has been formalised in Lean~4.
- [14] arXiv:2611.25331 [pdf, html, other]
-
Title: The Semi--Fibonacci Partition TreeSubjects: Combinatorics (math.CO); Number Theory (math.NT)
In this work, we introduce a binary tree in which every semi-Fibonacci partition appears exactly once. The left--right address of a vertex gives an explicit formula for the parts of the corresponding partition and encodes statistics such as the largest $2$-adic valuation among its parts. We construct a sign-reversing involution that refines Andrews's parity theorem by determining the difference between the numbers of partitions of a given integer at even and odd depths. Inspired by properties of the Calkin--Wilf tree, we study several parameters of our tree and use them to obtain new results on semi-Fibonacci partitions. We also derive generating functions for partition statistics and determine the average and extremal partition sizes at each level.
- [15] arXiv:2611.25346 [pdf, html, other]
-
Title: A complete intersection theorem for sets of bounded sizeComments: 14 pagesSubjects: Combinatorics (math.CO)
Let \(1\le t\le k\le n\) and \(2k<n+t\). We prove that a largest \(t\)-intersecting family of subsets of \([n]\) of size at most \(k\) is obtained by taking all such subsets that contain at least \(t+r\) points of a fixed \((t+2r)\)-element set, for some \(0\le r\le\left\lfloor\frac{n-t}{2}\right\rfloor\). This settles a conjecture of Ahlswede, Bey, Engel and Khachatrian from 2002.
- [16] arXiv:2611.25381 [pdf, html, other]
-
Title: Strong chromatic index of graphs with Ore-degree at most nineSubjects: Combinatorics (math.CO)
The strong chromatic index $\chi_s^{\prime}(G)$ of a graph $G$ is the minimum number of colors in an edgecoloring in which distinct edges at distance at most two in the line graph receive different colors. Let $\theta(G)=\max _{x y \in E(G)}\left(d_G(x)+d_G(y)\right)$ denote the maximum edge weight, also called the Ore-degree, of $G$. We prove that every finite loopless multigraph $G$ with $\theta(G) \leq 9$ satisfies $\chi_s^{\prime}(G) \leq 28$. For simple graphs, this improves the direct greedy bound from 32 to 28. In particular, it verifies the Erdős-Nešetřil conjecture for simple graphs of maximum degree five whose vertices of degree five form an independent set, using one fewer color than the conjectured bound of 29. When $\theta(G)=9$, our bound is four colors above the bound of 24 predicted by the Ore-degree conjecture of Chen, Huang, Yu, and Zhou.
- [17] arXiv:2611.25447 [pdf, html, other]
-
Title: Note on the random triadic process IISubjects: Combinatorics (math.CO)
For a fixed integer $r\geqslant 3$, the random $r$-generalized triadic process starts from a minimum weakly $K_r$-saturated graph, namely the complete $(r-1)$-partite graph $K_{1^{r-2},n-r+2}$ with $r-2$ singleton parts and one part of size $n-r+2$. At each step of the process a new edge $\boldsymbol{e}$ is added with probability $p$, provided there exists a copy of $B_{r-2}$ in $K_n$ for which $\boldsymbol{e}$ is its spine and the only edge that has not yet been added to the current graph, where $B_{r-2}$ denotes a triangular book graph consisting of $r-2$ triangles sharing a single common edge known as the spine of the book. When $r=3$, this is the random triadic process. Korándi et al. proved a sharp threshold probability ${p}= \frac 12n^{ - \frac 12}$ for the propagation of the random triadic this http URL and Yang complemented those results by considering the final size of the random $r$-generalized triadic process when ${p}=o( n^{- \frac 12}\log^{ \alpha(3-r)} n)$ for any fixed constant $\alpha> \frac 12$.In this note, we further consider the sharp threshold probability $\tilde{p}_r$ for the propagation of the random $r$-generalized triadic process when $r\geqslant 4$. We prove that $\frac 12 n^{- \frac 12}<\tilde{p}_r\leqslant c\, n^{- \frac 12}\log^{ \frac 12} n$ for some positive constant $c$, and conjecture that $\tilde{p}_r= c_r\, n^{ - \frac 12}$, where $c_r= \frac 12(r-2)!^{ \frac{1}{2r-4}}\bigl( \frac{2r-5}{r-2}\bigr)^{ \frac{2r-5}{2r-4}}$.
- [18] arXiv:2611.25505 [pdf, html, other]
-
Title: Fixed-opening-set positivity for perfect matchingsComments: 32 pagesSubjects: Combinatorics (math.CO)
For a perfect matching $M$ on $[2n]$, let $P_M$ be the interval order on its edges and let $\operatorname{Open}(M)$ be the set of smaller endpoints of its edges. For an opening set $O$ that occurs for some matching, put $S_O=\sum_{\operatorname{Open}(M)=O}X_{\operatorname{Inc}(P_M)}$ and $H_O=\omega S_O$. We give explicit Schur and power-sum expansions of $H_O$ with nonnegative integer coefficients, and prove that $H_O$ is $h$-positive (equivalently, $S_O$ is $e$-positive). The Schur coefficients count standard tableaux of staggered skew shapes with prescribed entries in the left cells of distinguished dominoes. The Schur expansion follows from a Jacobi--Trudi sign-reversing involution on arrays with prescribed opener positions. For every partition $\mu$ of $n$, a coefficient-transfer formula expresses $[h_\mu]H_O$ as a positive scalar multiple of an elementary coefficient of the chromatic symmetric function of a clique blow-up of a path. This graph is a unit interval graph, so Hikita's theorem gives nonnegativity. The power-sum coefficients admit a cycle-type autocorrelation formula in terms of the restricted permutations from the Ferrers threshold model and an interpretation by alternating permutations with prescribed valley values and record partitions; we also obtain explicit threshold formulas. Further results include descent-set refinements, formulas for selected $h$-coefficients, and a rim-hook cancellation for the coefficient of $h_n$. These results refine the global matching identity of Amdeberhan, Shareshian, and Stanley.
- [19] arXiv:2611.25516 [pdf, html, other]
-
Title: Rational Designs and Prouhet--Tarry--Escott ProblemsComments: 56 pagesSubjects: Combinatorics (math.CO); Metric Geometry (math.MG); Number Theory (math.NT)
For every strength, we prove the existence of rational designs on spheres, orthogonal and unitary groups, real and complex Grassmannians, and ellipsoids that are defined by positive-definite quadratic forms with rational coefficients and have a rational point. This answers Bannai's Problem for these spaces, solves the problem of Cui--Xia--Xiang on rational spherical $4$-designs on the unit circle, and proves Xiang's conjecture in the stronger form of existence in every dimension. To this end, we introduce the $(G,\mathcal{S})$-Prouhet--Tarry--Escott problem for an abelian group $G$ and a finite set of characters $\mathcal{S}$ and develop its existence and minimality theory. We also prove a general theorem transforming integer-weighted rational designs into equi-weighted designs on distinct rational points. On the unit circle $\mathbb{S}^1$, we determine the minimum sizes of rational spherical designs of strengths $4,5,6,7$ and show that they are respectively $2304,4608,9216,9216$. We also show that the minimum size of a rational spherical $5$-design on $\mathbb{S}^2$ is $192$. We further apply our framework to prove a conjecture of Thuswaldner--Ziegler on sums of distinct units and to answer Mahabaduge's problem on convex equilateral lattice polygons affirmatively.
- [20] arXiv:2611.25544 [pdf, html, other]
-
Title: Distance-hereditary split graphs whose second largest eigenvalue does not exceed 1Comments: 28 pages, 5 figuresSubjects: Combinatorics (math.CO)
The gem is obtained by joining a vertex to every vertex of a path on four vertices. A distance-hereditary split graph is a split graph containing no induced gem. In this paper, we characterize all connected distance-hereditary split graphs whose second largest eigenvalue does not exceed 1 and determine the multiplicity of the eigenvalue 1. Our result extends previous results on threshold graphs whose second largest eigenvalue does not exceed 1.
- [21] arXiv:2611.25559 [pdf, html, other]
-
Title: k-trees with second largest eigenvalue at most oneSubjects: Combinatorics (math.CO)
The problem of characterizing graphs whose second largest adjacency eigenvalue is at most $1$ was posed by Hoffman and first studied by Cvetković in 1982. In this paper, all $k$-trees with second largest eigenvalue at most $1$ are characterized. We determine all equality cases and the multiplicity of the eigenvalue $1$. For each fixed $k\geq2$, we also determine the $k$-trees attaining the largest second largest eigenvalue below $1$ and the smallest above $1$. Finally, we determine all minimal forbidden induced subgraphs among $k$-trees with $k\geq 1$, each of which has second largest eigenvalue greater than $1$, but deleting any vertex gives a graph whose second largest eigenvalue is at most $1$.
- [22] arXiv:2611.25662 [pdf, html, other]
-
Title: Positive semidefiniteness of random submatricesComments: 11 pagesSubjects: Combinatorics (math.CO); Probability (math.PR)
Given a symmetric matrix $A \in [-1,1]^{n \times n}$, we estimate the probability that a random principal submatrix, obtained by taking each index independently with probability $p$, is positive semidefinite. As a corollary, we show that $O(\varepsilon^{-1})$ indices chosen uniformly at random suffice for testing positive semidefiniteness with squared Frobenius distance threshold $\varepsilon n^2$, thus nearly matching the lower bound of Bakshi, Chepurko, and Jayaram (``Testing Positive Semi-Definiteness via Random Submatrices'', FOCS 2020). The key ingredient is a dense model lemma for positive semidefinite matrices, proved using the hyperplane separation theorem and a contraction inequality for Rademacher random variables.
- [23] arXiv:2611.25684 [pdf, html, other]
-
Title: A sharp bounded bijection for tight cylindric partitionsComments: 9 pagesSubjects: Combinatorics (math.CO); Number Theory (math.NT)
Fix a cyclic profile of coprime rank $r$ and level $\ell$, both at least three, and an entry bound $n\ge1$. Let $d$ be the deficit from the maximum volume of a tight cylindric partition. For $d\le n\min(r,\ell)$, the one-row combinatorial $R$ matches the tight cylinders whose last slice lies inside the maximizer's last slice with the partitions of $d$ in which each part occurs fewer than $r$ times. The inverse preserves the profile and entry bound. We identify every partition missed at the next deficit. A prefix test decides whether any cylinder lies outside this sector and, if so, identifies the unique one of least deficit. This explains the leading coefficient gap in Warnaar's $Q_{n,c}$. We also determine the first correction to the vertex terms of the published bounded determinant.
- [24] arXiv:2611.25685 [pdf, html, other]
-
Title: Extremal spectral results of outerplanar graphs without starlike treesComments: 18Subjects: Combinatorics (math.CO)
A graph $G$ is $F$-free if it does not contain $F$ as a subgraph. Let $\operatorname{SPEX}_{\mathcal{OP}}(n,F)$ denote the set of $n$-vertex $F$-free outerplanar graphs with maximum spectral radius. Define $S(l_1,l_2,\ldots,l_t)$ as the starlike tree obtained from $t$ vertex-disjoint paths of lengths $l_1,l_2,\ldots,l_t$ by identifying one endpoint of each path, and $C_{l_1,l_2,\ldots,l_t}$ as the graph obtained from $t$ vertex-disjoint cycles of lengths $l_1,l_2,\ldots,l_t$ by identifying one vertex from each cycle. When $l_1=l_2=\cdots=l_t=l$, we abbreviate these graphs as $S(t\cdot l)$ and $C_{t\cdot l}$, respectively. Previous results determined $\operatorname{SPEX}_{\mathcal{OP}}(n,S(t\cdot l))$ for $t\ge4$ [Graphs Combin. 42 (2026) 80] and for $t=3$, in each case for sufficiently large $n$. For $C_{l_1,l_2,\ldots,l_t}$, the corresponding extremal graphs are known for $t=2$ and sufficiently large $n$. The sets $\operatorname{SPEX}_{\mathcal{OP}}(n,C_{t\cdot l})$ were also determined for sufficiently large $n$ [Discrete Math. 349 (2026) 114673]. In this paper, we determine $\operatorname{SPEX}_{\mathcal{OP}}(n,S(l_1,l_2,\ldots,l_t))$ for sufficiently large $n$ when the branch lengths are not all equal. Our result for $t\ge4$ also includes equal branch lengths. As applications, we determine $\operatorname{SPEX}_{\mathcal{OP}}(n,C_{l_1,l_2,\ldots,l_t})$ for arbitrary cycle lengths and sufficiently large $n$. We also determine $\operatorname{SPEX}_{\mathcal{OP}}(n,F)$ for certain linear forests $F=\bigcup_{i=1}^tP_{l_i}$ and sufficiently large $n$. Finally, we apply our main theorems to obtain the known results on outerplanar graphs forbidding matchings or theta graphs for sufficiently large $n$.
- [25] arXiv:2611.25715 [pdf, html, other]
-
Title: Real Principal-Minor Detectors: Normal Forms and Regular Parity LiftsComments: 19 pagesSubjects: Combinatorics (math.CO)
Let $A$ be a symmetric matrix over $\mathbb{F}_2$ on a finite index set, and let $t$ be the column of diagonal entries of $A$, viewed over $\mathbb{R}$. A real detector of $A$ is a real matrix whose principal minors equal the integer $0/1$ representatives of the corresponding principal minors of $A$. We prove that $A$ has a real detector if and only if it has one of the form $K+tt^T$, with $K$ skew-symmetric and $\{0,\pm1\}$-valued. These conditions are equivalent to the existence of a principally unimodular skew-symmetric signing of the bordered lift matrix of $A$, and to regularity of the parity lift of its delta-matroid. If the graph on the nonempty index set of $A$, with edges given by its nonzero off-diagonal entries, is connected, every real detector of $A$ is diagonally similar to a detector of this form. The proof uses cut-transposes to preserve the prescribed symmetric part up to diagonal similarity, then applies feasible singleton pivots to a minimal counterexample. For ribbon bouquets, the characterization proves Whistler's conjecture. For every $A$ with a real detector, the feasible-set generating polynomial is Hurwitz stable, and the polynomial counting feasible sets of sizes $2i-1$ or $2i$ by $i$ has only strictly negative real zeros and ultra-log-concave coefficients.
- [26] arXiv:2611.25727 [pdf, html, other]
-
Title: Fourier bases for square-order Paley graphsComments: 14ppSubjects: Combinatorics (math.CO); Number Theory (math.NT)
Let $q$ be an odd prime power and consider the Paley graph $P(q^2)$ on the finite field $\mathbb{F}_{q^2}$. A well-known optimal eigenfunction of this graph is supported on the norm-one subgroup, where it takes the values $1$ and $-1$ on the two cosets of its subgroup of index two. Its support has the minimum possible size $q+1$. Starting from this eigenfunction, we construct a family of multiplicative translates and prove that they form a basis of the space of complex-valued functions on $\mathbb{F}_{q^2}^{\times}$. After extending these functions to the whole field, the translates indexed by squares form a basis of one nonprincipal eigenspace of the Paley graph, while those indexed by nonsquares form a basis of the other. In particular, both nonprincipal eigenspaces admit bases consisting entirely of optimal eigenfunctions. The main ingredient is a multiplicative Fourier analysis of the shifted eigenfunction. We determine the moduli of all its Fourier coefficients and, in particular, show that none of them vanishes.
- [27] arXiv:2611.25741 [pdf, html, other]
-
Title: Beyond geometric lattices: pseudo-atoms and redundant join representations in the face lattice of the permutohedronComments: 27 pagesSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
We study the lattice obtained from the poset of ordered set partitions (the Fubini poset), ordered by merging adjacent blocks, by adjoining a bottom element of rank -1. It is the face lattice of the permutohedron. We look at it from the point of view of geometric lattices: it is graded, atomic and coatomic in the strong sense that every element is a meet of coatoms, but it is not semimodular. Its atoms are the $n!$ permutations, and its elements of rank one, which we call pseudo-atoms, are the edges of the permutohedron. Describing ordered set partitions by chains of subsets, the cuts, we show that the rank is modular whenever the meet is above $\bot$, while the join of two distant atoms can have large rank, so that the rank of the join is a metric on permutations. An element has a unique representation as a join of atoms only up to rank one; above it, irredundant representations have sizes ranging from two to the rank, and the redundancy of an element is its number of atoms minus two. The Möbius function is that of an Eulerian lattice, the Whitney numbers are the face numbers of the permutohedron, and the characteristic polynomial has the alternating coefficients of the geometric case, but only $\bot$ and $\top$ are left-modular, so the lattice is not supersolvable. We show that it is CL-shellable, we exhibit EL-labelings for $n\le5$, and we compare the independent sets of Raz arXiv:2307.05005 (v3, Jan. 2026) with irredundant families and with the matroid of the vertices of the permutohedron. Replacing ordered set partitions by partial flags of subspaces of $\mathbb F_q^n$ gives a $q$-analogue, whose Möbius function is $(-1)^{\mathrm{rk}+1}q^{\kappa}$, with $\kappa$ the number of pairs of elements in a common block at $q=1$, and whose characteristic polynomial and Betti numbers are polynomials in $q$.
- [28] arXiv:2611.25785 [pdf, html, other]
-
Title: Coxeter Group Symmetries of Frieze PatternsComments: 12 pages, 2 figuresSubjects: Combinatorics (math.CO); Representation Theory (math.RT)
Coxeter group symmetries of frieze patterns are investigated through their relation to $2\times n$ matrices and the associated Plücker coordinates. For odd order $n$, the symmetric group acts on the set of friezes, while for even $n$, the dihedral subgroup acts. We further show that a larger group acts when $n = 6$.
- [29] arXiv:2611.25850 [pdf, html, other]
-
Title: Weak Degeneracy with Availability for Planar GraphsComments: 30 pages, 3 figuresSubjects: Combinatorics (math.CO)
Every planar graph admits exponentially many proper colorings for any assignment of lists of five allowed colors to its vertices. In this paper, we show that very little beyond degeneracy is needed to prove that this statement holds. In particular, given a planar graph G (but not the list assignment), our argument provides an algorithm consisting entirely of instructions of the following form: ``Color the vertex v using any color c from its list, and remove c from the lists of neighbors of v.'' and ``For the edge uv, choose any k colors from the list of u, then color v by any color c from its list that does not appear among these k colors, and remove c from the lists of neighbors of v.'' For every assignment of lists of size five to vertices of G, following this algorithm in all possible ways guarantees that at least $2^{|V(G)|/7}$ different proper colorings of G are produced (and at least one color choice is guaranteed to be available in each step). We also show that this result has the following consequence: for every planar graph G, there exists a set $R\subseteq V(G)$ of size at least 0.06|V(G)| such that G can be properly colored from any assignment of lists of size four to vertices in R and lists of size five to the rest of vertices of G. Moreover, these statements remain true even in stronger settings, such as for correspondence coloring.
- [30] arXiv:2611.25893 [pdf, html, other]
-
Title: A very robust Ramsey theorem for hypergraph matchingsComments: 15 pagesSubjects: Combinatorics (math.CO)
A fundamental result in Ramsey theory due to Alon, Frankl and Lovász gives an exact formula for the $q$-colour Ramsey numbers of matchings in $r$-uniform hypergraphs: if $n\ge\mathsf{AFL}_r(\mathbf{t})=(r-1)\|\mathbf{t}\|_\infty+1+\sum_{j=1}^q(t_j-1)$ then in any $q$-edge-colouring of $K^r_n$ there is some colour $j$ with a matching of size $t_j$. We show that a very weak quasirandomness assumption suffices for this Ramsey property: we can replace $K^r_n$ by any $r$-graph $H$ on at least $\mathsf{AFL}_r(\mathbf{t})+o(n)$ vertices that is a sublinear connector, meaning that it has no balanced $r$-partite holes of linear size. This generalises the result for $r=2$ (ordinary graphs) that we proved previously using a compression algorithm based on Gallai-Edmonds decompositions. This structure theory is unavailable in the hypergraph setting, so we combine two other proof methods, namely (a) simultaneous optimisation in all colours by clustering vertices using fractional cover weights from LP duality, and (b) local-to-global structure via random sampling and Kahn's matching theorem.
- [31] arXiv:2611.25956 [pdf, html, other]
-
Title: Schubert Calculus in the Eye of the StormComments: 37 pagesSubjects: Combinatorics (math.CO)
We introduce new combinatorial objects, called storm diagrams, to study the torus-equivariant quantum $K$-theory of complete flag varieties $GL_n(\mathbb{C})/B$. We consider the quantum product of an arbitrary Schubert class with a modified Hirzebruch $\lambda_y$-class of a tautological subbundle. We show that its Schubert expansion coefficients are given by the total weights of storm diagrams. As applications, we establish Pieri rules for the torus-equivariant quantum $K$-theory of partial flag varieties $GL_n(\mathbb{C})/P$. Our storm diagrams provide the first combinatorial model for a manifestly positive multiplication formula for partial flag varieties beyond the Chevalley case, with restrictions imposed on only one of the two Schubert classes.
- [32] arXiv:2611.25973 [pdf, html, other]
-
Title: Proof of Stanley's Conjecture on the Leading Ehrhart Coefficients of the Birkhoff PolytopeSubjects: Combinatorics (math.CO)
Let $c(n,k)$ denote the coefficient of $r^{(n-1)^2-k}$ in the Ehrhart polynomial of the $n\times n$ Birkhoff polytope. For every fixed nonnegative integer $k$, we prove that $c(n,k)/c(n,0)\sim n^{3k}/(2^k k!)$ as $n\to\infty$, confirming a conjecture of Stanley.
- [33] arXiv:2611.26034 [pdf, html, other]
-
Title: Stars and paths in oriented graphsComments: 22 pagesSubjects: Combinatorics (math.CO)
Let $\overrightarrow{F}$ be a fixed oriented graph. Its oriented Turán number, written $\exo(n,\overrightarrow{F})$, is the largest size of an $n$-vertex oriented graph with no copy of $\overrightarrow{F}$. This parameter extends the classical notion of Turán number to oriented graphs. In this paper, we investigate the supersaturation results for the directed path $P_k~(k\geq 2)$ and all oriented stars $\overrightarrow{S}_{p,q}~(0\leq p\leq q$), and all oriented paths of order at most four.
- [34] arXiv:2611.26037 [pdf, html, other]
-
Title: An improved Moore bound for girths seven and elevenComments: 23 pages, 4 figuresSubjects: Combinatorics (math.CO)
Let $n(d,k)$ be the minimum number of vertices of a graph of minimum degree $d$ and girth at least $g=2k+1$. A simple counting argument gives the classical lower bound $n(d,k)\ge m(d,k)=1+d\sum_{i=0}^{k-1}(d-1)^i$, known as the Moore bound and dating back at least to 1960. Apart from complete graphs and odd cycles, graphs attaining this lower bound can exist only for girth $5$ and degrees $3,7$ and $57$ (Hoffman and Singleton 1960; Bannai and Ito 1973; Damerell 1973). Nevertheless, for more than sixty years this lower bound has not been substantially improved beyond an additive constant. For $k\geq 3$, i.e. girth at least $7$, the best general bound was $n(d,k)\ge m(d,k)+2$, due to Bannai and Ito (1981). We show that for fixed girth $7$ and growing degree $d$ we have $n(d,3)\ge m(d,3)+(1-o(1))d/8$. Furthermore, for girth $11$ we have $n(d,5)\ge m(d,5)+\Omega(d^{3/5})$. In particular, the excess $n(d,k)-m(d,k)$, for $k\in\{3,5\}$, tends to infinity with $d$ and is therefore generally unbounded, which answers a question of Bollobás from 1978. For the degree/diameter problem we obtain similar bounds. A graph of maximum degree $d$ and diameter $3$ or $5$ has at most $m(d,3)-\Omega(\sqrt{d})$ or $m(d,5)-\Omega(d^{3/10})$ vertices, respectively. This answers a question of Bermond and Bollobás from 1981: for every constant $c$ there are $d$ and $k$ such that every graph of maximum degree $d$ and diameter $k$ has at least $c$ fewer vertices than the Moore bound.
- [35] arXiv:2611.26110 [pdf, html, other]
-
Title: Hilbert functions over the exterior algebra and f-vectors in higher rank III: Lattice points of the Kozlov polytopeComments: 63 pages, 11 figures. Parts I and II are arXiv:2609.23605 and arXiv:2610.14985. Much of the paper is formalised in Lean 4 with Mathlib (no sorry, no extra axioms; marks in the margin say which results). Lean files, code and run logs: this https URL and DOI https://doi.org/10.5281/zenodo.24288404Subjects: Combinatorics (math.CO)
Let $E$ be the exterior algebra on $n$ generators and $F=\bigoplus_{i=1}^r Eg_i$ a graded free $E$-module with $°g_i=d_i$. Part I of this series identified the convex hull of the Hilbert functions of the quotients $F/M$, $M$ a proper monomial submodule, as the Kozlov polytope $\mathrm{Koz}(n;\mathbf{d})$, a Minkowski sum of shifted Kozlov simplices, and described its vertices at rank two, conjecturing its facets there; Part II counted the Hilbert functions. Here we study the lattice points of the polytope. We show that the Kozlov simplex $\mathrm{Koz}(n)$ is a lecture hall simplex and that every point of $\mathrm{Koz}(n;\mathbf{d})$ has a unique chained decomposition into points of $\mathrm{Koz}(n)$. Hence the lattice points of $\mathrm{Koz}(n;\mathbf{d})$ are exactly the sums of shifted lattice points of $\mathrm{Koz}(n)$, the polytope has the integer decomposition property, every lattice point is a Hilbert function when $n\le 3$, and lattice-point counts and Ehrhart polynomials are products of transfer matrices of the kind used in Part II. We determine the codegree of every Kozlov polytope and show that none is Gorenstein for $n\ge 3$. Finally we compare discrete and continuous invariants: the number of Hilbert functions against the volume and the lattice-point count, where we prove Kupreyeva's observed limit for the fraction of lattice points that are $f$-vectors and extend it to every rank. We also compare the centroid and second moments of the Hilbert functions with those of the polytope.
- [36] arXiv:2611.26130 [pdf, html, other]
-
Title: Maximum signless Laplacian spectral radius of graphs with given minimum degree and edge connectivityComments: Any comments and suggestions are welcomeSubjects: Combinatorics (math.CO)
Let $G$ be a simple connected graph of order $n$ with minimum degree $\delta$ and edge connectivity $k$. Recently, in [Linear Algebra Appl. 751 (2026) 318-330], Zhao, Ye, and Fan characterized the extremal graph with maximum signless Laplacian spectral radius among all graphs of order $n$ with minimum degree $\delta$ and edge connectivity $k$ when $n \geq \delta^2+4\delta+3$ and $k \in \{0,1,2\}$, and proposed the corresponding problem for $3 \leq k \leq \delta-1$. In this paper, we solve the problem for the entire range $0 \leq k \leq \delta-1$ and completely remove the order restriction. Specifically, we prove that $$ q(G) \leq q(B_{n,n-\delta-1}^{k}), $$ with equality if and only if $G \cong B_{n,n-\delta-1}^{k}$, where $B_{n,n-\delta-1}^{k}$ is the graph obtained from $K_{n-\delta-1} \cup K_{\delta+1}$ by adding $k$ edges joining a single vertex of $K_{n-\delta-1}$ to $k$ distinct vertices of $K_{\delta+1}$.
- [37] arXiv:2611.26189 [pdf, html, other]
-
Title: Optimal Radius Ratio of Compact Nonuniform PackingsComments: 31 pages, 11 figuresSubjects: Combinatorics (math.CO); Metric Geometry (math.MG); Optimization and Control (math.OC)
We study the ratio of the smallest to the largest radius in a nonuniform disk packing whose tangency graph triangulates the plane. We give a computer-assisted proof that the largest possible ratio is $s=0.651050185882609\ldots$, attained uniquely up to similarity by packing~53 of Fernique, Hashemi, and Sizova. In fact, every nonuniform packing with radius ratio at least $0.65105$ is similar to this packing. No periodicity or restriction on the number of radii is assumed; the radii are required only to have a positive infimum and a finite supremum. Following the finite-subgraph exclusion program of Connelly and Zhang, we first restrict the degree-five flowers and their pairings. The remaining exceptional degree-seven corona forces seventeen complete flowers on an unfolded disk with thirty-seven labels. An exact interval certificate excludes their angle equations. A comparison of logarithmic radii on a recurrent network then forces the radii and the three local degree words. We identify the entire triangulation by reducing these words to the square--octagon tiling and showing that its decoration is forced.
- [38] arXiv:2611.26226 [pdf, html, other]
-
Title: The existence of generalized Steiner systemsSubjects: Combinatorics (math.CO)
A generalized Steiner system $GS(t,w,n,q)$ is a $q$-ary constant-weight code of length $n$ and weight $w$ that has minimum distance at least $2(w-t)+1$ and attains the Johnson-type upper bound $(q-1)^t\binom nt/\binom wt$. For strengths $t=1$ and $t=2$, such systems were known to exist for all sufficiently large lengths satisfying the necessary divisibility conditions. For general fixed parameters, Liu and Shangguan (J. Combin.\ Theory Ser.~A 209 (2025), 105955) proved that the Johnson-type bound is attained asymptotically, and asked whether it is attained with equality for all sufficiently large lengths satisfying these conditions. We answer this question affirmatively. We prove that, for fixed integers $q\geq3$ and $w>t\geq1$, a $GS(t,w,n,q)$ exists for every sufficiently large $n$ such that $\binom{w-i}{t-i}$ divides $(q-1)^{t-i}\binom{n-i}{t-i}$ for all $0\leq i<t$. Moreover, the system can be chosen so that the supports of distinct codewords intersect in at most $t$ coordinates. Our proof assigns an independent random labelling to every set of $t+1$ coordinates, which turns large support intersections into conflicts in an exact covering problem, and then applies Keevash's decomposition theorem for labelled complexes.
- [39] arXiv:2611.26229 [pdf, html, other]
-
Title: Sharp topological overlap in every dimensionSubjects: Combinatorics (math.CO); Computational Geometry (cs.CG)
For a positive integer $d$ let $c_d^{\mathrm{top}}$ (resp. $c_d^{\mathrm{aff}}$) be the maximum $c$ such that, for every continuous (resp. affine) map from the $n$-dimensional simplex $\Delta^n$ to $\mathbb{R}^d$, some point of $\mathbb{R}^d$ lies in the images of at least $(c-o(1))\binom{n+1}{d+1}$ of the $d$-dimensional faces, as $n\to\infty$. We show that \[
c_d^{\mathrm{top}}=c_d^{\mathrm{aff}}=\frac{(d+1)!}{(d+1)^{d+1}}. \] The second equality confirms a conjecture of Bukh, Matoušek, and Nivasch, who established the upper bound.
The proof was found by GPT-6 Astra, following the directions of the author. - [40] arXiv:2611.26253 [pdf, html, other]
-
Title: Combinatorial Dvoretzky TheorySubjects: Combinatorics (math.CO); Metric Geometry (math.MG)
Let $P \subset \mathbb{R}^n$ be an $n$-dimensional polytope such that $P \subset B_2^n$. Let $M^*(P)$ denote its mean width, and let $N$ be the number of facets (faces of dimension $n-1$) of $P$. We prove the following two bounds:
(1) If $N \leq e^n$, then \[ M^*(P) \leq 1 - \frac{c}{\log^2(\frac{N}{n})}. \]
(2) For arbitrary $N$, \[ M^*(P) \leq 1 - \frac{c}{n}N^{-\frac{2}{n-1}}. \]
In both bounds, $c>0$ is an absolute constant. - [41] arXiv:2611.26259 [pdf, html, other]
-
Title: An asymptotic bound for Yuster's independent transversal factor conjectureSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
An $[r,n,1]$-graph has $r$ independent parts of size $n$, with a matching between each pair of parts. Yuster conjectured in 2021 that every such graph has a partition into independent transversals whenever $n\ge 2\lceil r/2\rceil$. We prove that there is an absolute constant $A>0$ such that, for all sufficiently large $r$, this partition exists whenever $n\ge\lceil r+A r^{20/21}\rceil$. Thus $f(r)\le r+O(r^{20/21})$, where $f(r)$ is the least $n_0$ such that every $[r,n,1]$-graph has such a partition whenever $n\ge n_0$. In particular, $f(r)/r\to1$, giving an asymptotic form of the conjecture.
- [42] arXiv:2611.26277 [pdf, html, other]
-
Title: Dense induced bipartite subgraphs under local sparsitySubjects: Combinatorics (math.CO)
The study of dense induced bipartite subgraphs dates back to the work of Erdős, Faudree, Pach, and Spencer on triangle-free graphs. In this paper, we study this problem under different local sparsity conditions. First, we prove that for every fixed integer $t\ge 2$ and all sufficiently large $d$, every $K_{t,t}$-free graph of minimum degree at least $d$ contains an induced bipartite subgraph of average degree at least $\log d-16t\log\log d$. This follows from our bound $\chi_f(G)\le d/(\log d-16t\log\log d)$ for every $d$-degenerate $K_{t,t}$-free graph $G$, which answers a problem of Allen, Dhawan, and Noel. For triangle-free $d$-degenerate graphs $G$, we prove that $\chi_f(G)\le(2.85+o(1))d/\log d$, improving the leading constant 4 in the bound of Martinsson and Steiner. So every triangle-free graph of minimum degree at least $d$ contains an induced bipartite subgraph of average degree at least $(20/57-o(1))\log d$. We also extend the study of a conjecture of Esperet, Kang, and Thomassé to graphs containing triangles. We prove that if $G$ has minimum degree at least $d$ and each edge belongs to at most $d/k^2$ triangles, where $k=\lfloor\log d/\log\log d\rfloor$, then $G$ contains an induced bipartite subgraph of average degree $\Omega(\log d/\log\log d)$.
- [43] arXiv:2611.26280 [pdf, html, other]
-
Title: Rainbow Matchings in $K_{r+1}$-free GraphsComments: 26 pagesSubjects: Combinatorics (math.CO)
Let $n,m,r$ be positive integers with $n\ge 2m+2$, where $n$ is sufficiently large relative to $r$. Alon and Frankl determined the maximum number of edges in an $n$-vertex graph containing neither $K_{r+1}$ nor a matching of size $m+1$. In this paper, we establish a rainbow analogue of their result. More precisely, if $G_1,\ldots,G_{m+1}$ are $K_{r+1}$-free graphs on a common vertex set of size $n$, each having more than $\operatorname{ex}(n,\{K_{r+1},M_{m+1}\})$ edges, then $\{G_1,\ldots,G_{m+1}\}$ admits a rainbow matching.
- [44] arXiv:2611.26330 [pdf, html, other]
-
Title: Equality in the clique bound for critical graphsSubjects: Combinatorics (math.CO)
A graph is $k$-critical if its chromatic number is $k$ and every proper subgraph is $(k-1)$-colorable. Gao and Ma (2023) proved that every $n$-vertex $k$-critical graph with $n > k \ge 4$ contains at most $n - k + 3$ cliques of size $k - 1$, and asked which graphs attain this bound. We answer this question by showing that equality holds if and only if $n - k + 3$ is odd and the graph is isomorphic to the join of a complete graph on $k - 3$ vertices and a cycle of length $n - k + 3$. More generally, for $n>k\ge3$, we determine when the size of a nonempty family of distinct $(k-1)$-cliques in an $n$-vertex $k$-critical graph attains the upper bound $s-k+3$, where $s$ is the number of vertices covered by the family. Equality holds if and only if the graph is such a join (with the complete part empty when $k = 3$) and the family consists of all its $(k-1)$-cliques.
- [45] arXiv:2611.26397 [pdf, html, other]
-
Title: Hook histories and a two-parameter Murnaghan--Nakayama rule for dual canonical Grothendieck functionsComments: 37 PagesSubjects: Combinatorics (math.CO); Representation Theory (math.RT)
We establish a two-parameter Murnaghan--Nakayama rule for power-sum multiplication in the dual canonical stable Grothendieck basis. The coefficients admit a closed boundary product formula and a signed combinatorial description by hook histories. We determine their exact support and prove an exact divisibility law for off-diagonal coefficients governed by the edge-connected components of the indexing skew diagram. We also obtain a hook expansion of power sums, an explicit binomial reduction to the dual stable rule, and a Grassmannian $K$-homological interpretation of the one-parameter specialization. Finally, we deduce complementary rules for power-sum multiplication in the canonical basis and the corresponding lowering operation in the dual canonical basis.
- [46] arXiv:2611.26429 [pdf, html, other]
-
Title: Algebraic matroids with non-algebraic duals exist in any positive characteristicSubjects: Combinatorics (math.CO); Algebraic Geometry (math.AG)
We show that for every field $K$ of positive characteristic there exists an algebraic matroid $M$ over $K$ such that the dual matroid $M^*$ is not algebraic over any field. Our conceptual proof relies on the theory of matroids over one-dimensional algebraic groups. As an application, we deduce that the classes of supports of realizable volume polynomials and of realizable covolume polynomials differ in positive characteristic.
- [47] arXiv:2611.26439 [pdf, html, other]
-
Title: An operator $b$-positivity conjecture for Jack charactersComments: 11 pagesSubjects: Combinatorics (math.CO)
Goulden and Jackson defined a Jack deformation $a_{\mu\nu}^\lambda(\alpha)$ of the connection coefficients of the symmetric group and conjectured that these were polynomials in $b=\alpha-1$ with nonnegative interger coefficients. This conjecture was extended to the structure constants of (stable) Jack characters by Śniady. We formulate a stronger operator conjecture: the differential operators $\Delta_\mu(\alpha)$ that multiply by stable Jack characters should have coefficients in ${\mathbb N}[b]$ in the normally ordered Heisenberg basis $p_ID_J$. We provide numerical evidence, as well as theoretical consequences of the conjecture which can be rigorously proved. Namely, we exhibit two families of $\alpha$-shifted symmetric functions whose associated differential operators are ${\mathbb N}[b]$ positive simultaneously on the bases $p_ID_J$ and $\Delta_\mu(\alpha)$. These operators correspond to the Boolean cumulants of the Jack transition measure and to the Cartan generators of the affine Yangian $Y(\widehat{\mathfrak gl}_1)$.
- [48] arXiv:2611.26513 [pdf, html, other]
-
Title: Hypergraph Hajnal-SzemerédiComments: 26 pages plus references and appendixSubjects: Combinatorics (math.CO)
A seminal result of Hajnal and Szemerédi from 1970 asserts that every graph on $n$ vertices with $q\;|\;n$ and minimum degree at least $\Big(1-\frac{1}{q}\Big)n$ admits a $K_q$-factor (a collection of vertex-disjoint copies of $K_q$ spanning all vertices). There has been sustained interest in extending this result to hypergraph $K_q^r$-factors. For general $q$ and $r$, Lu and Székely in 2007 showed that every large enough, $r$-graph $G$ with $q\mid v(G)$ and $\delta_{r-1}(G) \ge \left(1- \frac{c}{q^{r-1}}\right)v(G)$ admits a $K_q^r$-factor (where $c$ is a constant depending on $r$ but not $q$), and there have been various subsequent improvements to the constant (but not the order) of this bound over the ensuing decades. Meanwhile, results from codegree Turán theory show that $\delta_{r-1}(G) \ge \left(1 - \frac{c \cdot \log q}{q^{r-1}} \right)v(G)$ is necessary.
Surprisingly, our main result shows that the order of this upper bound is not correct and, in fact, the codegree $K_q^r$-factor threshold is much closer to this codegree Turán theory bound. In particular, we show that $\delta_{r-1}(G) \ge \left( 1-c\cdot \frac{\log^{1-1/(r-1)}q}{q^{r-1}}\right)v(G)$ suffices for the existence of a $K_q^r$-factor. Our key contribution is showing the same is true for the fractional threshold. Inspired by the first and fourth author's recent proof of the Nash-Williams' Conjecture, we accomplish this by combining a linear programming framework with ideas from discharging. Additionally, we establish a technical result about finding large independent sets in sparse, non-uniform hypergraphs, which may be of independent interest. - [49] arXiv:2611.26539 [pdf, html, other]
-
Title: Large $k$-cross-free familiesSubjects: Combinatorics (math.CO)
Two subsets $A,B$ of a finite set $X$ are crossing if $A\cap B$, $A\setminus B$, $B\setminus A$, and $X\setminus(A\cup B)$ are all nonempty. A family is $k$-cross-free if it contains no $k$ pairwise crossing members. We construct such families on $n$ elements of size $(\frac{1}{3}+o(1))kn\log k$, where the asymptotic is taken as $k$ tends to infinity and is uniform over all integers $n\ge k$. This disproves the uniform $O(kn)$ bound conjectured by Karzanov and Lomonosov. Our construction consists of cyclic intervals with at most one point deleted, together with their complements. We also prove an $O(kn\log k)$ upper bound for $k$-cross-free families closed under all cyclic shifts of a fixed cyclic ordering of the ground set.
- [50] arXiv:2611.26556 [pdf, html, other]
-
Title: Edge cuts of bounded degree in sparse graphsComments: 5 pagesSubjects: Combinatorics (math.CO)
Every simple graph on $n \ge 2$ vertices with at most $2n-2$ edges can be split into two nonempty parts with at most two crossing edges at each vertex. For $d \ge 3$ we bound the minimum number of edges in an n-vertex graph without a d-cut.
- [51] arXiv:2611.26622 [pdf, html, other]
-
Title: Quasipolynomial pyjamasComments: 43 pagesSubjects: Combinatorics (math.CO); Dynamical Systems (math.DS); Number Theory (math.NT)
The ``pyjama stripe" $E(\varepsilon)$ is the set of all complex numbers whose real part lies within $\varepsilon$ of the nearest integer. The Pyjama Problem asks whether, for each $\varepsilon > 0$, there exists some union of finitely many rotations of $E(\varepsilon)$ about the origin that covers the plane. This was answered in the affirmative by Manners. Kravitz and Leng subsequently showed that $\exp(\exp(\exp(\varepsilon^{-O(1)})))$ rotations suffice. In this paper, we prove an upper bound of \[\exp((\log \varepsilon^{-1})^{50000})\] rotations. We also show that at least $(\pi/2 + 0.003 + o(1))\varepsilon^{-1}$ rotations are necessary, improving upon the natural lower bound of $(\pi/2 + o(1))\varepsilon^{-1}$.
New submissions (showing 51 of 51 entries)
- [52] arXiv:2611.24997 (cross-list from cs.IT) [pdf, html, other]
-
Title: There is no binary linear $[65,9,29]$ codeComments: 10 pagesSubjects: Information Theory (cs.IT); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
We prove that no binary linear $[65,9,\geqslant29]$ code exists, equivalently, that no even binary linear $[66,9,\geqslant30]$ code exists. Together with known constructions, this determines $d_2(65,9)=28$, $n_2(9,29)=66$, and $n_2(9,30)=67$. A residual-code bound and a known construction also give $d_2(122,10)=56$. To prove nonexistence, we associate with a hypothetical even code a quadratic function derived from half the codeword weight modulo $2$. Its polar form determines the fourth derivative of a Boolean function of degree at most four. Character sums, weight moments, and the exclusion of weight-$42$ codewords give upper bounds on the support of this function in seven cases. Restrictions to nondegenerate affine subspaces exclude six cases. In the remaining case, equality would force four distinct coordinate functionals to be identically $1$ on an affine seven-space, although at most two can have this property. The argument uses published minimum-length results for binary linear codes of dimensions eight and nine.
- [53] arXiv:2611.25011 (cross-list from cs.LG) [pdf, html, other]
-
Title: Near-Quadratic Sample Compression for All VC ClassesYang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Shay Moran, Grigoris Velegkas, Di Wang, Manfred K. WarmuthSubjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO); Machine Learning (stat.ML)
The sample compression conjecture is a longstanding open problem in learning theory, originating in the work of Littlestone and Warmuth in the 1980s. At its heart is a connection between simplification and generalization: if a predictor consistent with a training sample is defined using only a small part of that sample, then it is likely to generalize. Sample compression schemes formalize this idea, and many natural learning algorithms can be analyzed this way.
The sample compression conjecture of Floyd and Warmuth (1995) asserts that every binary concept class of VC dimension $d$ admits a sample compression scheme of size $O(d)$; a weaker conjecture asks only for size polynomial in $d$. Both have remained open: the first bound depending only on $d$, due to Moran and Yehudayoff (2016), is exponential in $d$. We prove the weaker conjecture by constructing a sample compression scheme of size $O(d^2 \log^2 d)$. - [54] arXiv:2611.25042 (cross-list from math.GT) [pdf, html, other]
-
Title: A census of alternating tanglesComments: 22 pages, 8 figures, 2 tablesSubjects: Geometric Topology (math.GT); Combinatorics (math.CO)
We give a census of the roughly 10 billion prime, connected, alternating tangles with at most 14 crossings. Along the way, we prove analogs of the Tait conjectures for alternating tangles and observe that aspects of the geometry of alternating tangles are reflected in their diagrams, as is the case with links.
- [55] arXiv:2611.25081 (cross-list from math.PR) [pdf, html, other]
-
Title: The Markov Property on Decorated Metric Planar MapsComments: This paper together with https://arxiv.org/abs/2505.05447 were originally only one paper that was uploaded to ArXiv on May 2025, so before the AI craziness of 2026. Thanks to the comments of some referees we decided to separate the original paper into two partsSubjects: Probability (math.PR); Mathematical Physics (math-ph); Combinatorics (math.CO)
We introduce decorated metric planar maps: planar maps whose edges $e$ are replaced by segments $[0,w_e]$, together with a continuous function on the resulting metric space, the decoration. We consider laws under which, conditionally on the metric map, the decoration follows a statistical physics model such as the Ising model or the Gaussian free field: the values at the vertices interact through a quadratic Hamiltonian and, given these values, the decoration along each edge is a Brownian bridge. Working with 4-regular maps with a boundary (the duals of quadrangulations with a boundary), we define a Markov property that allows explorations to stop in the middle of an edge. We show that, under mild regularity assumptions, the rerooting-invariant families of laws satisfying this Markov property are exactly the Boltzmann decorated metric maps. We also prove a strong Markov property and show that the random submaps inducing a Markovian decomposition are exactly the stopping maps for a suitable filtration. Finally, we obtain analogous results for classical decorated planar maps.
- [56] arXiv:2611.25164 (cross-list from cs.CG) [pdf, html, other]
-
Title: Convexity is overrated: Shortest paths on 4-polytopes are hard to computeComments: 64 pages, 2 figuresSubjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC); Combinatorics (math.CO); Metric Geometry (math.MG)
We prove that computing geodesic distance on the boundary of a rational convex $4$-polytope is NP-hard. We then construct rational $4$-polytopes with two rational points joined by exponentially many shortest paths of equal rational length, disproving several conjectures along the way. For the same problem, we also prove SQRTSUM-hardness under deterministic polynomial-time Turing reductions. By a separate argument, we show that the square of the geodesic distance between distinct rational boundary points of a rational convex polytope is a totally positive multiquadratic number.
- [57] arXiv:2611.25268 (cross-list from math.OC) [pdf, html, other]
-
Title: Integer Programming Strategies for the Snake-in-the-Box ProblemSubjects: Optimization and Control (math.OC); Combinatorics (math.CO)
We present a selection of Integer Programming (IP) strategies for the Snake-in-the-Box problem, which asks for the longest induced path in the $d$-dimensional hypercube. Current records are based on sophisticated, exhaustive searches, with optimality proven only for instances up to dimension 8, motivating our study of IP formulations. We address symmetries and potential strengthenings. With the smallest open instance having as few as 512 binary decision variables, the proposed IPs offer a challenging and intriguing combinatorial problem. In addition, we extend the problem to higher-dimensional grid graphs and provide solutions for unexplored and unsolved instances.
- [58] arXiv:2611.25997 (cross-list from math.AC) [pdf, html, other]
-
Title: Minimal primes and radicality of join-meet ideals of modular lattices with one diamondComments: 18 pages. Every comment is very welcome!Subjects: Commutative Algebra (math.AC); Combinatorics (math.CO); Rings and Algebras (math.RA)
Let $L$ be a finite modular lattice with exactly one diamond, that is, exactly one interval of length two with at least three atoms. We describe the minimal primes of the join-meet ideal $I_L$ in terms of maximal closed distributive sublattices of $L$, and we show that $I_L$ has height $|L|-\mathrm{rank}(L)$. Moreover, we characterize the radicality of $I_L$, over any field, in terms of the complements of the atoms of the diamond in their fibres. Finally, we prove that $I_L$ is unmixed if and only if all its minimal primes have the same height, if and only if the rank of every maximal closed distributive sublattice through an atom of the diamond is $\mathrm{rank}(L)-1$; in this case $I_L$ is radical.
- [59] arXiv:2611.26185 (cross-list from math.RT) [pdf, html, other]
-
Title: Euler up-down numbers and quiver representationsComments: 27 pagesSubjects: Representation Theory (math.RT); Algebraic Geometry (math.AG); Combinatorics (math.CO)
We show that Euler up-down numbers enumerate isoclasses of representations arising from quiver Grassmannians which provide an explicit realization of PBW degenerate flag varieties. Using this geometric realization, we derive several formulas connecting Euler up-down numbers, median Genocchi numbers, and Motzkin numbers. We also define a new $q$-analogue of Euler up-down numbers and derive several formulas for these polynomials. We describe a natural poset structure on the set of isoclasses of subrepresentations and describe it in terms of the classical degeneration order. Finally, we prove that the finer strata defined by fixing isotypes of sub- and quotient representations are the orbits under the automorphism group of the ambient quiver representation.
- [60] arXiv:2611.26246 (cross-list from math.AG) [pdf, html, other]
-
Title: Presentations of the cohomology ring of Hessenberg varieties for the minimal nilpotent orbit in type AGiulia Gaggero, Megumi Harada, Hannah Nardone, Brett Nasserden, Jenna Rajchgot, Lisa Seccia, Adam Van TuylSubjects: Algebraic Geometry (math.AG); Combinatorics (math.CO); Representation Theory (math.RT)
In 2016 Abe and Crooks found a presentation for the cohomology ring of Hessenberg varieties associated with the minimal nilpotent orbit. Specifically, they presented the ring as a quotient of the cohomology ring of the flag variety, and described the kernel of the quotient map as the span of certain Schubert classes. This note improves upon their result in the Lie type A case, by giving a minimal generating set for the kernel. Our description uses substantially fewer generators than that of Abe-Crooks. Our list consists of a set of Schubert polynomials associated to permutations constructed from the Hessenberg function ${\mathbf h}$.
- [61] arXiv:2611.26300 (cross-list from quant-ph) [pdf, html, other]
-
Title: A Tensor-Algebraic No-Go Theorem for High-Dimensional Photonic Greenberger--Horne--Zeilinger States Discovered with AlphaProof NexusComments: 13 pages, 1 figure, Lean examples. Comments welcomeSubjects: Quantum Physics (quant-ph); Artificial Intelligence (cs.AI); Combinatorics (math.CO)
Photonic GHZ states generated with probabilistic pair sources can be described by edge-coloured, complex-weighted graphs. In this representation, conditioning on an event with one photon in every detector turns the output amplitudes into coherent sums over perfect matchings, and generating an \(N\)-photon \(D\)-dimensional GHZ state is equivalent to constructing a monochromatic quantum graph. Here, we prove that no complex-weighted monochromatic quantum graph exists for any even \(N\ge4\) when \(D\ge N\). The proof, discovered through AI-assisted formal proof search in Lean using AlphaProof Nexus, constructs a weighted sum \(\mathcal F\) of amplitudes whose coefficients factor vertex by vertex. Summing over the colours at one fixed vertex reduces the problem to an \((N-1)\times N\) matrix of effective edge weights. For the graph amplitudes \(\omega\) and GHZ target \(\Delta\), the row--column imbalance yields \(\mathcal F(\omega)=0\) but \(\mathcal F(\Delta)\neq0\), contradicting the required equality \(\omega=\Delta\). Finally, we give a physical interpretation of the AI-discovered mathematical proof.
- [62] arXiv:2611.26446 (cross-list from cs.CC) [pdf, html, other]
-
Title: Degree Lower Bounds for Symmetric Boolean Functions: Breaking the Prime-Gap BarrierSubjects: Computational Complexity (cs.CC); Combinatorics (math.CO)
We prove that every nonconstant symmetric Boolean function on $n$ variables has exact real polynomial degree at least $n-O(n^{1/3}(\log n)^{2/3})$. This makes progress toward the conjecture of von zur Gathen and Roche that the degree is always at least $n-3$. The original prime-gap argument of von zur Gathen and Roche yields a degree deficit of $O(n^{0.525})$ using the theorem of Baker, Harman, and Pintz, or $O(n^{0.52})$ using an estimate claimed in a recent preprint. Our $\widetilde{O}(n^{1/3})$ bound on the degree deficit improves upon the $\widetilde{O}(\sqrt{n})$ bound obtainable from the prime-gap approach, even assuming the Riemann hypothesis or Legendre's conjecture. Notably, our proof avoids prime-gap estimates entirely.
The proof combines vanishing binomial moments with the arithmetic of linear recurrences. A quantitative form of the integer Hankel determinant method in the Pólya--Carlson theorem forces the function's values on a central interval of Hamming weights to satisfy a short rational recurrence. A second determinant argument bounds the number of characteristic roots near $-1$. Through the binomial transform, these roots can then be cancelled by a polynomial test of degree below the deficit. An integer annihilator and contour estimates make the test isolate the first failure of the recurrence, yielding a contradiction with the vanishing-moment conditions. If the recurrence agrees with the function on a sufficiently long interval, arithmetic height bounds instead force a bounded period, which is ruled out by a separate polynomial test. Every numbered result in the paper has been formally verified in Lean~4. - [63] arXiv:2611.26457 (cross-list from math.AC) [pdf, html, other]
-
Title: Comprehensive Gröbner Bases in Macaulay2María Agustina Cagliero, Oliver Clarke, Lorenzo De Biase, Angelo El Saliby, Giulia Gaggero, Weijia WangSubjects: Commutative Algebra (math.AC); Combinatorics (math.CO)
Studying parameter-dependent polynomial systems often requires stratifying parameter space according to the algebraic or geometric properties of the specialised systems. Comprehensive Gröbner bases and systems, which provide Gröbner bases valid under every specialisation, either uniformly or on specified regions of parameter space, are classical tools for studying polynomial ideals under specialisation. We introduce ComprehensiveGBs, a Macaulay2 package for computing comprehensive Gröbner bases and systems, either over the full parameter space or under specified parameter conditions. We describe its use and implementation, with examples involving Weierstrass cubics and graphs.
- [64] arXiv:2611.26570 (cross-list from math.PR) [pdf, html, other]
-
Title: On Romik's rationality conjectures for critical percolationComments: 45 pages, 9 figures, results obtained without the use of AISubjects: Probability (math.PR); Mathematical Physics (math-ph); Combinatorics (math.CO)
The completely packed $O(1)$ loop model can be viewed as an interface representation of critical bond percolation on the square lattice. We consider submatching events, which prescribe how these interfaces pair finitely many consecutive boundary points. Romik's rationality conjectures predict that the probabilities of these events on the semi-infinite cylinder are given by specific rational functions, which even become dyadic rationals in the half-plane limit.
We derive explicit Pfaffian formulae for the probability of $k$ nested arches on the semi-infinite cylinder of circumference $2N$, valid for $k<N$. We deduce that these probabilities are rational functions of $N$ and, by taking the limit $N\to\infty$, that the corresponding half-plane probabilities remain rational. This establishes key aspects of Romik's conjectures.
Our proof uses identities of Fonseca and Zinn-Justin, derived through the qKZ formalism, which express these probabilities as ratios of enumeration numbers for totally symmetric self-complementary plane partitions (TSSCPPs). These plane partitions admit a dimer representation, allowing us to apply Kasteleyn theory. We evaluate the resulting hypergeometric sum using Zeilberger's and Gosper's algorithms and then take the half-plane limit $N\to\infty$. Along the way, we derive a somewhat simplified expression for the inverse Kasteleyn matrix entries (encoding correlations in TSSCPPs) of Ayyer and Chhita, which might be of independent interest.
Cross submissions (showing 13 of 13 entries)
- [65] arXiv:2308.14208 (replaced) [pdf, html, other]
-
Title: Castelnuovo-Mumford regularity for $321$-avoiding Kazhdan-Lusztig varietiesComments: 28 pages; We thank the anonymous reviewer who noted errors in the earlier version of this manuscript. In this version, we amend our theorem statements and give an algorithm to compute regularies in restricted cases. For general 321-avoiding permutations, our algorithm provides a lower boundSubjects: Combinatorics (math.CO); Commutative Algebra (math.AC)
We prove the Castelnuovo--Mumford regularity of 321-avoiding Kazhdan--Lusztig varieties can be computed combinatorially in terms of $K$-theoretic skew excited Young diagrams. We present an algorithm which gives a lower bound for this regularity and describe a setting in which this algorithm provides precise regularity computations. This algorithm specializes to compute the regularity of all two-sided mixed ladder determinantal varieties.
- [66] arXiv:2407.05827 (replaced) [pdf, html, other]
-
Title: An analogue of Reed's conjecture for digraphsSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
Reed in 1998 conjectured that every graph $G$ satisfies $\chi(G) \leq \lceil \frac{\Delta(G)+1+\omega(G)}{2} \rceil$. As a partial result, he proved the existence of $\varepsilon > 0$ for which every graph $G$ satisfies $\chi(G) \leq \lceil (1-\varepsilon)(\Delta(G)+1)+\varepsilon\omega(G) \rceil$. We propose an analogue conjecture for digraphs. Given a digraph $D$, we denote by $\vec{\chi}(D)$ the dichromatic number of $D$, which is the minimum number of colours needed to partition $D$ into acyclic induced subdigraphs. We let $\overleftrightarrow{\omega}(D)$ denote the size of the largest biclique (a set of vertices inducing a complete digraph) of $D$ and $\tilde{\Delta}(D) = \max_{v\in V(D)} \sqrt{d^+(v) \cdot d^-(v)}$. We conjecture that every digraph $D$ satisfies $\vec{\chi}(D) \leq \lceil \frac{\tilde{\Delta}(D)+1+\overleftrightarrow{\omega}(D)}{2} \rceil$, which if true implies Reed's conjecture. As a partial result, we prove the existence of $\varepsilon >0$ for which every digraph $D$ satisfies $\vec{\chi}(D) \leq \lceil (1-\varepsilon)(\tilde{\Delta}(D)+1)+\varepsilon\overleftrightarrow{\omega}(D) \rceil$. This implies both Reed's result and an independent result of Harutyunyan and Mohar for oriented graphs.
To obtain this upper bound on $\vec{\chi}$, we prove that every digraph $D$ with $\overleftrightarrow{\omega}(D) > \frac{2}{3}(\Delta_{\max}(D)+1)$, where $\Delta_{\max}(D) = \max_{v\in V(D)} \max(d^+(v),d^-(v))$, admits an acyclic set of vertices intersecting each biclique of $D$, which generalises a result of King.
We finally give a short proof that every oriented graph $D$ with underlying graph $G$ satisfies $\vec{\chi}(D) \leq \frac{\sqrt{2}}{2} \tilde{\Delta}(D) + 2$ and $\vec{\chi}(D) \leq \frac{1}{3}\Delta(G)+2$, improving on results of Golowich and Steiner, respectively. - [67] arXiv:2502.00176 (replaced) [pdf, html, other]
-
Title: Settling the no-$(k+1)$-in-line problem when $k$ is not smallComments: Revised version: replaces the asymptotic subgraph enumeration argument of Isaev and McKay (which required extra conditions) with an elementary direct count of submatchings, yielding exact results for improved bounds on $k$. Note that Grebennikov and Kwan subsequently extended the exact result to all sufficiently large $k$, independent of $n$Subjects: Combinatorics (math.CO)
What is the maximum number of points that can be selected from an $n\times n$ square lattice so that no $k+1$ of them are collinear? This was asked more than $100$ years ago for $k=2$ and it remained wide open ever since. In this paper, we prove the exact answer is $kn$, provided that $ n\ge k\ge C\log n$ for an absolute constant $C<20$. The proof relies on carefully constructed block-uniform random bipartite graphs and concentration inequalities.
- [68] arXiv:2507.06365 (replaced) [pdf, html, other]
-
Title: Salvetti complexes for conditional oriented matroidsComments: Fixed typos and updated references. Version to appear in Advances in Applied MathematicsSubjects: Combinatorics (math.CO)
We give a new proof of the fact that the complement of the complexification of a real hyperplane arrangement is homotopy equivalent to the Salvetti complex of the associated oriented matroid. Our proof involves no choices, is relatively easy to visualize, and generalizes to the setting of conditional oriented matroids.
- [69] arXiv:2508.04396 (replaced) [pdf, html, other]
-
Title: Unimodality and Cluster Algebras from SurfacesJournal-ref: European Journal of Combinatorics, 136, 104392(2026)Subjects: Combinatorics (math.CO)
We prove that the rank polynomial of the lattice of order ideals of a loop fence poset is unimodal. This poset arises as the poset of join-irreducibles in the lattice of good matchings of loop graphs associated with notched arcs. Equivalently, such polynomials can be obtained by evaluating all coefficient variables in an F-polynomial at a single variable q. We also conclude that the rank polynomial of any tagged arc, whether plain or notched, is not only unimodal but also satisfies a symmetry condition known as almost interlacing. Furthermore, when the lamination consists of a single curve, the cluster expansion-evaluated by setting all cluster variables to 1 and all coefficient variables to q-is also unimodal. We conjecture that polynomials in this case are log-concave.
- [70] arXiv:2509.10232 (replaced) [pdf, html, other]
-
Title: A case of the dijoin conjecture on inverting oriented graphsComments: 16 pages. Version 2: minor edits and clarificationsSubjects: Combinatorics (math.CO)
For an oriented graph $D$, the inversion of $X\subseteq V(D)$ in $D$ is the graph obtained by reversing the orientation of all arcs with both ends in $X$. The inversion number $\mathrm{inv}(D)$ is the minimum number of inversions needed to obtain an acyclic oriented graph.
We show that the dijoin conjecture of Bang-Jensen, da Silva and Havet, that $\mathrm{inv}(D_1\rightarrow D_2)=\mathrm{inv}(D_1)+\mathrm{inv}(D_2)$, is true in the case where $\mathrm{inv}(D_1)=2$ and $\mathrm{inv}(D_2)$ is even. We also characterise the cases $\mathrm{inv}(D_1)=2$ and $\mathrm{inv}(D_2)$ odd, for which the conjecture does and does not hold. We then go on to show a similar result for n-joins, in doing so we prove a conjecture of Alon, Powierski, Savery, Scott and Wilmer. Our proofs build on the idea of tournament minimum rank, introduced by Behague, Johnston, Morrison and Ogden. - [71] arXiv:2512.10281 (replaced) [pdf, html, other]
-
Title: Computations with diagonal simplicial tensor modulesComments: 15 pages, 1 figure, 2 tables. Rewritten and retitled. Programs for the tensor and graph computations are available at this https URLSubjects: Combinatorics (math.CO)
For each vertex order $\pi$ of a finite simple graph on at least two vertices, insert an isolated vertex between successive vertices. In the resulting adjacency matrix $A$, deleting row $i$ and column $i$ gives a principal submatrix $A_i$. The alternating sum of the $A_i$ is the simplicial boundary of $A$ and has full rank over $\mathbb F_2$ exactly when $\pi$ traces a Hamiltonian path. Each Hamiltonian path gives two full-rank orders. We tabulate boundary rank distributions over all vertex orders of the Petersen, $4\times4$ rook, and Shrikhande graphs. Full-rank counts distinguish the cospectral rook and Shrikhande graphs. For each finite graph, vertex and edge tensors in a three-axis diagonal simplicial tensor module generate a simplicial submodule whose normalized chains form the graph's incidence complex and compute its homology. Let $X$ be a diagonal simplicial tensor module on $k\ge1$ axes over a nonzero unital commutative ring. We give coordinate bases for its horn kernels and normalized chains. A horn has a unique filler exactly when its degree exceeds $k$. For a shape in $X$ of simplicial dimension $n$ (shortest axis length $n+1$), the simplicial module $X$ is an $n$-hypergroupoid exactly when $k\le n$. We prove analogous bounds for horn filling in a dendroidal module on rooted trees. Over a field, we construct a rational map from the space of hypermatrices of fixed shape and degree to a product of Grassmannians. The reduced closure of its image is rational and, over $\mathbb C$, is isomorphic to a Schubert variety. Python code for this paper's examples and rank tables is at this https URL.
- [72] arXiv:2601.04836 (replaced) [pdf, html, other]
-
Title: Arboreal Networks and UltrametricsComments: 25 pages, 5 figuresSubjects: Combinatorics (math.CO)
Ultrametrics are an important class of distances used in applications such as phylogenetics, clustering and classification theory. Ultrametrics are essentially distances that can be represented by an edge-weighted rooted tree so that all of the distances in the tree from the root to any leaf of the tree are equal. In this paper, we introduce a generalization of ultrametrics called arboreal ultrametrics which have applications in phylogenetics and also arise in the theory of distance-hereditary graphs. These are partial distances, that is distances that are not necessarily defined for every pair of elements in the groundset, that can be represented by an ultrametric arboreal network, that is, an edge-weighted rooted network whose underlying graph is a tree. As with ultrametrics all of the distances in the ultrametric arboreal network from any root to any leaf below it are are equal but, in contrast, the network may have more than one root. In our two main results we characterize when a partial distance is an arboreal ultrametric as well as proving that, somewhat surprisingly, given any unrooted edge-weighted phylogenetic tree there is a necessarily unique way to insert roots into this tree so as to obtain an arboreal ultrametric.
- [73] arXiv:2601.22205 (replaced) [pdf, html, other]
-
Title: Transitive Sets of Mutually Orthogonal Latin SquaresComments: 12 pagesSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Group Theory (math.GR)
Write $n=\prod_{i=1}^u p_i^{a_i}$ for the prime factorization of $n$. We prove that a net of order $n$ admitting a point-transitive group of automorphisms preserving each parallel class has at most $\min_i(p_i^{a_i}+1)$ parallel classes. This extends Jungnickel's sharp bound for translation nets. Equivalently, the maximum number of jointly cell-transitive mutually orthogonal Latin squares of order $n$ is $\min_i(p_i^{a_i}-1)$. An explicit Latin square of order nine answers affirmatively Krotov and Potapov's question about the existence of an isotopically transitive, non-topolinear Latin square.
- [74] arXiv:2603.26379 (replaced) [pdf, html, other]
-
Title: The Bollobás--Nikiforov inequality for complete multipartite graphs, with remarks on the $K_4$-free caseComments: v4: substantially revised. Corrects errors in v1-v3 (equality cases, Hoffman-type bound, stability conjecture, Zykov lemma, attributions); the claimed result for dense K4-free graphs is withdrawn. 10 pagesSubjects: Combinatorics (math.CO)
Bollobás and Nikiforov conjectured that every graph $G \neq K_n$ with $m$ edges and clique number $\omega$ satisfies $\lambda_1^2(G) + \lambda_2^2(G) \leq 2(1 - 1/\omega)m$, where $\lambda_1(G) \geq \lambda_2(G)$ are the two largest adjacency eigenvalues. We give a short self-contained proof of the inequality for complete multipartite graphs, based on a quadratic-form identity which shows that $\lambda_2 \leq 0$, and we determine the equality cases in this class. We show that equality in the conjecture is attained by a wider family than the Turán graphs, namely by disjoint unions of two complete bipartite graphs, or of two balanced complete $r$-partite graphs of possibly different orders. For $K_4$-free graphs we record the cases that follow from known results, with corrected attributions, and we give examples showing that three natural lines of attack fail: a Hoffman-type eigenvalue bound for graphs with large independence number, a spectral stability statement for connected graphs, and Zykov symmetrization in an arbitrary direction.
- [75] arXiv:2604.14405 (replaced) [pdf, html, other]
-
Title: Infinite graphs with finite metric dimensionSubjects: Combinatorics (math.CO)
We study the metric dimension (strong and weak) of connected infinite graphs. In particular, our main interest is characterizing infinite graphs with finite dimension. Our main results: (1) graphs with more than one end have infinite strong dimension; (2) for locally finite graphs with a finite number of cycles, the weak dimension is finite if and only if the graph has finitely many vertices of degree at least three, and the strong dimension is finite if and only if the graph has one end and finitely many vertices of degree at least three.
- [76] arXiv:2605.05455 (replaced) [pdf, html, other]
-
Title: Thresholds for Tic-Tac-Toe on Finite Affine SpacesSubjects: Combinatorics (math.CO)
We study the strong positional game in which two players alternately claim points of $\F_q^m$ and the first to complete an affine $n$-subspace wins. We distinguish the first winning dimension $\tau(n,q)$ from the eventual winning threshold $T(n,q)$, without assuming monotonicity in $m$. Affine Ramsey theory proves finiteness, while the Erdős-Selfridge criterion and explicit geometric strategies give lower bounds. In the binary case, a quantitative form of the classical quotient argument yields $T(n,2)\le2^{n-1}+n$, with a corresponding bound for any number of colors. A plane-counting recursion gives further multicolor and extremal estimates. We prove $\tau(2,2)=T(2,2)=4$ and show that every $31$-point subset of $\F_2^6$ contains an affine $3$-subspace. This gives an elementary proof of the known equality $\AR_2(3;2)=6$ and implies $\tau(3,2)=T(3,2)\in\{5,6\}$. Previously known planar outcomes are recovered within the same framework.
- [77] arXiv:2605.10542 (replaced) [pdf, html, other]
-
Title: Algorithms for Computing Set Tolerances: Theory, Computational Analysis and ApplicationsSubjects: Combinatorics (math.CO); Optimization and Control (math.OC)
The regular set tolerance is an important term in sensitivity analysis. For combinatorial sum problems, e.g., the Traveling Salesman Problem, Shortest Path Problem and Minimum Spanning Tree Problem, it determines how much the sum of the costs of the elements of a set can be increased while ensuring that all current optimal solutions remain optimal. The regular set lower tolerance determines how much the sum of the costs of the elements of a set can be decreased while ensuring that the objective value of the optimal solution is not changed. We investigate general methods for computing regular (upper and lower) set tolerances in combinatorial sum problems. For the upper tolerance, we present a linear programming approach, and for the lower tolerances, three linear programming approaches, where the last two are novel and lead to recursive procedures for computation of the lower tolerances of all subsets of the given ground set. We give new upper bounds for set lower tolerances. For both upper and lower tolerances, we give an exact formula for sets of cardinality 2 and 3. Furthermore, we computationally compare and analyze our introduced tolerance LPs. Finally, we consider the computation of tolerances for the Minimum Spanning Tree Problem, give a formula for single tolerances, a lower bound for regular set upper tolerances and an exact formula for regular set lower tolerances.
- [78] arXiv:2605.23284 (replaced) [pdf, html, other]
-
Title: Higher Rank-Support Weights and $(q,m)$-PolymatroidsSubjects: Combinatorics (math.CO)
The aim of this paper is to develop a $(q,m)$-polymatroidal approach to higher supports and higher rank-weight enumerators of Delsarte rank-metric codes. In this framework, we establish rank-metric analogs of several fundamental results known for matroids and linear codes. We describe minimal higher supports in terms of cocircuits of suitable truncations of the associated $(q,m)$-polymatroid, and obtain a polymatroidal interpretation of generalized minimum rank weights and their Singleton-type bound. We also prove that the associated $(q,m)$-polymatroid and the higher support distributions determine each other. On the enumerative side, we establish a Greene-type identity relating higher rank-weight enumerators to the rank generating function, and conversely show that the full sequence of higher rank-weight enumerators determines this function. As the main application, we prove MacWilliams-type identities for higher rank-weight enumerators by first deriving a duality formula for higher weight polynomials of $(q,m)$-polymatroids and then applying it to a rank-metric code and its dual.
- [79] arXiv:2606.08061 (replaced) [pdf, html, other]
-
Title: Cheeger-type inequalities for the second largest spectral gap from $1$ of the normalized LaplacianComments: We added a note in v2 regarding the novelty of our resultsSubjects: Combinatorics (math.CO); Spectral Theory (math.SP)
We study the second largest spectral gap from $1$ of the normalized Laplacian of a graph, a quantity that appears in the literature in connection with random walks, expander graphs, and Ramanujan graphs. We relate it to the classical Cheeger and dual Cheeger constants, and we introduce a new Cheeger-type constant admitting a probabilistic interpretation in terms of two-step random walks. For this constant, we establish sharp inequalities analogous to the classical Cheeger inequalities.
- [80] arXiv:2607.02589 (replaced) [pdf, other]
-
Title: Thresholds for the Frankl-Wang $3/7$ conjecture on maximum-degree ratiosComments: The results in this paper are either not new or straightforwardSubjects: Combinatorics (math.CO)
Let $\mathcal{F}\subset\binom{[n]}{k}$ be an intersecting family, $\Delta(\mathcal{F})=\max_{x\in[n]}|\{F\in\mathcal{F}:x\in F\}|$, and $\varrho(\mathcal{F})=\Delta(\mathcal{F})/|\mathcal{F}|$. Frankl and Wang conjectured that if $n>100k$ and $|\mathcal{F}|>\binom{n-3}{k-3}$, then $\varrho(\mathcal{F})\ge 3/7$; the constant $3/7$ is sharp because of the Fano-plane construction. In this note we obtain three results. First, we show that no linear threshold $n>Ck$ can be sufficient: using a truncated Fano-plane construction we exhibit, for every constant $C$ and all large $k$, an intersecting family with $n>Ck$, $|\mathcal{F}|>\binom{n-3}{k-3}$, yet $\varrho(\mathcal{F})<3/7$. In particular, the original condition $n>100k$ does not guarantee the conclusion. Second, for $k=3$ we prove that $\varrho(\mathcal{F})\ge 3/7$ holds for every nonempty intersecting $3$-uniform family; the proof is nontrivial and does not rely on any assumption on $n$ or $|\mathcal{F}|$. Third, using the classical pseudo-sunflower bound $|\mathcal{F}|\le t^k$ (for families containing no pseudo-sunflower of size $t+1$), we obtain a completely explicit polynomial threshold for all $k\ge4$: if $n>(k-3)(7k^4+k)+3$ and $|\mathcal{F}|>\binom{n-3}{k-3}$, then $\varrho(\mathcal{F})\ge 3/7$. In particular, the simplified bound $n>7k^5$ is sufficient for every $k\ge4$.
- [81] arXiv:2608.07607 (replaced) [pdf, html, other]
-
Title: A congruence obstruction to Roman's bound for Zarankiewicz numbersComments: 14 pagesJournal-ref: Discrete Mathematics 350(4) (2027), 115552Subjects: Combinatorics (math.CO)
Let z(m,n;s,t) be the largest number of ones in an m x n zero-one matrix with no s x t all-ones submatrix. Roman's 1975 inequality gives a general upper bound for s >= 3, with improvements known in special parameter ranges. We show it is not attained on much of the range just below the design threshold T = (t-1)C(m,s)/(s+1).
For n = T-c with 1 <= c <= sT/(s+2), Roman's bound equals the counting bound. Viewing columns as sets of row indices (points), attainment forces all but at most one column to have cardinality s+1 or s+2. These two sizes contribute multiples of d = gcd(s,C(s+1,2)) to the coverage count at each point. At each point, the unused coverage is congruent to mu modulo d, with a correction for the possible exceptional column. With r = c mod s and sigma(r) a slack depending only on s, the bound drops by at least one whenever 1 <= sigma(r) < d and m*mu != s*sigma(r), or mu != 0 and m*mu > s*sigma(r). The first needs s odd and is confined to one residue class; the second covers the whole interval when mu != 0 and m is sufficiently large.
For s = 4, t = 2, m = 28 all 2730 values of n are covered. For odd s, when c = (s+1)/2 and an s-(m,s+1,t-1) design exists we obtain the exact value z = (s+1)(T-c). We also locate the obstruction relative to linear programming: the refined program of Davies, Gill and Horsley (2026) still attains the Roman vertex on an explicit family of such parameters. - [82] arXiv:2608.08692 (replaced) [pdf, html, other]
-
Title: Weighted bond posets and a new chromatic symmetric functionComments: 59 pages, 13 figures. Minor revisions in the exposition and update of citations and referencesSubjects: Combinatorics (math.CO)
The classical bond lattice of a graph was used in a formula of Whitney to compute the chromatic polynomial. In this paper, we use weighted versions of the bond lattice, to introduce and study a new polynomial and a new symmetric function invariant of a graph. Examples of the new polynomial invariant include the classical Narayana polynomials (for the path graph), the tree-Eulerian polynomials (for the complete graph), and the binomial-Eulerian polynomials (for the star graph). These examples suggest an interesting connection to $h$-polynomials of general graph-associahedra. We prove that for any chordal graph, our polynomial graph invariant is $\gamma$-positive.
Multiweighted bond posets yield a symmetric function graph invariant that is an analog of the chromatic polynomial. The highest degree homogeneous component of this symmetric function is of particular interest. The parking function symmetric function introduced by Haiman arises as an example, as do symmetric functions studied by the first author in connection with multibracketed Lie algebras and with colored exterior algebras. The $\gamma$-positivity result mentioned above is a specialization of an $e$-positivity result for the highest degree homogeneous component, which we prove for any chordal graph using the theory of lexicographic shellability. We conjecture that this symmetric function is Schur-log-concave, which specializes to Huh's log-concavity theorem for the chromatic polynomial. - [83] arXiv:2608.24336 (replaced) [pdf, other]
-
Title: On the Maximum Number of Vertices that Belong to Every Metric BasisComments: 20 pages, 8 figures. Parts of this paper appeared in CALDAM 2025Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
Resolving sets of graphs have been widely studied since their introduction in the 1970's by Slater and, independently, by Harary and Melter. The minimum cardinality of a resolving set of a graph $G$ is called the metric dimension of $G$ and is denoted by $\dim(G)$. In this paper, we concentrate on the existence of vertices in a graph $G$ that belong to all metric bases of $G$, i.e. resolving sets of cardinality $\dim(G)$. Such vertices are called basis forced vertices, and we denote the number of them by $\mathrm{bf}(G)$. We show that $\mathrm{bf}(G)\le 2/3(n-\dim(G)-1)$ for any connected nontrivial graph $G$ of order $n$. In addition, we show that this bound can be attained. Furthermore, it also implies that $\mathrm{bf}(G)\le 2/5(n-1)$ holds for any nontrivial connected graph $G$. This result answers a question posed by Bagheri \emph{et al.} in 2016. Moreover, we provide a complete realization of the parameters $n$, $\dim(G)$ and $\mathrm{bf}(G) \ge 1$ within the previous bounds. We consider some extremal cases related to basis forced vertices in a graph, in particular, we give a full characterization of the graphs with $\mathrm{bf}(G) = 2$ and $\dim(G) = n-4$.
- [84] arXiv:2609.06145 (replaced) [pdf, html, other]
-
Title: Bounded Ratios of Lorentzian Polynomials I: The Ternary Theory and Optimal Bounding ConstantsComments: 23 pagesSubjects: Combinatorics (math.CO); Metric Geometry (math.MG)
We study bounded coefficient ratios and their optimal bounding constants for ternary Lorentzian polynomials. For every degree $d\geq2$ and every fixed ternary $M$-convex support, we prove that bounded ratios are generated by those of quadratic derivatives. We express the optimal bounding constants through a variational formula. For full support, we determine all linear relations among the logarithms of triangular ratios in every degree. For ternary cubics, we compute sharp constants for products of any two distinct triangular ratios. Finally, we compare the bounds for Lorentzian polynomials with those for volume polynomials and rank-three matroid basis counts.
- [85] arXiv:2609.17551 (replaced) [pdf, html, other]
-
Title: A $\sqrt{2}$-Approximation to the Bilu-Linial ConjectureSubjects: Combinatorics (math.CO)
Bilu and Linial conjectured that if $d\ge 2$, then every $d$-regular graph $G$ has an edge signing $\sigma:E(G)\to\{-1,1\}$ such that its signed adjacency matrix $A_\sigma$ satisfies the Ramanujan bound \begin{equation*}
\rho(A_\sigma)\le 2\sqrt{d-1} \end{equation*} and they proved that \begin{equation*}
\rho(A_\sigma)=O\!\left(\sqrt{d\log^3 d}\right). \end{equation*}
Using a method of interlacing polynomials, Marcus, Spielman, and Srivastava confirmed one side of this conjecture that there is a signing $\sigma$ for which
\[
\lambda_{\max}(A_\sigma)\le 2\sqrt{d-1}. \] By constructing an auxiliary bipartite graph from a balanced orientation of $G$ and applying a bipartite signing argument, we prove that every finite simple graph $G$ of maximum degree $d\ge 3$ admits an edge signing $\sigma$ such that \[
\rho(A_\sigma)
\le 4\sqrt{\left\lceil \frac d2\right\rceil-1}
\le 2\sqrt{2(d-1)}. \] This gives a new proof of Ravichandran and Srivastava's bound $2\sqrt{2(d-1)}$. - [86] arXiv:2609.23128 (replaced) [pdf, html, other]
-
Title: There Are No Nontrivial Perfect Codes in the Johnson SchemeSubjects: Combinatorics (math.CO)
In his seminal work from 1973, Delsarte conjectured that the Johnson schemes admit no nontrivial perfect codes. We prove this fundamental conjecture which is central in combinatorial coding theory. Our arguments combine lower bounds on the design strength of a perfect code with divisibility conditions for the size of a metric ball. We show that the ball size divides the greatest common divisor of specified binomial coefficients. An exact formula for this gcd implies squarefreeness and localizes a unique power of each prime divisor of the ball size to a short interval. Lloyd polynomials, explicit prime estimates, and bounds for linear forms in logarithms then exclude all radii except for $1$ and $2$. Additional arithmetic arguments handle these two remaining radii.
- [87] arXiv:2609.29351 (replaced) [pdf, html, other]
-
Title: Nearly optimal packings of equally sized rainbow forestsComments: 6 pages, 1 figure. This version presents a substantially shorter proof and extends the result from proper edge-colorings to arbitrary edge-colorings satisfying the same global color bound. The new proof was developed with the assistance of AI tools, which helped identify a key lemma and refine the proofSubjects: Combinatorics (math.CO)
For every $\varepsilon>0$, we prove that whenever $m$ is sufficiently large in terms of $\varepsilon$ and $1\le k\le2m$, every simple graph with $km$ edges and at most $m$ edges of each color contains at least $(1-\varepsilon)m$ edge-disjoint forests, each with $k$ edges of distinct colors. This gives the packing conjectured by Montgomery, Pokrovskiy, and Sudakov throughout this range, even when adjacent edges may have the same color. For every $k>2m$ there is a graph on $k$ vertices with $km$ edges of distinct colors and no $k$-edge forest. Applied to $K_n$, the theorem gives $(1-o(1))\lfloor n/2\rfloor$ edge-disjoint rainbow spanning trees whenever each color occurs on at most $\lfloor n/2\rfloor$ edges.
- [88] arXiv:2610.07049 (replaced) [pdf, html, other]
-
Title: On possible Turán densities under general uniformity conditionsComments: title changed. Substantially expanded and reorganized as a survey of ordinary, minimum-degree, and uniform Turán densities under general uniformity conditionsSubjects: Combinatorics (math.CO)
The Turán problem asks how dense a hypergraph can be while avoiding a prescribed family of subhypergraphs. For a family $\mathcal S\subseteq2^{[r]}$, an $r$-graph is $\mathcal S$-uniformly dense in the sense of Reiher, Rödl, and Schacht if, in every large collection of ordered vertex tuples selected by joint restrictions on the positions in each $S\in\mathcal S$, at least a prescribed proportion of the tuples form edges. Ordinary and minimum $\ell$-degree Turán densities correspond to $\mathcal S=\{\{1\}\}$ and $\mathcal S=\{\{1,\ldots,\ell\}\}$, respectively, for $1\le\ell<r$. This survey collects results on possible Turán densities within this framework and gives a complete description of these values for many choices of $\mathcal S$.
- [89] arXiv:2610.14100 (replaced) [pdf, html, other]
-
Title: Digraph Laplacian spectra: The 2005 polygon conjecture fails for all orders above fourComments: 22 pages, 1 figure. In this version 4, the changes are highlighted in blueSubjects: Combinatorics (math.CO); Rings and Algebras (math.RA); Spectral Theory (math.SP)
Let $\Lambda_n$ be the set of all eigenvalues of standardized Laplacian matrices of order $n$, equivalently, of stochastic $n\times n$ matrices with off-diagonal entries at most $\frac1n$. In 2005, a polygon $S_n\subseteq\Lambda_n$ was constructed, and it was conjectured that $\Lambda_n=S_n$; this holds for $n\le3$. We show that the conjecture fails for every $n\ge5$. The vertices of $S_n$ are eigenvalues of circulant Laplacians built from powers of the directed $n$-cycle. To first order, no perturbation of these circulants moves such an eigenvalue out of $S_n$; however, adding chords with nonconstant weights moves it along an edge of $S_n$ to first order and, with an explicit coefficient, beyond the supporting line of this edge to second order. Consequently, every edge of $S_n$ not incident to $0$ or $1$ contains interior points of $\Lambda_n$, except possibly, for even $n$, the two horizontal edges, whereas the four edges incident to $0$ or $1$ lie on $\partial\Lambda_n$. For $n=4$, whose only other edges are horizontal, the question has recently been settled, $\Lambda_4=S_4$, by computer-assisted proofs of D. Z. Liu and L. Marshall; Liu also proved that $\Lambda_n$ is not convex for $n\ge5$. We certify an explicit weighted counterexample for $n=5$, lying only $1.5\cdot10^{-3}$ outside $S_5$, and an unweighted one for $n=7$: the directed $6$-cycle with a duplicated vertex. Its eigenvalue outside $S_7$ is also an eigenvalue of the two-chord digraph that ends the above perturbation; for the analogous digraphs of order $n$, the excess is asymptotic to $\frac{\pi^2}{2n^4}$. We also observe that $S_n$ is a zonotope, describe $\Lambda_n$ in terms of eigenvectors, and prove that $S_m\subseteq S_n$ whenever $m\mid n$.
- [90] arXiv:2610.32192 (replaced) [pdf, html, other]
-
Title: Identifying codes of Archimedean gridsSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
An identifying code of a graph is a dominating set $C$ such that the sets $N[v]\cap C$ are pairwise distinct. The minimum density of an identifying code has been studied extensively for several infinite grids. It is known to be $1/4$ for the triangular grid and $7/20$ for the square grid, whereas for the hexagonal grid the problem is still open, between $5/12$ and $53/126$. These three grids are the regular members of the family of the eleven Archimedean grids. In this paper, we start a systematic study of identifying codes in this family. We determine the minimum density for five of the nine Archimedean grids for which it was not known: it is $2/3$ for the truncated hexagonal grid, $3/7$ for the truncated square grid, and $1/3$ for the trihexagonal (kagome) grid, the elongated triangular grid and the snub hexagonal grid. All lower bounds are proved by the discharging method. For the three remaining non-regular Archimedean grids, we also obtain some bounds: the minimum density lies between $3/7$ and $13/30$ for the truncated trihexagonal grid, between $1/3$ and $11/30$ for the rhombitrihexagonal grid, and between $2/7$ and $9/28$ for the snub square grid. As a by-product, we prove that every identifying code of a cubic graph with the slow growth property in which every vertex lies on exactly one triangle (resp. $4$-cycle) has density at least $2/3$ (resp. $3/7$).
- [91] arXiv:2610.34372 (replaced) [pdf, html, other]
-
Title: Sharp enumeration and growth of admissible sets of integersSubjects: Combinatorics (math.CO)
A set of positive integers is admissible if equal sums of finite subsets always have equal numbers of summands. Let $a(N)$ count the nonempty admissible subsets of $\{1,\ldots,N\}$, and let $b(N)$ count those with maximum $N$. We prove $\log a(N)\sim\log b(N)\sim\pi\sqrt{2N/3}$, establishing the sharp logarithmic asymptotic proposed by Nicolas. More generally, let $Q_h(N)$ count the subsets for which each integer has subset-sum representations of at most $h$ distinct cardinalities. Uniformly for all positive integers $h,N$, we prove $\log Q_h(N)\asymp\min\{N,\sqrt{hN}\}$ with absolute implied constants. Every infinite set satisfying the same condition for some fixed $h$ has counting function $o(\sqrt x)$. At $h=1$, the uniform count proves the conjecture $\log a(N)\asymp\sqrt N$ of Erdős, Nicolas and Sárközy, and the infinite-set theorem strengthens their conjectured vanishing lower limit to a full limit. The proofs record each subset sum together with its cardinality and use the counting theorem of Campos and the structure theorem of Carpenter, Defant and Kravitz. The sharp count also uses Nicolas's partition enumeration and an elementary construction of a long restricted-sum progression. Finally, we give an exact partition formula and asymptotics for the odd sets with separated alternate cardinality layers suggested by Nicolas, and deduce lower bounds for the number of non-stratified admissible sets.
- [92] arXiv:2610.40321 (replaced) [pdf, html, other]
-
Title: Computer-Assisted Results for $n$-Sided Non-Transitive Dice Taking Face Values in $[n]$Comments: 11 pages, revised exposition, supplementary material includes Julia code, fixed metadata tex using $$ rather than \(\)Subjects: Combinatorics (math.CO)
We consider non-transitivity among dice with $n$ sides restricted to taking face values in the set $\{1,\ldots,n\}$. We give a computer-assisted proof that $n=6$ is the smallest $n\ge3$ which admits a non-transitive cycle of maximum length $n$ with uniform and minimal winning advantage. For $n=6$, we identify the two unique non-transitive cycles of length $6$. We present computational evidence supporting a conjecture that $n=6$ is the largest $n\ge3$ which admits a non-transitive cycle of maximum length $n$ with uniform and minimal winning advantage.
- [93] arXiv:2610.40496 (replaced) [pdf, html, other]
-
Title: Real-rooted Ehrhart $h^*$-polynomials of crown posets and wheel and whirl matroidsSubjects: Combinatorics (math.CO)
For every integer $r\ge3$, the crown order polytope on $2r$ elements and the rank-$r$ whirl base polytope have the same Ehrhart $h^*$-polynomial. We also prove that every convex combination of the $h^*$-polynomials of the rank-$r$ wheel and whirl base polytopes has degree $2r-2$ and only simple negative roots. Its coefficients are positive, unimodal, and strictly ultra log-concave of order $2r-2$. These results settle the real-rootedness conjecture of Lundström and Saud Maia Leite for crown order polytopes.
- [94] arXiv:2611.06470 (replaced) [pdf, html, other]
-
Title: How many sorted projections determine any n points in k dimensions?Comments: 33 pages, 9 figures. v2: added word "any" to title, improved a bound following comment from ZM26, added three small special cases, removed unicode from an anc file, and added a statement about deep sets. v3: no new results, but many small text edits for clarity, and also added appendix with four new figures to aid in indexation of resultsSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Information Theory (cs.IT); Machine Learning (cs.LG)
Let $d_1,\dots,d_m$ be directions in $\mathbb{R}^k$, where $k\ge 2$. A multiset $X$ of $n$ points of $\mathbb{R}^k$ projects to the $m$ multisets of numbers $\{\{x\cdot d_j : x\in X\}\}$, or equivalently to the $m$ sorted lists of these numbers. How many directions are needed for these projections to determine every multiset of $n$ points? Two simple bounds are known in every dimension: more than $(k-1)\log_2 n$ directions are always needed, and $(k-1)n+1$ directions in general position always suffice. In the plane much more is known: Matousek, Privetivy and Skovron showed that almost every choice of $O(\log n \log\log n)$ directions suffices. Whether anything similar holds in higher dimensions was left open by Dym, Wellershoff, Tsoukanis, Levy and Balan. We observe that two lemmas of Hair and Sahai, proved for list recovery of random linear codes, answer that question, and by tightening their argument we show that in every dimension almost every choice of $(4k-2)\ln(2n)\ln(k\log_2 2n)+k+1$ directions suffices. For $k\le 10$ this beats the linear bound once $n$ is larger than about 100: for example, 144 directions suffice for multisets of 1000 points in the plane, and an exact computation lowers this to 133. Letting some of the random blocks in their argument fail removes a factor $\log k$: almost every choice of $O(k\log n\log\log n)$ directions suffices, uniformly in $k$ and $n$. We also show that $2k-1$ directions never determine three points, so that the logarithmic lower bound is not tight; that every $m$ directions in the plane fail on some pair of multisets of size $O(1.65^m)$, improving the bound $O(1.80^m)$ of Matousek, Privetivy and Skovron; and that for each $k$, $m$ and $n$, either almost every choice of $m$ directions works or almost none does.
- [95] arXiv:2611.13693 (replaced) [pdf, html, other]
-
Title: Rotating Walks, Derandomized Squares, and Permutation Conjugated WalksSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Probability (math.PR)
Using the recent strong convergence results of Bordenave and Collins (Annals of Mathematics) and Chen et al. (Annals of Mathematics), we study the average case behavior of rotating random walks of Cohen and Maor (STOC 2023) and the derandomized square construction of Rozenman and Vadhan (RANDOM 2005).
Concretely, we prove a conjecture of Cohen et al. (ITCS 2025) regarding the average case behavior of derandomized squaring for random graphs and show that the existential bounds of Cohen and Maor for their rotating random walk construction hold with high-probability for random graphs. Using the results of O'Donnell and Wu (FOCS 2020), we can in polynomial time construct a family of graphs and rotations which almost saturate the bounds of Cohen and Maor, and meet the bounds conjectured by Cohen et al. for all vertex-transitive auxiliary graphs of fixed degree in the derandomized square.
Finally, we study independent random permutation conjugates of deterministic regular graph adjacency matrices. We prove quantitative weak convergence to freely independent tree adjacency operators when the degrees are fixed and the girths tend to infinity. Separately, a covering argument gives deterministic spectral lower bounds for polynomials with non-negative coefficients, recovering the lower bound of Cohen et al. for rotating walks. - [96] arXiv:2611.22254 (replaced) [pdf, html, other]
-
Title: Between proper and strong edge-colorings of graphs with maximum degree at most fourComments: 12 pages, 8 figuresSubjects: Combinatorics (math.CO)
A $(1^j,2^k)$-packing edge-coloring of a graph $G$ is a partition of its edge set $E(G)$ into $j$ matchings and $k$ induced matchings. It can be viewed as intermediate colorings between proper and strong edge-coloring. The study of this topic on subcubic graphs has drawn considerable attention recently, with many conjectures and open problems proposed and resolved. However, very few results are known for graphs with maximum degree four or more. Henderson, Kennedy, and Santana showed that every graph with degree at most four has a $(1,2^{19})$-packing edge-coloring and a $(1^2,2^{17})$-packing edge-coloring.
In this paper, we improve the results of Henderson, Kennedy, and Santana by showing every graph with degree at most four has a $(1,2^{17})$-packing edge-coloring. As a corollary of our result, every graph with degree at most four has a $(1^2,2^{16})$-packing edge-coloring. - [97] arXiv:2611.23647 (replaced) [pdf, html, other]
-
Title: Removable forests in $k$-connected and $k$-edge-connected graphsComments: 9 pagesSubjects: Combinatorics (math.CO)
We prove the forest conjecture of Clay and Jordán: Let $k\ge1$ be an integer and let $F$ be a forest with $m$ vertices and $e$ edges. If a $k$-connected graph $G$ has minimum degree at least $\max\{k+e,m-1\}$, then it contains a copy of $F$ whose edge deletion preserves $k$-connectivity. We also prove the $k$-edge-connectivity version.
- [98] arXiv:2611.24775 (replaced) [pdf, html, other]
-
Title: A disproof of the van Emde Boas--Kruyswijk conjecture on the Davenport constantSubjects: Combinatorics (math.CO); Number Theory (math.NT)
The Davenport constant $D(G)$ of a finite abelian group $G$ is the smallest positive integer $\ell$ such that every sequence $S$ with terms from $G$ and with length $|S| \ge \ell$ has a nontrivial zero-sum subsequence. A long-standing conjecture, first proposed by van Emde Boas and Kruyswijk in 1969, states that $D(C_n^r)=r(n-1)+1$ for all positive integers $n$ and $r$. We disprove this conjecture for every exponent $n=2k$ with $k\ge3$ odd. For each such $n$, we prove that $D(C_n^r)>r(n-1)+1$ for every $r\ge 8n-7$.
- [99] arXiv:2607.03405 (replaced) [pdf, html, other]
-
Title: Oddomorphisms, Split-Off Minors, and the Strong Roberson ConjectureComments: To appear in the proceedings of CSL 2027. 22 pages. Simplified proof of Theorem 6, improved exposition, and updated referencesSubjects: Discrete Mathematics (cs.DM); Logic in Computer Science (cs.LO); Combinatorics (math.CO)
We show that the existence of an oddomorphism from a graph $F$ to a graph $G$ does not imply that $G$ is a minor of $F$. This answers a question posed by Roberson (2026) and shows that the CFI graphs cannot be used to prove the Strong Roberson Conjecture. Additionally, we introduce the concept of a split-off minor and show that the existence of an oddomorphism from $F$ to $G$ implies that $G$ is a split-off minor of $F$. Consequently, every class that is closed under taking split-off minors and disjoint unions is homomorphism distinguishing closed. The split-off minor relation is the first minor-like structural relation shown to have this property, marking a meaningful advancement in our understanding of the interaction between structural graph containment and homomorphism indistinguishability relations.
- [100] arXiv:2607.24033 (replaced) [pdf, html, other]
-
Title: Continuous solutions of the complex Kac--Bernstein functional equation on the integers and the real numbersComments: 26 pages, 3 tablesSubjects: Classical Analysis and ODEs (math.CA); Combinatorics (math.CO); Group Theory (math.GR); Probability (math.PR)
In this paper, the continuous solutions of the complex Kac--Bernstein functional equation \[ f_1 ( u + v ) f_2 ( u - v ) f_1 ( u' + v' ) f_2 ( u' - v' ) = f_1 ( u + v' ) f_2 ( u - v' ) f_1 ( u' + v ) f_2 ( u' - v ) \] are classified for $ \mathbb{ Z } $ and $ \mathbb{ R } $. By using this classification for $ \mathbb{ Z } $, we consider a generalization of the Kac--Bernstein theorem on the one-dimensional torus $ \mathbb{ T } $ by Baryshnikov--Eisenberg--Stadje from probability Borel measures to complex Borel measures. Similarly, the original Kac--Bernstein theorem on $ \mathbb{ R } $ is generalized from probability Borel measures to complex Borel measures.
- [101] arXiv:2609.25174 (replaced) [pdf, other]
-
Title: A geometric realization of socle-projective categories for posets of type $\mathbb{D}$Comments: 40 pages, 11 figuresSubjects: Representation Theory (math.RT); Combinatorics (math.CO)
We introduce posets of type $\mathbb{D}$, a family of posets described by an admissible Dynkin quiver of type $D_n$ together with a compatible set of extra arrows (alien arrows), and show that their socle-projective representation category is of finite representation type. Continuing, in the same spirit, a program initiated for posets of type $\mathbb{A}$ [R. Schiffler, R-J. Serna, A geometric realization of socle-projective categories for posets of type $\mathbb{A}$, J. Pure Appl. Algebra 224 (2020), no. 12, 106436], we build on an existing geometric model for cluster-tilted algebras of type $D_n$, whose geometric combinatorics is more intricate than that of type $\mathbb{A}$. Our main result establishes a $\Bbbk$-linear categorical equivalence $\Theta$ between a full subcategory $(\mathcal C/T)_F$ of the arc category of a punctured $(n+3)$-gon, whose objects are certain $sp$-arcs, and the category of finitely generated socle-projective $\Bbbk\mathscr{P}$-modules, for $\mathscr{P}$ a poset of type $\mathbb{D}$. As a consequence, when the set of alien arrows is empty, we conclude that the cluster subalgebra generated by the $sp$-arcs coincides with the full cluster algebra.
- [102] arXiv:2610.33131 (replaced) [pdf, html, other]
-
Title: Locally eventually onto cellular automataComments: 33 pages, minor revisionSubjects: Formal Languages and Automata Theory (cs.FL); Discrete Mathematics (cs.DM); Combinatorics (math.CO); Dynamical Systems (math.DS); Cellular Automata and Lattice Gases (nlin.CG)
We give a new checkable criterion to ensure that a one-dimensional cellular automaton on a finite alphabet is open and locally eventually onto. In this setting, openness is equivalent to being n-to-1 for some n and therefore implies surjectivity. Bipermutive cellular automata are known to be open and locally eventually onto, while open cellular automata that are neither bipermutive nor bijective appear to have received less attention. Building on Sutner's work with de Bruijn graphs, we describe a method for deciding openness and at the same time determining n. We then introduce the notion of block-regularity of local rules as a generalization of bipermutivity and prove that it implies openness. We further identify two conditions that, together with block-regularity, ensure that every nonempty cylinder set is mapped onto the whole configuration space after a finite number of iterations, and hence that the cellular automaton is open and locally eventually onto. The appendix provides the algorithms that check these finite criteria and then presents examples of open, locally eventually onto, non-bipermutive cellular automata for small diameters.
- [103] arXiv:2610.36372 (replaced) [pdf, html, other]
-
Title: Morse-Maxwell Theory for Directed Acyclic GraphComments: 25 pagesSubjects: Algebraic Topology (math.AT); Combinatorics (math.CO)
The Maxwell graph of a directed acyclic graph records the extrema of its iterated basin and hill boundaries. Their unweighted counts need not satisfy Morse inequalities, and the reduction can change homology. We assign multiplicities using the reduced homology of lower and upper order links and retain every vertex with nonzero local homology. This modified reduction preserves both hierarchies, the local groups, and the homology of all sublevel and superlevel order complexes. Its Morse numbers satisfy the weak and strong Morse inequalities over any field. We give explicit formulas in low dimensions and for complete layered graphs. We also construct local Morse numbers for path homology and prove agreement with the reachability construction on complete layered graphs, including those without transitive arrows. Counterexamples distinguish the homology theories and show that local Morse degrees need not equal vertex depths. A comparison with discrete-gradient methods explains the role of auxiliary choices.
- [104] arXiv:2610.41703 (replaced) [pdf, html, other]
-
Title: Exchange graphs and $τ$-tilting complexes of surface rigid algebrasComments: 42 pages, 5 figures; added results on spherical homotopy types; revised exposition and titleSubjects: Representation Theory (math.RT); Combinatorics (math.CO)
Let $A=\Lambda_{\mathbf R}$ be the surface rigid algebra associated with a partial tagged triangulation $\mathbf R$ of a punctured marked surface with nonempty boundary, and let $C_A$ be the Cartan matrix of $A$. We classify the connected components of the support $\tau$-tilting graph of $A$. For connected $A$, such a graph is disconnected if and only if $A$ is non-local and weakly symmetric with $\operatorname{rank}C_A=1$. The graph then has exactly two components. The completion graph of every nonzero basic $\tau$-rigid pair over connected $A$ is connected. When $\mathbf R$ is nonempty and all arc endpoints are punctures, we construct an explicit homotopy equivalence from the realization of the support $\tau$-tilting complex to a sphere of dimension $\operatorname{rank}C_A-1$. Under the same hypothesis, $A$ is $\tau$-tilting finite if and only if $C_A$ is positive definite. In the finite case, we give a root-system realization of the $g$-vectors of indecomposable $\tau$-rigid pairs, with types $A$, $D$ and $C$ determined by the tagged surface configuration.
- [105] arXiv:2611.23485 (replaced) [pdf, html, other]
-
Title: Ramsey Theory for Edge IdealsComments: 12 pages. Two typos in the proof of Theorem 5 removedSubjects: Commutative Algebra (math.AC); Combinatorics (math.CO)
We initiate the study of Ramsey theory for edge ideals. The edge ideal I_G is generated by the monomials x_ux_v for all edges uv of G. A central invariant measuring structure in algebraic geometry and commutative algebra are the betti number beta_{i,j}(S/I) for some ideal I in a ring S. We prove the Ramsey Theorem for Edge Ideals: For any betti number indices i,j, and any number of colors m, there is a graph F such that for every m-coloring of the edges of F, there is a color l such that beta_{i,j}(S/I_{F_l}) >0, where F_l is the subgraph of F whose edges are in color l. Moreover, the number of vertices of F is at most jm^2.