2022/08/26 by Felix Joos, Joos, Felix, Dhruv Mubayi +1 · 2 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Topology and Set Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2208.12563
We give asymptotically optimal constructions in generalized Ramsey theory using results about conflict-free hypergraph matchings. For example, we present an edge-coloring of Kn,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üredi 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 Kn with 5n/6+o(n) colors that assigns each copy of K4 at least five colors. This gives an alternative very short solution to an old question of Erdős and Gyárfás that was recently answered by Bennett, Cushman, Dudek, and Pralat by analyzing a colored modification of the triangle removal process.