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 10
Counting and Covering in Nearest-Neighbour Representations of Boolean Functions
We study the number of prototypes needed to represent Boolean functions by nearest-neighbour classification.Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis
Local-to-global techniques for establishing spectral gaps have played a central role in the modern theory of Markov chain mixing times and the theory of high-dimensional expanders.Improved Algorithms for Beck--Fiala with Bounded Sets
We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size.Sharp spectral norm concentration of sparse random tensors
We prove a sharp concentration inequality for the spectral norm of sparse random tensors with independent Bernoulli entries.Fast FPRAS for the Permanent
We give an FPRAS for the permanent of an $n\times n$ $0/1$ matrix with running time $\widetilde{O}(n^{3.5}\varepsilon^{-2})$.Kernel--wreath constructions and infinite families of finite simple skew braces
We introduce a kernel--wreath construction for finite skew braces.A quantitative tree-likeness bound from average hyperbolicity
Chatterjee and Sloman proved that a bounded measurable similarity function with sufficiently small average Gromov hyperbolicity admits a tree representation with small mean approximation error.The Complexity of Undirected Partizan Edge Geography
Partizan Edge Geography is a two-player game on a graph where each player has their own token on a vertex and moves their token to a neighbor in a turn removing the edge.Improved Approximation for Unsplittable CVRP via a Greedy Approach
We devise a polynomial-time $3.159$-approximation algorithm for the metric unsplittable Capacitated Vehicle Routing Problem.List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$
We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$.Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with $\|\sum_i s_i H_i\|\le 13\|\sum_i…PrecPack: An Efficient Open-Source Exact Solver for Bin Packing with Generalized Precedence Constraints
Efficient resource use in packing and assembly-line applications requires decisions that jointly account for capacity and precedence constraints.Structural Parameterizations for Eternal Vertex Cover
Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph $G$.A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution
The demand matching problem generalizes both the knapsack problem and the $b$-matching problem.The Complexity of Weak Partition Connectivity in Hedgegraphs
We prove that the integer-threshold decision problem for weak partition connectivity in hedgegraphs is NP-complete, answering an open question about its computational complexity.The threshold for online balancing of i.i.d. binary vectors
Consider the task of online vector balancing for stochastic arrivals $X_1,\ldots,{X_T}$, where the $X_i$ are independent uniformly random $d$--sparse binary vectors in $\{0,1\}^n$.Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231
We give an exact algorithm counting the permutations that avoid a fixed pattern from the following family: the direct sum of an increasing pattern and the pattern 231.A Cheeger Inequality for Hypergraphs and Its Applications
Hypergraphs provide a natural framework for modeling higher-order relationships, but the development of spectral techniques with provable guarantees for general non-uniform hypergraphs remains…Relative commuting probability and BFC-type results for finite skew braces
We develop a probabilistic approach to the structure of finite skew left braces, motivated both by classical commuting probability in finite group theory and by the role of skew left braces in the…Kusner's conjecture is false for $p>4$
An equilateral set is a set of points in a metric space whose pairwise distances are all equal.