General minimum codegree conjecture for perfect matchings in uniform hypergraphs

At least 10 years old · documented by

Suppose that k,ℓ∈Nk,\ell\in\mathbb N with ℓ≤k−1\ell\leq k-1. For a kk-uniform hypergraph HH, let δℓ(H)\delta_\ell(H) denote its minimum ℓ\ell-degree, and let mℓ(k,n)m_\ell(k,n) be the smallest integer mm such that every kk-uniform hypergraph on nn vertices with δℓ(H)≥m\delta_\ell(H)\geq m contains a perfect matching. Let δ(n,k,ℓ)\delta(n,k,\ell) be the maximum minimum ℓ\ell-degree among the divisibility-barrier hypergraphs described in the source. Then the general minimum codegree conjecture asserts that, for all sufficiently large n∈kNn\in k\mathbb N,

mℓ(k,n)=max⁡{δ(n,k,ℓ), (n−ℓk−ℓ)−((1−1/k)n−ℓ+1k−ℓ)}+1.m_\ell(k,n)=\max\left\{\delta(n,k,\ell),\ \binom{n-\ell}{k-\ell}-\binom{(1-1/k)n-\ell+1}{k-\ell}\right\}+1.

This conjecture combines the divisibility and space-barrier constructions, each of which gives a lower bound for the minimum ℓ\ell-degree forcing a perfect matching. It is known in several cases, including ℓ≥k/2\ell\geq k/2 and various small pairs (k,ℓ)(k,\ell), but remains open in general.

References

Primary source

Andrew Treglown and Yi Zhao, “A note on perfect matchings in uniform hypergraphs”, arXiv:1503.03357 (2016).

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.