Minimum-degree Baranyai factorization conjecture

Fix kk and ε>0\varepsilon>0. Let GG be an nn-vertex kk-uniform hypergraph, and let δ(G)\delta(G) denote its minimum vertex degree. A perfect matching is a set of pairwise disjoint edges covering all vertices; a decomposition into perfect matchings is a 11-factorization.

Minimum-degree Baranyai conjecture. For all sufficiently large nn, an nn-vertex kk-graph GG with

δ(G)(1/2+ε)n\delta(G)\ge (1/2+\varepsilon)n

can be decomposed into perfect matchings if and only if knk\mid n and GG is vertex-regular.

This proposes a dense minimum-degree extension of Baranyai's theorem. The divisibility and regularity conditions are necessary, and the source presents sufficiency as open.

Sources & referencesView supporting material

Primary source

Stefan Glock, Daniela Kühn and Deryk Osthus, “Extremal aspects of graph and hypergraph decomposition problems”, arXiv:2008.00926 (2021).

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.