Fractional cycle decompositions in hypergraphs. Issue 3 (14th December 2021) - Joos, Felix; Kühn, Marcus
Abstract: We prove that for any integer k ≥ 2 $$ k\ge 2 $$ and ε > 0 $$ ε >0 $$, there is an integer ℓ 0 ≥ 1 $$ {\ell}_0\ge 1 $$ such that any k ‐uniform hypergraph on n vertices with minimum codegree at least ( 1 / 2 + ε ) n $$ \left(1/2+ε \right)n $$ has a fractional decomposition into (tight) cycles of length ℓ $$ \ell $$ ( ℓ $$ \ell $$ ‐cycles for short) whenever ℓ ≥ ℓ 0 $$ \ell \ge {\ell}_0 $$ and n is large in terms of ℓ $$ \ell $$ . This is essentially tight. This immediately yields also approximate integral decompositions for these hypergraphs into ℓ $$ \ell $$ ‐cycles. Moreover, for graphs this even guarantees integral decompositions into ℓ $$ \ell $$ ‐cycles and solves a problem posed by Glock, Kühn, and Osthus. For our proof, we introduce a new method for finding a set of ℓ $$ \ell $$ ‐cycles such that every edge is contained in roughly the same number of ℓ $$ \ell $$ ‐cycles from this set by exploiting that certain Markov chains are rapidly mixing.