You are now in the main content area
Seminar: The Erdos-Gyarfas function f(n,4,5) = 5n/6 + o(n) (so Gyarfas was right)
- Date
- October 17, 2023
- Time
- 12:00 PM EDT - 1:00 PM EDT
- Location
- ENG-210 and virtually via zoom
- Open To
- All faculty, staff, students and guests are welcome to attend
- Contact
- Pawel Pralat (pralat@torontomu.ca)
A $(4, 5)$-colouring of $K_n$ is an edge-colouring of $K_n$ where every $4$-clique spans at least five colours. We show that there exist $(4, 5)$-colourings of $K_n$ using $\frac 56 n + o(n)$ colours. This settles a disagreement between Erd\H{o}s and Gy\'arf\'as 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 colouring process uses random triangle removal, a process first introduced by Bollob\'as and Erd\H{o}s, and analyzed by Bohman, Frieze and Lubetzky. \\ (This is a joint work with Bennett, Cushman, and Dudek.)
