Noga Alon (Tel Aviv University) will be giving a public talk on September 7, 2017,as part of the program on combinatorics and complexity hosted by the CMSA during AY17-18.  The talk will be at 5:00pm in Askwith Hall, 13 Appian Way, Cambridge, MA.

Title: Graph Coloring: Local and Global

Abstract: Graph Coloring is arguably the most popular subject in Discrete Mathematics, and its combinatorial, algorithmic and computational aspects have been studied intensively. The most basic notion in the area, the chromatic number of a graph, is an inherently global property. This is demonstrated by the hardness of computation or approximation of this invariant as well as by the existence of graphs with arbitrarily high chromatic number and no short cycles. The investigation of these graphs had a profound impact on Graph Theory and Combinatorics. It combines combinatorial, probabilistic, algebraic and topological techniques with number theoretic tools. I will describe the rich history of the subject focusing on some recent results.