Hàn–Person–Schacht minimum degree conjecture for perfect matchings in hypergraphs

About 15 years old · traced to

Let HH be an rr-uniform hypergraph on nn vertices, where nn is divisible by rr, and let md(r,n)m_d(r,n) be the smallest integer mm such that every rr-uniform hypergraph HH on nn vertices with minimum dd-degree δd(H)≥m\delta_d(H)\geq m contains a perfect matching. Here 1≤d<r/21\leq d<r/2.

Hàn–Person–Schacht conjecture.

md(r,n)∼max⁡{12,1−(r−1r)r−d}(n−dr−d)m_d(r,n) \sim \max\left\{\frac{1}{2}, 1-\left(\frac{r-1}{r}\right)^{r-d}\right\}{n-d \choose r-d}

This conjecture predicts the asymptotic minimum dd-degree threshold for perfect matchings in the range d<r/2d<r/2, extending the known upper bound of Hàn, Person and Schacht. The surrounding text does not state whether the conjecture has been resolved.

References

Primary source

Imdadullah Khan, “Perfect matching in 3-uniform hypergraphs with large vertex degree”, arXiv:1101.5830 (2012).

Additional references

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

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.