HEXAGONbeta

A cubic variance bound for matching deficiency

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath.PR — Probability

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

Version 1 / Oct 14, 2026 / CC BY 4.0

Abstract

Let MM be a uniformly random matching of a finite graph, let D=ν−E∣M∣D=\nu-\mathbb E|M| be its expected deficiency from a maximum matching, and let V=Var⁡(∣M∣)V=\operatorname{Var}(|M|). Kahn showed that DD and VV tend to infinity together, proved D=O(V4)D=O(V^4) when VV is bounded below, and conjectured D=O(V3)D=O(V^3). We prove D≤41V+104V2+64V3D\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)∣≤1/4|V(G)-V(G-v)|\le1/4.

Provenance statement

This work was produced within the Bolzano project (https://bolzano.app), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking. Text origin: primarily AI-generated. Human understanding: some parts of this contribution have been checked and understood by a human. The manuscript received only limited human checking. The prior automated editorial and literature checks do not constitute human verification. The manuscript proves the cubic variance bound and a sharpness family. Classical matching methods are credited; absolute priority is not certified.

Tools used

Bolzano team
Bolzano

References

  1. J. Kahn, A normal law for matchings, Combinatorica 20 (2000), 339--391. doi:10.1007/PL00009835 (https://doi.org/10.1007/PL00009835).DOI
  2. O. J. Heilmann and E. H. Lieb, Theory of monomer-dimer systems, Communications in Mathematical Physics 25 (1972), 190--232. doi:10.1007/BF01877590 (https://doi.org/10.1007/BF01877590).DOI
  3. C. D. Godsil, Matching behaviour is asymptotically normal, Combinatorica 1 (1981), 369--376. doi:10.1007/BF02579458 (https://doi.org/10.1007/BF02579458).DOI
  4. L. Lovász and M. D. Plummer, Matching Theory , North-Holland Mathematics Studies 121 , North-Holland, Amsterdam, 1986; reprinted by AMS Chelsea Publishing, 2009.
  5. M. Jerrum and A. Sinclair, Approximating the permanent, SIAM J. Comput. 18 (1989), 1149--1178. https://doi.org/10.1137/0218077.DOI
  6. L. H. Harper, Stirling behavior is asymptotically normal, Ann. Math. Statist. 38 (1967), 410--414. https://doi.org/10.1214/aoms/1177698956.DOI
  7. J. Pitman, Probabilistic bounds on the coefficients of polynomials with only real zeros, J. Combin. Theory Ser. A 77 (1997), 279--303. https://doi.org/10.1006/jcta.1997.2747.DOI
  8. M. Michelen and J. Sahasrabudhe, Central limit theorems and the geometry of polynomials, J. Eur. Math. Soc. 28 (2026), no. 5, 2261--2305. https://doi.org/10.4171/JEMS/1530.DOI
  9. J. L. Lebowitz, B. Pittel, D. Ruelle and E. R. Speer, Central limit theorems, Lee--Yang zeros, and graph-counting polynomials, Journal of Combinatorial Theory, Series A 141 (2016), 147--183. doi:10.1016/j.jcta.2016.02.009 (https://doi.org/10.1016/j.jcta.2016.02.009).DOI
  10. Z. Du, T.-W. Chao and Y.-N. Yeh, Several improved asymptotic normality criteria and their applications to graph polynomials, Discrete Mathematics 346 (2023), no. 5, 113303. doi:10.1016/j.disc.2022.113303 (https://doi.org/10.1016/j.disc.2022.113303).DOI
Show all 16 referencesShow fewer references
  1. H. Zhang, M. Brunetti and J. Wang, Asymptotic normality for the coefficients of graph polynomials, Mediterranean Journal of Mathematics 23 (2026), 188. doi:10.1007/s00009-026-03186-0 (https://doi.org/10.1007/s00009-026-03186-0).DOI
  2. J. Kahn and J. H. Kim, Random matchings in regular graphs, Combinatorica 18 (1998), 201--226. https://sites.math.rutgers.edu/~jkahn/RM.pdf.link
  3. H. Lee, Random matchings in linear hypergraphs, Forum of Mathematics, Sigma 14 (2026), e117. doi:10.1017/fms.2026.10253 (https://doi.org/10.1017/fms.2026.10253).DOI
  4. A. Gupta, A rate for the average vacancy of uniformly random matchings in linear hypergraphs, arXiv:2609.26133v1 (2026). https://arxiv.org/abs/2609.26133.arXiv
  5. Z. Zheng, S. Zhang, J. Avigad, P. Tetali and S. Welleck, The Problem Is the Problem: Towards Scalable Mathematical Discovery, arXiv:2608.16977v1 (2026), Appendix C.7. https://arxiv.org/abs/2608.16977.arXiv
  6. C. D. Godsil, Matchings and walks in graphs, Journal of Graph Theory 5 (1981), 285--297. doi:10.1002/jgt.3190050310 (https://doi.org/10.1002/jgt.3190050310).DOI

Version history

  1. v1Submitted by Václav RozhoňInitial depositCurrentOct 14, 2026