Ramsey theory constructions from hypergraph matchings

arXiv2208.12563MaRDI QIDQ6408901FDOQ6408901

Felix Joos, Dhruv Mubayi

Publication date: 26 August 2022

Abstract: 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}$ with $2n/3+o(n)$ colors such that each $4$-cycle receives at least three colors on its edges. This answers a question of Axenovich, F"uredi and the second author (On generalized Ramsey theory: the bipartite case, J. Combin. Theory Ser B 79 (2000), 66--86). We also exhibit an edge-coloring of $K_n$ with $5n/6+o(n)$ colors that assigns each copy of $K_4$ at least five colors. This gives an alternative very short solution to an old question of ErdH{o}s and Gy'arf'as that was recently answered by Bennett, Cushman, Dudek, and Pralat by analyzing a colored modification of the triangle removal process.

This page was built for publication: Ramsey theory constructions from hypergraph matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6408901)