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

About 2 years old · traced to

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 v∈V(H)v\in V(H),

PH(v‾)=(1+od(1))d−1/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 k≥3k\geq 3; thus the conjecture is refuted in those cases.

References

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.