Partitioning edge-colored hypergraphs into few monochromatic tight cycles
Bustamante, S., Corsten, J., Frankl, N., Pokrovskiy, A. & Skokan, J.
(2020).
Partitioning edge-colored hypergraphs into few monochromatic tight cycles.
SIAM Journal on Discrete Mathematics,
34(2), 1460 – 1471.
https://doi.org/10.1137/19M1269786
Confirming a conjecture of Gyárfás, we prove that, for all natural numbers k and r, the vertices of every r-edge-colored complete k-uniform hypergraph can be partitioned into a bounded number (independent of the size of the hypergraph) of monochromatic tight cycles. We further prove that, for all natural numbers p and r, the vertices of every r-edge-colored complete graph can be partitioned into a bounded number of pth powers of cycles, settling a problem of Elekes, Soukup, Soukup, and Szentmiklóssy [Discrete Math., 340 (2017), pp. 2053-2069]. In fact we prove a common generalization of both theorems which further extends these results to all host hypergraphs of bounded independence number.
| Item Type | Article |
|---|---|
| Copyright holders | © 2020 Society for Industrial and Applied Mathematics |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1137/19M1269786 |
| Date Deposited | 06 Apr 2020 |
| Acceptance Date | 06 Apr 2020 |
| URI | https://researchonline.lse.ac.uk/id/eprint/104001 |
Explore Further
- http://www.lse.ac.uk/Mathematics/people/Research-Students/Jan-Corsten (Author)
- http://www.lse.ac.uk/Mathematics/people/Research-Students/Nora-Frankl (Author)
- http://www.lse.ac.uk/Mathematics/people/Jozef-Skokan (Author)
- https://www.scopus.com/pages/publications/85089852407 (Scopus publication)
- https://epubs.siam.org/journal/sjdmec (Official URL)
ORCID: https://orcid.org/0000-0003-3996-7676