Ajouter à votre agenda

Colloquium d'Informatique de L'UPMC Sorbonne Universités
Maria Chudnovsky, Princeton University

Tuesday 25 April 2017 18:00
Amphi 15 Université Pierre et Marie Curie

Induced subgraphs and coloring

Maria Chudnovsky

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.

Other information

Contact: Fanny Pascual

Steering committee

There will be a cocktail at 17:15, In front of Amphi 15.

Amphi 15
Université Pierre et Marie Curie (Jussieu Campus)
4, place Jussieu
Paris 5è (métro Jussieu)
How to reach Université Pierre et Marie Curie (Campus de Jussieu).

Electronic access

Colloquium announcements

In order to be informed of future events via emails, you can subscribe to colloquium announcements.
If you do not want to be informed anymore, you can unsubscribe to colloquium announcements