Beijing Institute of Mathematical Sciences and Applications

Benjamin Sudakov

Richard Montgomery

Tuesday, May 13, 2025 5:05 PM - 6:15 PM

Online

Zoom 787 662 9899 (BIMSA)

What conditions on an edge colouring of the complete graph with n vertices imply that it must contain an n-vertex cycle in which no two touching edges have the same colour (i.e., a properly-coloured Hamilton cycle)? In 1976, Bollobás and Erdős conjectured that if every vertex is adjacent to fewer than ⌊n/2⌋ edges of the same colour, then there is always a properly-colored Hamilton cycle. Bollobás and Erdős gave an extremal example showing that the bound ⌊n/2⌋ would be tight, and further extremal examples were later found by Fujita and Magnant, and by Lo who also proved the conjecture asymptotically in 2016.

I will discuss further extremal examples and a proof that this conjecture is true for large n. This is joint work with Aleksa Milojević, Alexey Pokrovskiy, and Benny Sudakov.

Richard Montgomery is an Associate Professor at the Mathematics Institute at the University of Warwick, whose primary research interests are in extremal and probabilistic combinatorics. He obtained his PhD in 2015 from the University of Cambridge under the supervision of Andrew Thomason. Prior to joining Warwick in 2022, he was a faculty member of the University of Birmingham from 2018, and held a Junior Research Fellowship at Trinity College, Cambridge, from 2015-2019. He received a Philip Leverhulme Prize in 2020 and the European Prize in Combinatorics with Alexey Pokrovskiy in 2019, and his research is currently supported by an ERC Starting Grant.