Premium
Fractional cycle decompositions in hypergraphs
Author(s) -
Joos Felix,
Kühn Marcus
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21070
Subject(s) - hypergraph , mathematics , integer (computer science) , combinatorics , set (abstract data type) , enhanced data rates for gsm evolution , markov chain , mixing (physics) , discrete mathematics , computer science , telecommunications , statistics , physics , quantum mechanics , programming language
We prove that for any integerk ≥ 2 $$ k\ge 2 $$ andε > 0 $$ \varepsilon >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+\varepsilon \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.