Tuesday, April 27, 2021
C&O Professor Sophie Spirkl's work with Maria Chudnovsky, Alex Scott and Paul Seymour on the Erdos-Hajnal conjecture has been featured in Quantamagazine. The Erdos-Hajnal conjecture, posed in 1989, is that for every graph H there exists a constant c > 0 such that every graph on n vertices not containing H as an induced subgraph has a clique or independent set of size at least nc.
In their paper, the conjecture is resolved for the case where the induced subgraph H is a cycle of length 5.
The Quantamagazine article is available here.