Fractional cycle decompositions in hypergraphs
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 y...
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
14 December 2021
|
| In: |
Random structures & algorithms
Year: 2022, Jahrgang: 61, Heft: 3, Pages: 425-443 |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.21070 |
| Online-Zugang: | Verlag, kostenfrei, Volltext: https://doi.org/10.1002/rsa.21070 Verlag, kostenfrei, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.21070 
|
| Verfasserangaben: | Felix Joos, Marcus Kühn |
| Zusammenfassung: | 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. |
|---|---|
| Beschreibung: | Gesehen am 12.12.2022 |
| Beschreibung: | Online Resource |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.21070 |