Fractional cycle decompositions in hypergraphs. Issue 3 (14th December 2021)

• Record Type: Journal Article
• Authors: Joos, Felix; Kühn, Marcus
• Is Part Of: Random structures & algorithms. Volume 61:Issue 3(2022)
• Page Start: 425
• Page End: 443
• Publication Date: 2021-12-14
• Subjects: cycles -- hypergraph decompositions -- random walk; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21070
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We prove that for any integer k ≥ 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.