| Monday 2 September 2024 | |
| Events for day: Wednesday 11 October 2023 |
| 14:00 - 15:00 Combinatorics and Computing Weekly Seminar The Erd?s-Gyarfas function $f(n,4,5) = frac{5}{6} n + o(n)$ --- so Gyarfas was right. School MATHEMATICS A $(4, 5)$-coloring of $K_n$ is an edge-coloring of $K_n$ where every $4$-clique spans at least five colors. We show that there exist $(4, 5)$-colorings of $K_n$ using $ frac{5}{6} n + o(n)$ colors. This settles a disagreement between Erdos and Gyarfas reported in their 1997 paper. Our construction uses a randomized process which we analyze using the so-called differential equation method to establish dynamic concentration. In particular, our coloring process uses random triangle removal, a process first introduced by Bollobas and Erdos, and analyzed by Bohman, Frieze and Lubetzky. (This is a joint work with Bennett, Cushman, and Dudek. |