Fractional cycle decompositions in hypergraphs. Issue 3 (14th December 2021) - Joos, Felix; Kühn, Marcus
Abstract: We prove that for any integer k ≥ 2 k2 and ε > 0 ε >0 , there is an integer ℓ 0 ≥ 1 _01 such that any k ‐uniform hypergraph on n vertices with minimum codegree at least ( 1 / 2 + ε ) n (1/2+ε )n has a fractional decomposition into (tight) cycles of length ℓ ( ℓ ‐cycles for short) whenever ℓ ≥ ℓ 0 _0 and n is large in terms of ℓ . This is essentially tight. This immediately yields also approximate integral decompositions for these hypergraphs into ℓ ‐cycles. Moreover, for graphs this even guarantees integral decompositions into ℓ ‐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 ℓ ‐cycles such that every edge is contained in roughly the same number of ℓ ‐cycles from this set by exploiting that certain Markov chains are rapidly mixing.