Almost partitioning every 2-edge-coloured complete k-graph into k monochromatic tight cycles

EUROCOMB’23

Abstract
A $k$-uniform tight cycle is a $k$-graph with a cyclic order of its vertices such that every $k$ consecutive vertices from an edge. We show that for $k\geq 3$, every red-blue edge-coloured complete $k$-graph on $n$ vertices contains $k$ vertex-disjoint monochromatic tight cycles that together cover $n – o(n)$ vertices.

Pages:
725–730
References

P. Allen. Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles. Combin. Probab. Comput., 17(4):471-486, 2008.
https://doi.org/10.1017/S0963548308009164

P. Allen, J. Böttcher, O. Cooley, and R. Mycroft. Tight cycles and regular slices in dense hypergraphs. J. Combin. Theory Ser. A, 149:30-100, 2017.
https://doi.org/10.1016/j.jcta.2017.01.003

S. Bessy and S. Thomassé. Partitioning a graph into a cycle and an anticycle, a proof of lehel's conjecture. J. Combin. Theory Ser. B, 100(2):176-180, 2010.
https://doi.org/10.1016/j.jctb.2009.07.001

S. Bustamante, J. Corsten, N. Frankl, A. Pokrovskiy, and J. Skokan. Partitioning edge-colored hypergraphs into few monochromatic tight cycles. SIAM J. Discrete Math., 34(2):1460-1471, 2020.
https://doi.org/10.1137/19M1269786

S. Bustamante, H. Hàn, and M. Stein. Almost partitioning 2-colored complete 3-uniform hypergraphs into two monochromatic tight or loose cycles. J. Graph Theory, 91(1):5-15, 2019.
https://doi.org/10.1002/jgt.22417

S. Bustamante and M. Stein. Partitioning 2-coloured complete k-uniform hypergraphs into monochromatic ℓ-cycles. European J. Combin., 71:213-221, 2018.
https://doi.org/10.1016/j.ejc.2018.04.005

D. Gale. The game of Hex and the Brouwer fixed-point theorem. Amer. Math. Monthly, 86(10):818-827, 1979.
https://doi.org/10.1080/00029890.1979.11994922

F. Garbe, R. Mycroft, R. Lang, A. Lo, and N. Sanhueza-Matamala. Partitioning 2-coloured complete 3-uniform hypergraphs into two monochromatic tight cycles. In preparation.

L. Gerencsér and A. Gyárfás. On Ramsey-type problems. Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 10:167-170, 1967.

A. Gyárfás. Vertex coverings by monochromatic paths and cycles. J. Graph Theory, 7(1):131-135, 1983.
https://doi.org/10.1002/jgt.3190070116

A. Gyárfás. Vertex covers by monochromatic pieces - a survey of results and problems. Discrete Math., 339(7):1970-1977, 2016.
https://doi.org/10.1016/j.disc.2015.07.007

A. Gyárfás and G. N. Sárközy. Monochromatic path and cycle partitions in hypergraphs. Electron. J. Combin., 20(1):18, 2013.
https://doi.org/10.37236/2631

A. Lo and V. Pfenninger. Towards Lehel's conjecture for 4-uniform tight cycles. Electron. J. Combin., 30(1):P1.13, 2023.
https://doi.org/10.37236/10604

T. Łuczak. R(Cn,Cn,Cn) ≤ (4 + o(1))n. J. Combin. Theory Ser. B, 75(2):174-187, 1999.
https://doi.org/10.1006/jctb.1998.1874

T. Łuczak, V. Rödl, and E. Szemerédi. Partitioning two-coloured complete graphs into two monochromatic cycles. Combin. Probab. Comput., 7(4):423-436, 1998.
https://doi.org/10.1017/S0963548398003599

G. N. Sárközy. Improved monochromatic loose cycle partitions in hypergraphs. Discrete Math., 334:52-62, 2014.
https://doi.org/10.1016/j.disc.2014.06.025

M. Simonovits and E. Szemerédi. Embedding graphs into larger graphs: results, methods, and problems. In Building bridges II-mathematics of László Lovász, volume 28 of Bolyai Soc. Math. Stud., pages 445-592. Springer, Berlin, [2019] ©2019.
https://doi.org/10.1007/978-3-662-59204-5_14

Metrics

0

Views

0

PDF views