Graphs and Matroids Seminar- Richard Lang

Thursday, November 22, 2018 3:30 pm - 3:30 pm EST (GMT -05:00)

Title: The upper density of monochromatic infinite paths

Speaker: Richard Lang
Affiliation: University of Waterloo
Room: MC 5417

Abstract: Given a complete graph $K_n$, whose edges are coloured in red and blue, what is the longest monochromatic path one can find? Gerencs\'er and Gy\'arf\'as proved that there is always a red or blue path on $2n/3$ vertices, which is best possible. It is natural to consider density analogues of this problem for infinite graphs. The study thereof was initiated by Erd\H os and Galvin in the early nineties. They provided some upper and lower bounds, but left a gap between them. In this talk I will present some of the recent progress on resolving this problem.

Join work with Jan Corsten, Louis DeBiasio and Ander Lamaison.