Kahn–Kim variance conjecture for random matchings in regular linear hypergraphs

About 2 years old · traced to

Let k≥2k\geq 2 be an integer, let HH be an nn-vertex 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 and Kim'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},

and

Var⁡(∣M∣)=(1+od(1))nk2d1/k.\operatorname{Var}(|M|)=(1+o_d(1))\frac{n}{k^2d^{1/k}}.

The conjecture extends the graph case and predicts both the local uncovered-vertex probability and the variance of the matching size. The first assertion is the earlier Kahn conjecture and is refuted for every k≥3k\geq 3 by this paper; the variance assertion is not resolved by the supplied text.

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.