Ramsey theory constructions from hypergraph matchings
Proceedings of the American Mathematical Society · 20.09.2024 · 152 (11) · 4537-4550
DOI: 10.1090/proc/16413 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the American Mathematical Society, online erschienen am 20.09.2024. Verfasst von Felix Joos und 1 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 12 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft.
Abstract (Originalsprache)
We give asymptotically optimal constructions in generalized Ramsey theory using results about conflict-free hypergraph matchings. For example, we present an edge-coloring of K n , n K_{n,n} with 2 n / 3 + o ( n ) 2n/3 + o(n) colors such that each 4 4 -cycle receives at least three colors on its edges. This answers a question of Axenovich, Füredi and the second author [J. Combin. Theory Ser B 79 (2000), pp. 66–86]. We also exhibit an edge-coloring of K n K_n with 5 n / 6 + o ( n ) 5n/6+o(n) colors that assigns each copy of K 4 K_4 at least five colors. This gives an alternative very short solution to an old question of Erdős and Gyárfás [Combinatorica 17 (1997), pp. 459–467] that was recently answered by Bennett, Cushman, Dudek, and Prałat [J. Combin. Theory Ser. B 169 (2024), pp. 253–297] by analyzing a colored modification of the triangle removal process.
Förderung
- Deutsche Forschungsgemeinschaft
Zitieren
APA
Joos, F., & Mubayi, D. (2024). Ramsey theory constructions from hypergraph matchings. Proceedings of the American Mathematical Society, 152(11), 4537-4550. https://doi.org/10.1090/proc/16413
Vancouver
Joos F, Mubayi D. Ramsey theory constructions from hypergraph matchings. Proceedings of the American Mathematical Society. 2024;152(11):4537-4550. doi:10.1090/proc/16413
BibTeX
@article{Joos2024,
author = {Joos, Felix and Mubayi, Dhruv},
title = {Ramsey theory constructions from hypergraph matchings},
journal = {Proceedings of the American Mathematical Society},
year = {2024},
volume = {152},
number = {11},
pages = {4537--4550},
doi = {10.1090/proc/16413}
}
EUVIMED