Standort: ---
Exemplare:
---
| Online-Ressource |
Verfasst von: | Joos, Felix [VerfasserIn]  |
| 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 |
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 |
Fractional cycle decompositions in hypergraphs / Joos, Felix [VerfasserIn]; 14 December 2021 (Online-Ressource)
68995943