- Computer Science Laboratory
  • Colloquium

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.


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.

Electronic access

https://sorbonne-universite.cloud.panopto.eu/Panopto/Pages/Embed.aspx?id=1376bdb9-ba3d-4c04-bf5d-aec80111915e
Maria Chudnovsky

About

Launched in 2012, the Colloquium d’Informatique de Sorbonne Université is a recurring event that invites major figures of the computer science field to give special lectures on the campus of Sorbonne University’s Science and Engineering Faculty. It targets a diverse yet technically-informed audience, and especially computer science researchers from all specialities, PhD students, and computer science students at master level.

The Colloquium’s main event is the invited speaker’s lecture, a 45-minute talk followed by questions and interactions with the audience. Generally, this lecture is associated with a masterclass reserved for PhD students from LIP6 and/or other labs.

As the main driving force behind to the steering committee, LIP6 oversees the Colloquium’s organisation, with occasional support from ISIR.


Steering committee


Contact: Fanny Pascual

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