Large matching minimum degree conjecture for uniform hypergraphs

About 13 years old · traced to

Let GG be a kk-uniform hypergraph on nn vertices. For integers nn, dd, kk, and ss with 1≤d≤k−11\leq d\leq k-1 and 0≤s≤(1−ε)n/k0\leq s\leq (1-\varepsilon)n/k, let mds(k,n)m_d^s(k,n) denote the minimum integer mm such that every kk-uniform hypergraph on nn vertices with minimum dd-degree at least mm has a matching of size ss. Large matching degree conjecture. For every ε>0\varepsilon>0,

mds(k,n)=(1−(1−sn)k−d+o(1))(n−dk−d).m_d^{s}(k,n)= \left(1-\left(1-\frac{s}{n}\right)^{k-d}+o(1)\right)\binom{n-d}{k-d}.

This extends the perfect-matching threshold problem to smaller matchings. The paper presents it as a proposed generalization; the supplied text gives no resolution of the conjecture, although it records exact results in some small-uniformity cases.

References

Primary source

Daniela Kühn, Deryk Osthus and Timothy Townsend, “Fractional and integer matchings in uniform hypergraphs”, arXiv:1304.6901 (2013).

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.