z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here