New papers on Combinatorics & discrete math

The best of the week

• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  Circular s-choice parking functions: an exact closed formula via rotational symmetry

  Exploiting rotational symmetry in the spirit of Pollak's proof of the count $(n+1{)}^{n-1}$, we prove that the empty spot is exactly equidistributed, which yields the closed formula $m^{n-1}{\left(\genfrac{}{}{0ex}{}{m-sd+s-1}{s-1}\right)}^n$ for the number of preferences leaving any prescribed spot empty.

  Hac\`ene Belbachir, Asma Recioui, Abdelhakim Ait-Zai — arXiv

  PreprintClaims a big step

  Save
• Math & statistics/Combinatorics & discrete mathSep 25, 2026

  Thinning and sprinkling: from robust sampling to almost Hamiltonicity

  We develop the thinning--sprinkling technique, a general method for proving robustness of graph properties under random vertex sampling.

  Micha Christoph, Zach Hunter, Benny Sudakov — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 21, 2026

  Condensed configurations and valuative matroid invariants

  We show that their inverse incidence matrices give explicit Schubert expansions and hence determine every valuative or covaluative matroid invariant.

  Jens Niklas Eberhardt — arXiv

  PreprintClaims a big step

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

  To address this problem, we introduce and study multidimensional cyclically permutable codes (CPCs), for which every cyclic translate uniquely determines both the original codeword and the applied translation.

  Yubo Sun, Yijun Zhang, Gennian Ge — arXiv

  PreprintReal-world use

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Simple symmetric Venn diagrams with 17 and 19 curves

  We exhibit simple, rotationally symmetric Venn diagrams with 17 curves and with 19 curves: n Jordan curves carried to one another by rotation through 2{\pi}/n, with every one of the 2^n regions present and connected and, since the diagrams are simple, every crossing on exactly two curves.

  Chris Dzoba — arXiv

  PreprintCode available

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

  Based on the bipartite graph model, we present the explicit capacity region of the general det-BC and a deterministic capacity-achieving coding scheme.

  Yiyu Qiu, Wei Chen, H.Vincent Poor — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Graphs with Minimum Algebraic Connectivity I: Proofs of Aldous-Fill and Guiduli-Mohar Conjectures

  We prove the Aldous--Fill conjecture and the Guiduli--Mohar conjecture, as well as the corresponding conjecture for $d$-regular graphs of fixed odd degree.

  Maryam Abdi, Ebrahim Ghorbani — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Lower Bounds for all List-Decodable Deletion Codes

  We prove a lower bound of ${\Omega }_k(2^{n}t{\log }^{1/t}n/n^{k+k/t})$ on the optimal size of a $t$-list decodable $k$-deletion code, giving a $\sqrt{\log n}$ improvement over the previously best known bounds for $2$-list decodable $2$-deletion codes [GH21] and providing the first nontrivial lower bound when $t>2$ or $k>2$.

  Andrew D. Lin — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 24, 2026

  Cubical Sheaf Complexes with Constant Expansion with Applications to Asymptotically Good qLTCs

  For every fixed integers $r\ge 4$ and $2\le k\le r-2$, we construct $r$-dimensional cubical sheaf complexes whose degree-$k$ CSS codes have positive constant rate, linear distance, and constant soundness, with bounded row and column weights.

  Yeyuan Chen, Miryam Mi-Ying Huang, Yinchen Liu and 1 more — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  Proof of Almkvist's conjecture on the unimodality of partition polynomials

  In this paper, we completely settle the conjecture.

  Jianxi Mao, Wenle Shi, Bao-xuan Zhu — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 24, 2026

  A Szemer\'edi-Trotter Theorem in Arbitrary Fields

  We prove that $m$ points and $n$ lines in $k^2$ determine $O((mn{)}^{2/3}+m+n+mn/p)$ incidences.

  Mark Lewko — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 21, 2026

  Finite deletion-induced saturation for every non-complete graph

  We prove, with finite certificate verification, that a finite graph $H$ admits such a finite graph $G$ if and only if $H$ is not complete.

  Haochen Liu — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 25, 2026

  Boolean threshold functions, neuron capacity, and memory retrieval

  In this paper, we show that the number $T_n$ of distinct Boolean threshold functions is \[ T_n=2\binom{2^n-1}{n}\bigl(1+O(n^{-99})\bigr).

  Xinyuan Xie — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth

  We determine the asymmetric homomorphism threshold from graphs of odd girth at least $7$ to triangle-free graphs, showing that ${\delta }_{hom}(\{C_3,C_5\},\{C_3\})=\frac{1}{9}$.

  Romain Bourneuf, Raphael Steiner, St\'ephan Thomass\'e and 1 more — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  On infinite families of $[P_n]$-irregular graphs

  We prove that there exist infinitely many $[P_n]$-irregular graphs for any path $P_n$ of order $n\ge 3$.

  Tatiana Dovzhenok, Ilya Lukashenko, Andrei Mikhalev and 1 more — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 25, 2026

  The Marcus-Minc Transform Inequality

  Then the permanent of A is at least the permanent of the new matrix.

  Yair Lavi — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  The Last Seven Open Radii for Perfect Codes in the Johnson Scheme

  In this paper, we prove that there are no nontrivial $e$-perfect codes in the Johnson scheme for $e\in \{1,2,4,9,10,12,16\}$.

  Xiande Zhang, Wenjie Zhong — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 25, 2026

  The coarse Erd\H{o}s-P\'{o}sa theorem

  We prove the coarse Erd\H{o}s-P\'{o}sa conjecture of Georgakopoulos and Papasoglu.

  Sandra Albrechtsen, Marthe Bonamy, Romain Bourneuf and 1 more — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  Searching for Primes: A Neural AlphaZero Approach to a Factoring Game

  Consequently, solving the game for a balanced-semiprime target is equivalent to integer factoring.

  Marcel Crasmaru — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 25, 2026

  A Combinatorial Proof of Hilton's Conjecture and Beyond

  Using refined absorption, we prove that for every integer $g\ge 1$ and real $\gamma >0$, and for sufficiently large $n$, there exists an $n^{-1+\gamma }$-spread distribution on Latin squares of order $n$ and girth at least $g$ that have no proper subsquares.

  Thomas Lesgourgues, Luke Postle — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds

  In this paper, we determine the precise asymptotics of the number of parts of stable regularity equipartitions in terms of the Littlestone dimension: every graph $G$ of Littlestone dimension $\mathrm{Lit}(G)\le \ell$ has a regular equipartition into excellent sets with $(1+o_{ϵ\to 0,\ell }(1))\cdot {ϵ}^{-\ell -1}$ parts and in the other direction, for every $\ell \in {\mathbb{N}}_{+}$, there is an infinite family of graphs, all of Littlestone dimension $\ell$, whose equipartitions into good sets must have size at least $(1+o_{ϵ\to 0,\ell }(1))\cdot {ϵ}^{-\ell -1}$.

  Leonardo N. Coregliano, Fernando G. Jeronimo — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs

  We prove a unified theorem: for arbitrary positive integers $d_1,\dots ,d_s$, every ${\sum }_{i=1}^s{d}_i(d_i+1)$-connected graph contains pairwise edge-disjoint spanning subgraphs $H_1,\dots ,H_s$ such that $H_i$ is $d_i$-rigid for every $i$.

  Hanzhi Bai, J{\o}rgen Bang-Jensen, Jin Yan — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  The Three-Dimensional Erd\H{o}s Box Problem Has Exponent $11/4$

  We construct a family of box-free hypergraphs matching Erd\H{o}s's upper bound: for each $q=2^m$ ($m\ge 1$), our hypergraph has $q^4$ vertices in each part and $q^{11}$ edges, establishing that $z(n)=\Theta (n^{11/4})$.

  Dean Menezes — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  The Partial List Colouring Conjecture is False

  This disproves the Partial List Colouring Conjecture of Albertson, Grossman and Haas.

  Jonathan A. Noel — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  A Phase Transition for Small Dense Subhypergraphs

  We determine $t_r(n,d,s)$ and obtain asymptotically sharp bounds in several parameter regimes.

  Peiru Kuang, Yan Wang — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  Extremal Least Common Multiples in Rows of Pascal's Triangle

  Our main asymptotic result is \[ \log a(n)=2n+O\!\left(n\exp\!\left(-c\frac{(\log n)^{3/5}}{(\log\log n)^{1/5}}\right)\right) \] for some absolute $c>0$, so $a(n{)}^{1/n}\to e^2$.

  Felix Huber — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 25, 2026

  Antichain polynomials of products of chains and minuscule posets

  We show that, for every connected minuscule poset $P$, if the antichain polynomial of $[k]\times P$ is palindromic, then it has only real and strictly negative zeros.

  Xi Chen, Yuxian Dong, Sihao Tang — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Minimising the harmonic sum of cycle lengths

  We prove this conjecture for all sufficiently large $k$, by showing the stronger statement that any $n$-vertex graph $G$ with $e(G)>(k-1)(n-k+1)$ and $n\ge 2k$ satisfies $s(G)\ge {\sum }_{\ell =2}^{k}1/(2\ell )$.

  Richard Montgomery, Aleksa Milojevi\'c, Alexey Pokrovskiy and 1 more — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  Bounded chromatic number of graphs with small clique number and large minimum degree

  We prove that every triangle-free graph with minimum degree at least $\frac{n}{3}$ is $4$-colorable and thereby settle a problem of Brandt and Thomass\'e (2005) at the threshold $\frac{n}{3}$.

  Jiaao Li, Xinyuan Li — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 21, 2026

  Wild frieze patterns over the integers

  Furthermore, we show that every finite simple directed graph arises as an induced subgraph of a directed graph ${\Gamma }_{2,n}(\mathbb{Z})$ for $n$ sufficiently large.

  Leon Eickhoff — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 24, 2026

  The Laplacian $S_{n,n}$ conjecture is true

  We prove all remaining cases and thus establish that the conjecture is true.

  Nathaniel Johnston — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 25, 2026

  Ramsey Theory for Product Trees

  We develop a Ramsey theory for leaf-generated subsets of finite products of trees.

  Alexander Fish, Sean Skinner — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number

  Namely, we prove that a hereditary graph class has strongly sublinear tree-independence number if and only if, for every fixed clique bound, its graphs of bounded clique number have strongly sublinear treewidth.

  Andrea Munaro — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 25, 2026

  S-meandric Permutations and Tangency Polynomials

  We give a realization criterion and show that the realizations of each realizable permutation form an affine space over the two-element field.

  Yury Belousov, Viktoriia Georgievskaia — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 24, 2026

  Smallest Cubic Non-1-Planar Graphs

  We show that the smallest cubic non-1-planar graphs have $30$ vertices.

  Sergey Pupyrev — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  Edge complexity of weighted graphs: involutory symmetries and NP-hardness

  A stronger separation for simple source graphs proves that additive $\frac{1}{256N^{\frac{7}{2}}}$ approximation of weighted edge complexity is NP-hard, even on connected graphs of odd order $N$ with at most two distinct positive integer weights, each at most $N^2$.

  Vishal Gupta, Alex Iosevich — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Improved upper bound on the number of distinct k-decks for any k and alphabet size by counting the independent parameters

  Writing $L_q(j)$ for the number of Lyndon words of length $j$ over an alphabet of size $q$, we deduce the improved upper bound \[ D_{q,k}(n)=O\!\left(n^{E_q(k)}\right),\qquad E_q(k)=\sum_{j=1}^{k}j L_q(j)-1 .

  Arman Nilforoushan, Farzad Parvaresh — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 25, 2026

  Thresholds and spread in set systems of bounded VC-dimension

  We prove that there is an absolute constant $C>0$ such that, if $\mathcal{F}$ has VC dimension at most $d\ge 1$, then $p_c(\mathcal{F})\le Cq(\mathcal{F})\log (d+1)$.

  Chong Shangguan — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 24, 2026

  Sparse Approximate Chromatic Profiles of Triangle-Free Graphs

  We prove a sparse version of the four-colour theorem of Brandt and Thomass\'{e}, answering a question of Allen, B\"ottcher, Kohayakawa and Roberts.

  Guorong Gao, Jialin He — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 21, 2026

  Automorphism groups of Cayley graphs on almost simple groups with normal connection sets

  We determine the full automorphism group of every connected Cayley graph on an almost simple group with a normal connection set.

  Mengyu Cao, Benjian Lv, Binzhou Xia — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 21, 2026

  On the Word-Representability of Tensor Product Graphs

  Among our main results, we prove that $W_{2n}\times G$, ${\mu }_{2n}\times G$, and ${\mu }_{2n}^{\prime }\times G$ are always word-representable for any graph $G$; that $K_n\times K_m$ is word-representable if and only if $\min \{n,m\}\le 3$; and that tensor products $G\times H$ containing $W_{2n+1}\times W_{2m+1}$ or ${\mu }_{2n+1}\times {\mu }_{2m+1}$ or ${\mu }_{2n+1}^{\prime }\times {\mu }_{2m+1}^{\prime }$ as induced subgraphs are non-word-representable.

  Nawaf Alshammari — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 24, 2026

  Exact local spectral thresholds for perfect matchings in $3$-graphs and $3$-partite $3$-graphs

  In this paper, we prove both perfect matching conjectures for large order.

  Pei Liu, Suil O — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 21, 2026

  Stellahedral Geometry of Partially Ordered Sets

  We show that the right augmented Chow polynomial of an Eulerian poset $P$ agrees with the toric $h$-polynomial of the stellahedral transform of $P$.

  Tommaso Faustini, Luis Ferroni, Ludovico Piazza — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Exact Ehrhart Series of Birkhoff Polytopes via Constant Terms and Finite-Field Evaluation

  We present an exact method for computing this series using constant terms and finite fields.

  Xinru Jiang, Guoce Xin, Chen Zhang and 1 more — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree

  We completely determine the sensitivity, average sensitivity, and block sensitivity of ${\sigma }_{n,d}$ for every $1\le d\le n$.

  Yuan Li, Jing Zhang — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 24, 2026

  Monochromatic triangles with empty intersection and Kneser Ramsey numbers

  We make substantial progress toward the problem of Holmsen, Hrusak, and Rold\'an-Pensado by proving that the conclusion already holds for every $k\ge 2$ whenever $n\ge 2k+1$.

  Igor Araujo — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  The existence and uniqueness of magic-faced hypercubes, and applications to Khajuraho most-perfect magic squares, cubes, and hypercubes

  We prove that a magic-faced hypercube of order $2$ exists in every dimension $n\ge 0$, and that it is unique up to a certain natural set of transformations of size $2^n(n+1)!$ when $n$ is even and $2^{n}n\cdot n!$ when $n$ is odd.

  Manjul Bhargava — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 22, 2026

  Positive formulas for q-Zeta numerators of Ferrers-cell posets

  We give explicit positive formulas for Chapoton's $q$-Zeta numerators of the Ferrers-cell posets $F_{\mathbf{b}}=\{(i,c):1\le i\le r,i\le c\le b_i\}$, where $b_1\ge \cdots \ge b_r\ge r$, and for every interval of their minimum-augmented lattices.

  Qihang Wang, Weiye Li — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Latin Eulerian Numbers

  We introduce Latin Eulerian numbers $\text{LE}\genfrac{}{}{0ex}{}{n}{k_1,\dots ,k_n}$, a multivariate refinement of classical Eulerian numbers counting order-$n$ Latin squares by column ascents.

  Madjid Mirzavaziri, Daniel Yaqubi — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 21, 2026

  Duality and minors for embeddings of graphs in pseudosurfaces

  We define the class of pseudocellular embeddings of graphs in pseudosurfaces, which allow pinchpoints at places other than vertices, in particular in the middle of faces or edges.

  Blake Dunshee, M. N. Ellingham, and Joanna A. Ellis-Monaghan — arXiv

  Preprint

  Save