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
A Universal Threshold Theory for Local Properties of Random Linear Codes
Thresholds for local properties tell us which guarantees to expect from random linear codes (RLCs) and help us carry those guarantees over to structured codes.First-Order Model Checking on Monadically Dependent Graph Classes
Monadically dependent graph classes are those in which first-order logic cannot encode all graphs.The probabilistic bound for perfect hashing is sharp only for binary alphabets
We investigate the optimal asymptotic rate $R_q$ of perfect $q$-hash codes, a fundamental extremal problem in combinatorics, information theory, and computer science.All minimum cuts of symmetric submodular functions
We compute Cunningham's canonical decomposition of a symmetric submodular function on $n$ elements in $O(n^3)$ time.Tusnády's problem and online two-sample thinning
We determine the sharp order of discrepancy in Tusnády's problem in every fixed dimension $d\ge 2$.A Complete Characterization of $q$-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes
Let $\mathcal{C}_k$ be the doubly-extended Reed--Solomon code with parameters $[q+1, k, q-k+2]_q$.How Unbalanced Must a Latin Rectangle Be?
We view a $k\times n$ Latin rectangle as $n$ points in the grid $[n]^k$.A Polynomial Erdős-Pósa bound for Eulerian digraphs
In [Combinatorica 1996], Reed, Robertson, Seymour and Thomas proved Younger's conjecture dating back to 1973 that states that directed cycles have the Erdős-Pósa property.How many sorted projections determine n points in k dimensions?
Let $d_1,\dots,d_m$ be directions in $\mathbb{R}^k$, where $k\ge 2$.A $2.81^n$ upper bound on the number of stable matchings
We study the maximum number ${\rm SM}(n)$ of stable matchings in an instance with $n$ men and $n$ women.A Sub-$3^n$ Upper Bound on the Number of Stable Matchings
We study the problem of determining the maximum number of stable matchings.Finding full immersions is fixed-parameter tractable in labeled tour graphs
We give an $O_H(n^5)$-time algorithm to test whether an $n$-vertex labeled tour graph has a full immersion isomorphic to a labeled tour graph $H$.Monadically Dependent Graph Classes Have Almost Bounded Merge-Width
A graph class $\mathcal{C}$ is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from $\mathcal{C}$ using a fixed formula of first-order logic.Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space
A fault-tolerant (FT) connectivity oracle for an $n$-vertex graph $G=(V,E)$ determines whether $G- F$ is connected for any query set $F\subseteq E$.Using topology to reveal all mutually unbiased bases in dimension six
Mutually unbiased bases (MUBs) describe complementary quantum measurements: certainty in one basis gives no information about the others.Resolving Tusnády's Problem
We prove a lower bound of $Ω_d((\log N)^{d-1/2})$ for the worst-case combinatorial discrepancy of $N$-point sets with respect to anchored boxes in every fixed dimension $d\ge3$.Testing Implies Distance Estimation with Polynomial Loss
A tester decides whether a graph has a property or is far from having it.Glauber Dynamics for Sampling Colorings: Rapid Mixing above $(1+1/\mathrm{e})Δ$ via Hidden Hard-Core Models
We show that for every $γ>0$ and every sufficiently large $Δ$, the Glauber dynamics for proper $q$-colorings of any $n$-vertex graph of maximum degree $Δ$ has spectral gap $Ω_γ(1/n)$, and hence…A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs
A \emph{rainbow cycle} in a list-edge-colored graph is a cycle where no color appears more than once.A Low-Diameter Nash-Williams--Tutte Theorem
The Nash-Williams--Tutte theorem characterizes the existence of $k$ edge-disjoint spanning trees by a condition on every vertex partition.