Hexagon

math.CO — Combinatorics

A cubic variance bound for matching deficiency

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

Let $M$ be a uniformly random matching of a finite graph, let $D=\nu-\mathbb E|M|$ be its expected deficiency from a maximum matching, and let $V=\operatorname{Var}(|M|)$ . Kahn showed that $D$ and $V$ tend to infinity together, proved $D=O(V^4)$ when $V$ is bounded below, and conjectured $D=O(V^3)$ . We prove $D\le41V+104V^2+64V^3$ for every graph, confirming the conjecture, and show that the exponent is attained by connected bipartite graphs with perfect matchings. The proof combines alternating-path identities for monomer probabilities with the sharp estimate $|V(G)-V(G-v)|\le1/4$ .

Primarily AI-generated textHuman understanding: some partsmatching deficiencymatchingsvariance

Oct 14, 2026PDF ↗View work →

hexagon:2610.00223v1

math.NT — Number Theory

Long runs and rare patterns of a random completely multiplicative function

Contributed by Brice Pouly

Let $f$ be a random completely multiplicative function with independent symmetric signs at the primes. We study rare constant runs and prescribed words at logarithmic lengths, despite long-range multiplicative identities. A uniform weighted two-window square-relation estimate, with critical bound $O_\varepsilon(N^{5/3+\varepsilon})$ , separates exact rational relations from residual components. At critical intensity, this estimate gives Poisson comparisons retaining positions, exact excess lengths and signs. For dictionaries, uniform bounds under size and overlap conditions are complemented by typical bounds obtained by averaging the distance after fixing the dictionary. In a quantitatively controlled regime of diverging intensity, an exact one-word coupling by largest-odd-prime pivots compares the full signed run field under prescribed small-prime conditioning. For fixed admissible window parameters and almost every fixed realization of $f$ , run-start counts in prescribed near-macroscopic windows satisfy an empirical Poisson law along dyadic scales. In the exceptionally rare regime, a relative marked comparison separates the boundary event from bulk occurrences. Conditional on existence, the first location, sign and overshoot have a two-source lattice law with scale-dependent weights. The two overshoots use different clocks: prime rank at the boundary and integer distance in the bulk.

Primarily AI-generated textHuman understanding: no partsLean 4Poisson approximationboundary effectscompletely multiplicative functionsformal verificationlong runsrandom multiplicative functionsrare patternssquare-product relations

Oct 14, 2026PDF ↗View work →

Matching works

A cubic variance bound for matching deficiency

Long runs and rare patterns of a random completely multiplicative function

Advanced search

math.AC — Commutative Algebra
math.AG — Algebraic Geometry
math.AP — Analysis of PDEs
math.AT — Algebraic Topology
math.CA — Classical Analysis and ODEs
math.CO — Combinatorics
math.CT — Category Theory
math.CV — Complex Variables
math.DG — Differential Geometry
math.DS — Dynamical Systems
math.FA — Functional Analysis
math.GM — General Mathematics
math.GN — General Topology
math.GR — Group Theory
math.GT — Geometric Topology
math.HO — History and Overview
math.IT — Information Theory
math.KT — K-Theory and Homology
math.LO — Logic
math.MG — Metric Geometry
math.NA — Numerical Analysis
math.NT — Number Theory
math.OA — Operator Algebras
math.OC — Optimization and Control
math.PR — Probability
math.QA — Quantum Algebra
math.RA — Rings and Algebras
math.RT — Representation Theory
math.SG — Symplectic Geometry
math.SP — Spectral Theory
math.ST — Statistics Theory
cs.AI — Artificial Intelligence
cs.CC — Computational Complexity
cs.CG — Computational Geometry
cs.DM — Discrete Mathematics
cs.DS — Data Structures and Algorithms
cs.FL — Formal Languages and Automata Theory
cs.IT — Information Theory
cs.LO — Logic in Computer Science
cs.MS — Mathematical Software
cs.NA — Numerical Analysis
cs.SC — Symbolic Computation
math-ph — Mathematical Physics
quant-ph — Quantum Physics
stat.TH — Statistics Theory