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 5
Stable and Online Algorithms for Random Matrix Discrepancy
We study the average-case matrix discrepancy problem: given independent normalized $d\times d$ Gaussian orthogonal ensemble matrices $A_1,\dots,A_N$ and a fixed margin $κ>0$, find signs…Exact Locality Gaps for Matchable Semi-Matchings
An assignment of tasks to servers can resist every small improvement and still make tasks wait longer than necessary.$(α, β)$ Spanners and Hybrid Spanners with Nearly Tight Bounds
For an $n$-vertex undirected, unweighted graph $G=(V,E)$ and a positive integer $k$, we present new spanner constructions with $O_k(n^{1+1/k})$ edges that achieve nearly optimal guarantees for all…Quantum State Routing and Perfect State Transfer on Signed Graphs under Environmental Noise
Routing unknown quantum information across distributed communication networks requires autonomous, measurement-free mechanisms to prevent wave-function collapse.Quantum Černý complexity of binary words
We introduce the quantum Černý complexity $\mathrm{qc}(w)$ of a binary word $w$: the least dimension $d$ for which there exist quantum channels $A_0,A_1$ on $d\times d$ density matrices and a start…The Reach of Abelian Covers in Hypergraphs
Covers in hypergraphs are frequently studied to capture various forms of dependence between hyperedges.A Spectral Theory of Distortion in LLM Graph Reconstruction: Sharp Bounds and Empirical Characterization
Evaluations of graph reconstruction by language models typically report a single aggregate distance between the original and the reconstructed graph.On the Guo-Fang-Lu Algorithm for Komlos Discrepancy
We give an exposition of the recent polynomial time algorithm of Guo, Fang, and Lu for the Komlos problem.Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian Certificates
We give a randomized polynomial-time algorithm that, for every fixed $\varepsilon > 0$, colors every $3$-colorable $n$-vertex graph using $O\bigl(n^{(13-\sqrt{97})/18+\varepsilon}\bigr) \approx…Solving Vertex Integrity Faster than $2^n$
Vertex Integrity is a classical graph parameter measuring the vulnerability of a network to vertex failures.Odd Cycle Transversal on $H$-free graphs
\textsc{Odd Cycle Transversal} is a classic $\mathsf{NP}$-hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite, or equivalently…On Kernels and Leaves: Searching for Bare and Lush Trees
We study a variation of the classical Maximum (Minimum) Leaf Spanning Tree problem.Boolean threshold functions, neuron capacity, and memory retrieval
How much information can a single neuron remember?Vertex-Coloring Edge-Weighting: Kernelization and Generalization
An edge weighting of a graph induces a coloring of its vertices in which the color of a vertex is the total weight of the edges incident with it.Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?
One item set evaluated at two capacities $R<D$ produces two concave hulls of optimal value against cardinality.Transposition achieves OPT$+O(1)$ in polynomial time for IID list update
In the classical list update problem, a set of items must be stored in a list-type structure, where accessing the $i$-th element costs $i$.Factorisability of Low Dimensional Non-Negative Integer Matrices
We consider the problem of determining if a given two-dimensional nonnegative integer matrix $M$ is the product of two such matrices, excluding trivial units.Backtracking Candidate Elimination: A One-Pass Algorithm for the Chip Testing Problem
In the chip testing problem, we are given $n$ chips, strictly more than half of which are good.Minimum Sum Vertex Cover via Minimum Vertex Cover
The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered.Witness Set in Weak Visibility Polygons is Polynomial-Time Solvable
In the classical Art Gallery Problem (AGP), guards are placed in a polygon so that together they see every point.