Colloquium d’Informatique de Sorbonne Université
Maria Chudnovsky, Princeton University

Tuesday, April 25, 2017 18:00
Amphi 15 Sorbonne University - Faculté des Sciences

Induced subgraphs and coloring

Maria Chudnovsky received her B.A. and M.Sc. form 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.

Abstract

What causes a graph to have high chromatic number? One reason is that the graph may contain a large set of pairwise adjacent vertices (called a "clique"), but what can be said if that is not the case? Around 1985 Andras Gayfas made three conjectures about structures that must be present in a graph with large chromatic number all of whose cliques have bounded size. Recently, in joint work with Alex Scott, Paul Seymour and Sophie Sprikl we proved the strongest of these conjectures, that implies the other two. In this talk we will discuss some of the proof ideas, and related problems and theorems.

Master Class

One particularly popular moment associated to the colloquium is the “Master Class” where students have the opportunity to give a short (but well-prepared) presentation of his/her work. Each presentation (10 minutes) is followed by an open discussion with the guest speaker (15 minutes) who gives a detailed feedback. The complete program is provided here.