ABSTRACT

A graph is a mathematical construct that represents information about connections between pairs of objects. As a result, graphs are widely used as a modeling tool in engineering, social sciences, and other fields. The paper written by Leonhard Euler in 1736 on the Seven Bridges of Konigsberg is often regarded as the starting point of graph theory; and we have come a long way since. This talk will survey a few classical problems in graph theory, and explore their relationship to the fields of research that are active today. In particular, we will discuss Ramsey theory, graph coloring, perfect graphs, as well as some more recent research directions.

About the Speaker:

Maria Chudnovsky received her B.A. and M.Sc. from the Technion, and a PhD from Princeton University in 2003. Currently she is a professor at Princeton. Before returning to Princeton in 2015, she was a Veblen Research Instructor at Princeton University and the IAS, an assistant professor at Princeton, a Clay Mathematics Institute research fellow, and a Liu Family Professor of IEOR at Columbia University. Her research interests are in graph theory and combinatorics. She is an editorial board member of the Journal of Graph Theory, and of Discrete Mathematics. Dr. Chudnovsky was a part of a team of four researchers that proved the strong perfect graph theorem, a 40-year-old conjecture that had been a well-known open problem in both graph theory and combinatorial optimization. For this work, she was awarded the Ostrowski foundation research stipend in 2003, and the prestigious Fulkerson prize in 2009. She was also named one of the "brilliant ten" young scientists by the Popular Science magazine. In 2012, Dr. Chudnovsky received the MacArthur Foundation Fellowship. In 2014, she was an invited speaker at the International Congress of Mathematicians.