18/12 Seminar Series: List Coloring Lecture from Noga Alon
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.
When?
18 December 2019, 4:30 PM
Where?
Mendel Museum's Augustinian Abbey Refectory at Mendel Square