Combinatorics and Probability Seminar
Dhruv Mubayi
UIC
Ramsey theory constructions from hypergraph matchings
Abstract: I will show some asymptotically optimal constructions in generalized Ramsey theory using recent results about conflict-free hypergraph matchings. An example: 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 an old (2000) question of Axenovich, Furedi and the speaker. Another example: 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 (1997) question of Erdos and Gyarfas that was recently answered by analyzing a colored modification of the triangle removal process. This is joint work with Felix Joos.
Monday October 10, 2022 at 2:00 PM in 636 SEO