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 $\overline{q}(H)$ be the average probability that a vertex is left uncovered. If $H$ has maximum degree $D$ and normalized average degree $\beta =k|E(H)|/(|V(H)|D)$, then, for every fixed $k\ge 2$ and uniformly in the order, $\overline{q}(H)\le 1-\beta +(\beta k+o_D(1))\log \log D/\log D$. The underlying estimate is the order-uniform count $\log Z(H)\ge (|E(H)|/D)(\log D-(k+o_D(1))\log \log 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\ge 3$, ${\sup }_H\overline{q}(H)\le (\max \{3,k-1\}+o_d(1))\log \log d/\log d$. Kahn's stronger pointwise prediction was disproved by Lee for $k\ge 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.

arXiv comment16 pages. Ancillary files include exact verification programs. Companion repository: https://github.com/agupta/average-vacancy-linear-hypergraphs