Random matchings in linear hypergraphs

For a given hypergraph H and a vertex v 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 + od (1) ) d^-1/k for all vertices v 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 3. For infinitely many values of d, we construct d-regular linear k-uniform hypergraph H containing two vertices v₁ and v₂ such that P (v₁ M) = 1 - (1 + od (1) ) d^{k-2} and P (v₂ M) = (1 + od (1) ) d+1. The gap between P (v₁ M) and P (v₂ 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.