A rate for the average vacancy of uniformly random matchings in linear hypergraphs
Abstract
Let M be chosen uniformly from all matchings of a finite linear k-uniform hypergraph H, and let q̅(H) be the average probability that a vertex is left uncovered. If H has maximum degree D and normalized average degree β=k|E(H)|/(|V(H)|D), then, for every fixed k≥ 2 and uniformly in the order, q̅(H) ≤ 1−β+(βk+oD(1))loglog D/log D. The underlying estimate is the order-uniform count log Z(H)≥ (|E(H)|/D)(log D−(k+oD(1))loglog D), and it also counts matchings of size (1−oD(1))|E(H)|/D. We prove this by sampling edges, deleting those incident with unusually large sampled degrees, and controlling only the total deleted mass before applying the Molloy-Reed list edge-colouring theorem. For d-regular H, a quantitative version of the earlier Asratian-Kuzjurin sampling-to-counting route, using the near-perfect-matching theorem of Gould and Kelly, sharpens the coefficient: for every fixed k≥ 3, supH q̅(H) ≤ (max{3,k−1}+od(1))loglog d/log d. Kahn's stronger pointwise prediction was disproved by Lee for k≥ 3. The qualitative averaged conclusion was already recorded by Kahn and Kim, crediting Anders Johansson, and also follows from the Grable-Asratian-Kuzjurin enumeration; neither source states a rate.
Related
- Perfect matchings in hypergraphs and Feige's inequality
- Random Signs into Matchings: A Godsil-Gutman Identity, Formalized in Lean 4 (Part I)
- Phase transition of random non-uniform hypergraphs
- A Proof of the Erdős Matching Conjecture for Large Matchings via Sharp Tail Probability for Sums of i.i.d. Nonnegative Random Variables
- Approximating Distributions on Vertex Degrees in Random Hypergraphs via Stein's Method
BibTeX
@misc{gupta2026rate,
title = {{A rate for the average vacancy of uniformly random matchings in linear hypergraphs}},
author = {Anish Gupta},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26133},
eprint = {2609.26133},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26133},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A rate for the average vacancy of uniformly random matchings in linear hypergraphs
AU - Anish Gupta
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.26133
UR - https://arxiv.org/abs/2609.26133
AB - Let M be chosen uniformly from all matchings of a finite linear k-uniform hypergraph H, and let q̅(H) be the average probability that a vertex is left uncovered. If H has maximum degree D and normalized average degree β=k|E(H)|/(|V(H)|D), then, for every fixed k≥ 2 and uniformly in the order, q̅(H) ≤ 1−β+(βk+o_D(1))loglog D/log D. The underlying estimate is the order-uniform count log Z(H)≥ (|E(H)|/D)(log D−(k+o_D(1))loglog D), and it also counts matchings of size (1−o_D(1))|E(H)|/D. We prove this by sampling edges, deleting those incident with unusually large sampled degrees, and controlling only the total deleted mass before applying the Molloy-Reed list edge-colouring theorem. For d-regular H, a quantitative version of the earlier Asratian-Kuzjurin sampling-to-counting route, using the near-perfect-matching theorem of Gould and Kelly, sharpens the coefficient: for every fixed k≥ 3, sup_H q̅(H) ≤ (max{3,k−1}+o_d(1))loglog d/log d. Kahn's stronger pointwise prediction was disproved by Lee for k≥ 3. The qualitative averaged conclusion was already recorded by Kahn and Kim, crediting Anders Johansson, and also follows from the Grable-Asratian-Kuzjurin enumeration; neither source states a rate.
ER -