The Alon–Frankl–Huang–Rödl–Ruciński–Sudakov conjecture on fractional matching thresholds

At least 10 years old · documented by

For k,ℓ∈Nk,\ell\in\mathbb N with ℓ≤k−1\ell\leq k-1, let ck,ℓ∗c^*_{k,\ell} be the smallest number cc such that every kk-graph HH on nn vertices with

δℓ(H)≥(c+o(1))(n−ℓk−ℓ)\delta_\ell(H)\geq (c+o(1))\binom{n-\ell}{k-\ell}

contains a perfect fractional matching, where a perfect fractional matching is a fractional matching of size n/kn/k. Alon–Frankl–Huang–Rödl–Ruciński–Sudakov conjecture. For all ℓ,k∈N\ell,k\in\mathbb N,

ck,ℓ∗=1−(1−1/k)k−ℓ.c^*_{k,\ell}=1-(1-1/k)^{k-\ell}.

This conjecture identifies the asymptotic minimum ℓ\ell-degree threshold for forcing a perfect fractional matching. The source states that it remains open and is particularly challenging for small values of ℓ\ell.

References

Primary source

Luyining Gan and Jie Han, “On the Keevash-Knox-Mycroft Conjecture”, arXiv:2202.04246 (2026).

Additional references

2 papers in this index state this conjecture (2015–2022). The statement above is taken from the most recent of them; the others are arXiv:1508.06170.

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.