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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
14 December 2021
|
| In: |
Random structures & algorithms
Year: 2022, Volume: 61, Issue: 3, Pages: 425-443 |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.21070 |
| Online Access: | Verlag, kostenfrei, Volltext: https://doi.org/10.1002/rsa.21070 Verlag, kostenfrei, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.21070 
|
| Author Notes: | Felix Joos, Marcus Kühn |
| Summary: | 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. |
|---|---|
| Item Description: | Gesehen am 12.12.2022 |
| Physical Description: | Online Resource |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.21070 |