Kahn's matching-uncovered probability conjecture for regular linear hypergraphs

Let HH be a dd-regular linear kk-graph, and let MM be a matching chosen uniformly from the set of all matchings of HH. For a vertex vv, write PH(v)\mathcal{P}_H(\overline{v}) for the probability that MM does not cover vv. Kahn's conjecture. For every vV(H)v\in V(H),

PH(v)=(1+od(1))d1/k.\mathcal{P}_H(\overline{v})=(1+o_d(1))d^{-1/k}.

Kahn proposed this as an asymptotic description of the average size of random matchings in regular linear hypergraphs. It was proved for graphs (k=2k=2) by Kahn and Kim, but the paper disproves it for every k3k\geq 3; thus the conjecture is refuted in those cases.

Sources & referencesView supporting material

Primary source

Hyunwoo Lee, “Random matchings in linear hypergraphs”, arXiv:2406.06421 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.