Random matchings in linear hypergraphs

Abstract

For a given hypergraph $H$ and a vertex $v\in V(H)$, consider a random matching $M$ chosen uniformly from the set of all matchings in $H.$ In $1995,$ Kahn conjectured that if $H$ is a $d$-regular linear $k$-uniform hypergraph, the probability that $M$ does not cover $v$ is $(1+o_d(1))d^{-1/k}$ for all vertices $v\in V(H).$ This conjecture was proved for $k=2$ by Kahn and Kim in $1998.$ In this paper, we disprove this conjecture for all $k\ge 3.$ For infinitely many values of $d,$ we construct $d$-regular linear $k$-uniform hypergraph $H$ containing two vertices $v_1$ and $v_2$ such that $\mathcal{P}(v_1\notin M)=1-\frac{(1+o_d(1))}{d^{k-2}}$ and $\mathcal{P}(v_2\notin M)=\frac{(1+o_d(1))}{d+1}.$ The gap between $\mathcal{P}(v_1\notin M)$ and $\mathcal{P}(v_2\notin M)$ in this $H$ is best possible. In the course of proving this, we also prove a hypergraph analog of Godsil's result on matching polynomials and paths in graphs, which is of independent interest.

arXiv comment15 pages