Back to Search
Start Over
Ramsey theory constructions from hypergraph matchings
- Publication Year :
- 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 Erd\H{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.<br />Comment: 11 pages
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2208.12563
- Document Type :
- Working Paper