List Coloring

18 December 2019
4:30 PM
Mendel Museum´s Augustinian Abbey Refectory at Mendel Square

Noga Alon is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers. He is also a Baumritter Professor Emeritus of Mathematics and Computer Science at Tel Aviv University.

He received his Ph. D. in Mathematics at the Hebrew University of Jerusalem in 1983 and had visiting positions in various research institutes including MIT, the Institute for Advanced Study in Princeton, IBM Almaden Research Center, Bell Laboratories, Bellcore and Microsoft Research (Redmond and Israel).

His research interests are mainly in Combinatorics, Graph Theory and their applications in Theoretical Computer Science. His main contributions include the study of expander graphs and their applications, the investigation of derandomization techniques, the foundation of streaming algorithms, the development and applications of algebraic and probabilistic methods in Discrete Mathematics and the study of problems in Information Theory, Combinatorial Geometry and Combinatorial Number Theory.

Noga Alon has received a number of awards, including the Erdős Prize in 1989, the Pólya Prize in 2000, the Landau Prize in 2005, the Gödel Prize in 2005, the Israel Prize, for mathematics in 2008, and the EMET Prize in 2011. He has been a member of the Israel Academy of Sciences and Humanities since 1997, he was elected as a fellow of the American Mathematical Society in 2015 and a Fellow of the Association for Computing Machinery in 2017.

Abstract

The list chromatic number of a graph G is the minimum k so that for every assignment of a list of k colors to any vertex of G there is a vertex coloring assigning to each vertex a color from its list so that adjacent vertices get distinct colors. This notion was introduced by Vizing and by Erdős, Rubin and Taylor in the late 70s and its study combines combinatorial, probabilistic and algebraic techniques.
Its natural extension to hypergraphs is closely related to questions in Euclidean Ramsey Theory.

I will discuss several old and new problems and results in the area focusing on a recent work with Briceno, Chandgotia, Magazinov and Spinka motivated by questions in statistical physics regarding vertex colorings of the d-dimensional lattice.