Monday, January 1, 2018

12:15–13:10

Schreiber 006

12:15–13:10

Schreiber 006

:: MINT Distinguished Lecture ::

Benny Sudakov

ETH Zürich

Rainbow structures, Latin squares & graph decompositions

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares. Since then rainbow structures were the focus of extensive research and found applications in design theory and graph decompositions. In this talk we discuss how probabilistic reasoning can be used to attack several old problems in this area. In particular we show that well known conjectures of Ryser, Hahn, Ringel, and Graham–Sloane hold asymptotically.

Based on joint works with Alon, Montgomery, and Pokrovskiy.