Applied Math · Mathematics & Statistics
Combinatorics
The newest papers in Combinatorics that ReadSearch has read, newest first. Each links to its own page, with its authors, date, where it was published and the original.
228 papers, from 31 August 2026 to 5 November 2026: 168 arXiv preprints and 60 OpenAlex records.
Get the few papers worth your time in Combinatorics every morning.
Follow Combinatorics and ReadSearch reads its new papers each day, then brings you the few worth reading, each with its key finding in a sentence.
Newest papers, page 6
Selecting the 7th Smallest of 16 Elements Takes Exactly 28 Comparisons
Let $V_i(n)$ denote the minimum worst-case number of comparisons needed to find the $i$-th smallest of $n$ distinct elements.Finding non-bisimplicial and triad-free minimal separators
A $u\hbox{-}v$ separator in $G$ is a set $S\subseteq V(G)\setminus\{u,v\}$ such that there is no $u\hbox{-}v$ path in $G\setminus S$.QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
A hereditary graph class has strongly edge-sublinear separators if, for some constant $0 \leqslant b < 1$, every graph in the class with $m$ edges admits a balanced separator of size $\mathcal…AI Discovery in Combinatorics: From Problems to Solutions and Back to Bigger Problems
We introduce $qt$Bench, a benchmark of 29 open problems in algebraic combinatorics.The Online Steinitz Problem
Inspired by Steinitz's celebrated result (1913) and recent online vector-balancing results of Kulkarni et al. (2024) and Aden-Ali (2026), we introduce the online Steinitz problem: $T$ vectors in…Exponential Local Search in Bounded-Occurrence MAX-CSP
We study the number of improving steps that local search may require for $(2,2,r)$-MCA (Maximum Constraint Assignment), a bounded-occurrence version of MAX-CSP with valued constraints in which every…Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs
Every 3-regular graph of girth at least $g$ has a cut containing at least a fraction $M_g$ of its edges, and the best rigorous bounds at large girth are $0.912\le \lim_{g\to\infty}M_g \le 0.92386$.The symmetry group of Turk's head knots
For p, q >= 3 with gcd(p,q) = 1 we show that the symmetry group of the Turk's head knot Th(p,q), the closure of the braid (sigma_1 sigma_2^{-1} sigma_3 sigma_4^{-1} ... sigma_{p-1}^{+-1})^q, is the…FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
FirstFit colors each arriving vertex with the smallest positive integer absent from its previously colored neighborhood.Two Linear Programs are Better than One
The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it.Stabilizer entropy cones as self-dual slices of linear rank cones: a five-party gap and dependence on the local dimension
Entanglement entropies of multipartite pure states satisfy linear inequalities; for stabilizer states, the backbone of quantum error correction, the achievable entropy vectors generate a convex cone.On the OpenAI proof that Landau-Siegel zeros do not exist
A recent manuscript of OpenAI asserts that Landau-Siegel zeros do not exist.Hull Variation in Symplectic Linear Codes
We study the variation of hull dimensions of symplectic linear codes under equivalence transformations preserving the symplectic distance.Ordinary and measurable colorings of Euclidean three-space
A proper coloring of Euclidean space is a coloring that assigns different colors to points at distance one.Harmonic Reduction of Spin-Coupled Grover Walks on Hypercubes via Quantum Bernoulli Noises
We consider spin-coupled Grover walks on hypercubes within the framework of quantum Bernoulli noises (QBN).Quantum-assisted rendezvous on hypercubes: a quantum Bernoulli noise approach
We study quantum-assisted balanced rendezvous on the $d$-dimensional hypercube in a one-step two-agent quantum-walk framework, where the two agents move the same Hamming distance and meet at a…Polynomial directed treewidth forces a large bramble with congestion two
Brambles of constant congestion in directed graphs have interesting structural and algorithmic applications, and it is desirable to find the smallest function $f_c(k)$ such that if a digraph has…Bipartite Carrier Compression and Machine-Certified Bounds in Schönhage Trilinear Multiplication Tensors
Under the conditional framework breaking the longstanding O(n log n) integer multiplication barrier (originating from OpenAI Preprint #109), the asymptotic time complexity exponent T(n) = O(n (log…Cardinalities of Kiselman monoids and their parity asymptotics
The cardinalities of Kiselman's semigroups $K_n$ are known to grow double exponentially in $n$: the sequence $2^{-n/2}\log_2|K_n|$ converges along the even and odd $n$ subsequences to positive…Restricting Odd Antiholes in Critical Graphs via List Coloring
By the Strong Perfect Graph Theorem, every graph whose chromatic number exceeds its clique number contains an odd hole or an odd antihole.