The smaller matching threshold conjecture

Let mds(k,n)m_d^s(k,n) be the smallest integer mm such that every kk-graph HH on nn vertices with minimum dd-degree at least mm contains a matching of size ss. Let Hs0(n,k)H_s^0(n,k) be the kk-graph whose vertex set is partitioned into ABA\cup B, with A=s1|A|=s-1, and whose edges are all kk-sets meeting AA.

Smaller matching threshold conjecture. Given 1dk21\leq d\leq k-2, there exist n0n_0 and CC such that

mds(k,n)=(ndkd)(nsd+1kd)+1m_d^s(k,n)=\binom{n-d}{k-d}-\binom{n-s-d+1}{k-d}+1

for all nn0n\geq n_0 and all sn/kCs\leq n/k-C.

The displayed value is exactly the lower bound supplied by the space barrier Hs0(n,k)H_s^0(n,k). The claim was known in some cases and an asymptotic version had been proved in a substantial range, but the stated general result remained open in the survey.

Sources & referencesView supporting material

Primary source

Yi Zhao, “Recent advances on Dirac-type problems for hypergraphs”, arXiv:1508.06170 (2015).

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.