Fractional cycle decompositions in hypergraphs

• Verfasst von: Joos, Felix [VerfasserIn]
• Verfasst von: Kühn, Marcus [VerfasserIn]
• Titel: Fractional cycle decompositions in hypergraphs
• Verf.angabe: Felix Joos, Marcus Kühn
• E-Jahr: 2022
• Jahr: 14 December 2021
• Umfang: 19 S.
• Fussnoten: Gesehen am 12.12.2022
• Titel Quelle: Enthalten in: Random structures & algorithms
• Ort Quelle: New York, NY [u.a.] : Wiley, 1990
• Jahr Quelle: 2022
• Band/Heft Quelle: 61(2022), 3, Seite 425-443
• ISSN Quelle: 1098-2418
• DOI: doi:10.1002/rsa.21070
• Datenträger: Online-Ressource
• Sprache: eng
• Sach-SW: cycles
• Sach-SW: hypergraph decompositions
• Sach-SW: random walk
• K10plus-PPN: 1826817042
• K10plus-PPN:
  Universitätsbibliothek
• Lokale URL UB: Zum Volltext

Abstract

We prove that for any integer and , there is an integer such that any k-uniform hypergraph on n vertices with minimum codegree at least has a fractional decomposition into (tight) cycles of length (-cycles for short) whenever 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.