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, page 2
Adjacency Labeling Schemes of Size $\log n+O(\log\log^* n)$ for Graphs of Bounded Treewidth
Gavoille and Labourel (ESA 2007) gave an adjacency labeling scheme of size $\log n+O(k\log\log n)$ for graphs of treewidth at most $k$, and asked whether $\log n+O(k)$ bits suffice.A King for Almost Everyone
A tournament is an orientation of a complete graph.A Family of Well-Behaved Multiflow Instances
We introduce a family of cut-sufficient instances for undirected multiflow that generalizes single-source planar and fully-planar instances.Monotone Local Search with Sample-Dependent Running Times
Monotone Local Search turns an algorithm that extends a given partial solution into an algorithm that finds a solution from scratch: sample a few elements, hope that they lie in an unknown solution…The Value of Steiner Hubs in Two-Hop Distance Labeling
Two-hop distance labelings were introduced in 2002 by Cohen, Halperin, Kaplan, and Zwick with hubs of two kinds: vertices of the graph, or, in their Steiner variant, arbitrary objects carrying…Metric Testing: A Characterization of One-Sided Testability
We give a unified framework for one-sided testability (constant-query testing) of metric families.Degree Realization with Maximum Matching
The Maximum Matching Degree Realization problem requires, for a sequence $d$ of $n$ positive integers, to compute a realizing graph(whose degree sequence corresponds to $d$) with the maximum…The C-3PO Framework: Algorithms for $\#\mathrm{BIS}$-Hard Problems on Graphs with Low Threshold Rank or High Girth
We give approximate counting and sampling algorithms for spin models on graphs of low threshold rank or high girth.Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\geq 2$
Given a simple undirected graph on $n$ vertices, random $k$-out sampling forms a spanning subgraph by having each vertex independently choose $k$ incident edges uniformly with replacement.Four-Coloring Planar Graphs in Linear Time
The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring?Layering and reverse extension for weighted $k$-path vertex cover
We study the weighted $k$-path vertex cover problem for any fixed integer $k \ge 2$, in which a vertex non-negatively weighted simple graph $G = (V, E)$ is given and one wants to find a…Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
For many optimization problems on random graphs, most prominently the largest independent set problem, natural algorithms reach only half the optimum, and such factor-two gaps are known to be sharp…Uniformity Testing for the Monomer-Dimer Model
We study uniformity testing for the monomer-dimer model on a known graph $G=(V,E)$.Local-to-Global Theorems Based on Cones with Applications to Graph Coloring
Local-to-Global theorems are a cornerstone of many of recent developments in theoretical computer science from coding theory and PCPs all the way to analyzing mixing time of Markov chains.Online Discrepancy of Sparse Random Vectors over Long Horizons
We study online vector balancing for independent sparse random vectors: each arrival is supported on a uniformly random set of $s$ of the $n$ coordinates, with nonzero entries equal to one (binary…Subgraph Isomorphism, Integer Linear Programming, and Lattices: A Linear Algebraic Framework
The subgraph isomorphism problem (SGI) asks a deceptively simple question: is a graph B found inside a parent graph A?Almost tight distributed approximation for domination in sparse graph classes
We study distributed approximation of Minimum Dominating Set in a very general class of sparse graphs, extending near-optimal approximation results from the minor-free setting to bounded expansion.A Polynomial-Time Algorithm for $k$-Path Vertex Cover Reconfiguration on Trees under Token Sliding
A $k$-path vertex cover ($k$-PVC) of a graph is a set of vertices meeting every path on $k$ vertices.Kempe Reachability with $k\geq 3$ Colors Is $\mathsf{PSPACE}$-Complete on Claw-Free Graphs
A \emph{proper vertex coloring} assigns colors to vertices so that adjacent vertices have distinct colors.Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings
Temporal graphs are graphs whose edge relation changes in discrete time steps.