Fractional cycle decompositions in hypergraphs

Abstract

We prove that for any integer $k\ge 2$ and $\epsilon >0$, there is an integer ${\ell }_0\ge 1$ such that any $k$-uniform hypergraph on $n$ vertices with minimum codegree at least $(1/2+\epsilon )n$ has a fractional decomposition into tight cycles of length $\ell$ ($\ell$-cycles for short) whenever $\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.

14 pages