Event Series
Event Type
Seminar
Thursday, May 26, 2022 2:00 PM
Sammy Luo (Stanford)
Given an r-edge-coloring of the complete graph K_n, what is the largest number of edges in a monochromatic connected component?  In this talk we introduce a general framework for studying this natural question and apply it to fully resolve the r = 3 and r = 4 cases, showing a lower bound of (n^2-n)/(2r^2-2r) on the number of edges in both cases, which is tight for sufficiently large n. The asymptotic answer for general r appears to depend on the existence of a finite affine plane of order r-1. The case r = 4 is joint work with David Conlon and Mykhaylo Tyomkyn.