Theory & Algorithms · Computer Science & AI
Discrete Mathematics
The newest papers in Discrete Mathematics that ReadSearch has read, newest first. Each links to its own page, with its authors, date, where it was published and the original.
129 papers, from 4 September 2026 to 5 November 2026: 129 arXiv preprints.
Get the few papers worth your time in Discrete Mathematics every morning.
Follow Discrete Mathematics 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
First-Order Model Checking on Monadically Dependent Graph Classes
Monadically dependent graph classes are those in which first-order logic cannot encode all graphs.Low-Temperature Sampling via Equilibrium Disagreements
We develop a new framework for sampling at low temperatures using Glauber dynamics.Sublinear Metric Distortion for Matching
We study metric distortion in one-sided matching.Single-Variable Connectivity in Random $k$-SAT
We resolve longstanding questions about connectivity, reconstruction,and looseness in random $k$-SAT, for sufficiently large fixed $k$ as the number $n$ of variables tends to infinity…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$.Computing Forest Degree Realizations with Minimum Cardinality Domination
In the Degree Realization problem with respect to a family $\mathcal{P}$ of graphs the input is a non-increasing sequence $d = (d_1,\ldots,d_n)$ of positive integers, and the goal is to decide…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.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.Distributionally Robust Search: The Power of Information and the Limits of Moments
We study binary search for a target drawn from a distribution on $n$ ordered elements.Abelian embeddings make useful promises: approximation of detrivialised equations
We study the following family of search problems: given a system of equations $x+y+z\equiv 0\pmod p$ promised to admit a solution that is nonconstant on every equation, find a $c$-colouring of the…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…The Power of Bidegeneracy for Hypergraph Data Structures
A hypergraph $H = (V,E)$ describes a set system over a vertex universe $V$.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.Recognizing Label-Connected Graphs
In classical gossiping, each participant initially knows a distinct piece of information.Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms
Using the bisection bound of Monien and Preis, Fomin and Høie proved in 2006 that every graph of maximum degree 3 on $n$ vertices has pathwidth at most $n/6+o(n)$.Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing
We study weighted edge coloring, where each edge of a graph $G$ has a weight in $(0,1]$, and colors are assigned so that the incident weight of each color at every vertex is at most one.The Optimizer's Windfall: Bounding Hindsight Gain under Random Restrictions
Suppose an optimization problem is randomly restricted, independently on each variable, and re-optimized after the restriction is revealed.