Minimum-degree Baranyai factorization conjecture

At least 5 years old · documented by

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 k∣nk\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.

References

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.