Back to Search
Start Over
Decomposing hypergraphs into cycle factors.
- Source :
-
Journal of Combinatorial Theory - Series B . Jan2023:Part 2, Vol. 158, p136-175. 40p. - Publication Year :
- 2023
-
Abstract
- A famous result by Rödl, Ruciński, and Szemerédi guarantees a (tight) Hamilton cycle in k -uniform hypergraphs H on n vertices with minimum (k − 1) -degree δ k − 1 (H) ⩾ (1 / 2 + o (1)) n , thereby extending Dirac's result from graphs to hypergraphs. For graphs, much more is known; each graph on n vertices with δ (G) ⩾ (1 / 2 + o (1)) n contains (1 − o (1)) r edge-disjoint Hamilton cycles where r is the largest integer such that G contains a spanning 2 r -regular subgraph, which is clearly asymptotically optimal. This was proved by Ferber, Krivelevich, and Sudakov answering a question raised by Kühn, Lapinskas, and Osthus. We extend this result to hypergraphs; every k -uniform hypergraph H on n vertices with δ k − 1 (H) ⩾ (1 / 2 + o (1)) n contains (1 − o (1)) r edge-disjoint (tight) Hamilton cycles where r is the largest integer such that H contains a spanning subgraph with each vertex belonging to kr edges. In particular, this yields an asymptotic solution to a question of Glock, Kühn, and Osthus. In fact, our main result applies to approximately vertex-regular k -uniform hypergraphs with a weak quasirandom property and provides approximate decompositions into cycle factors without too short cycles. [ABSTRACT FROM AUTHOR]
- Subjects :
- *HYPERGRAPHS
*INTEGERS
Subjects
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 158
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 160368785
- Full Text :
- https://doi.org/10.1016/j.jctb.2022.09.004