WiM Winter Colloquium 2021

Students, postdocs, faculty and research staff are all invited to the 2021 WiM Winter Colloquium. Professor Maria Chudnovsky from Princeton University will be holding a 30 minute talk followed by a Q&A session.

Register today!

---

Title: Recent progress on the Erdos-Hajnal Conjecture

Abstract:

The Erdos-Hajnal conjecture states that for every graph H there is a constant epsilon(H) such that every n-vertex graph with no induced subgraph isomorphic to H has a clique or a stable set of size n^{epsilon}. This conjecture has only been verified for a few graphs  H, and in particular until recently it remained open for the case when H is a cycle of length 5. This special case received a considerable amount of attention. In this talk we will survey some known results, and discuss the recent proof for the case of a cycle of length 5.

This is joint work with Alex Scott, Paul Seymour and Sophie Spirkl.

---

Speaker:

Prof. Maria Chudnovsky is a mathematician working on structural graph theory. She received her Ph.D. in 2003 from Princeton University. After postdoctoral research at the Clay Mathematics Institute, she became an assistant professor at Princeton University in 2005, and moved to Columbia University in 2006. By 2014, she was the Liu Family Professor of Industrial Engineering and Operations Research at Columbia. She returned to Princeton as a professor of mathematics in 2015. She is also a 2012 MacArthur Fellow.

Her contributions to graph theory include the proof of the strong perfect graph theorem (with Neil Robertson, Paul Seymour, and Robin Thomas) characterizing perfect graphs as being exactly the graphs with no odd induced cycles of length at least 5 or their complements. Other research contributions of Chudnovsky include co-authorship of the first polynomial-time algorithm for recognizing perfect graphs (time bounded by a polynomial of degree 9), and of a structural characterization of the claw-free graphs.