Navigation überspringen
Universitätsbibliothek Heidelberg
Standort: ---
Exemplare: ---
heiBIB
 Online-Ressource
Verfasst von:Joos, Felix [VerfasserIn]   i
 Kühn, Marcus [VerfasserIn]   i
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
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.
DOI:doi:10.1002/rsa.21070
URL:kostenfrei: Volltext: https://doi.org/10.1002/rsa.21070
 kostenfrei: Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.21070
 DOI: https://doi.org/10.1002/rsa.21070
Datenträger:Online-Ressource
Sprache:eng
Sach-SW:cycles
 hypergraph decompositions
 random walk
K10plus-PPN:1826817042
Verknüpfungen:→ Zeitschrift
 
 
Lokale URL UB: Zum Volltext

Permanenter Link auf diesen Titel (bookmarkfähig):  https://katalog.ub.uni-heidelberg.de/titel/68995943   QR-Code
zum Seitenanfang