University of Cambridge > > Isaac Newton Institute Seminar Series > Recent work on the Erdos-Hajnal Conjecture

Recent work on the Erdos-Hajnal Conjecture

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact nobody.

OOEW04 - Structure and Randomness - a celebration of the mathematics of Timothy Gowers

A typical graph contains cliques and independent sets of no more than logarithmic size.  The Erdos-Hajnal Conjecture asserts that if we forbid some induced subgraph H then we can do much better: the conjecture claims that there is some c=c(H)>0 such that every H-free graph G contains a clique or independent set of size at least |G|^c.  The conjecture looks far out of reach, and is only known for a small family of graphs.  We will discuss some recent progress. Joint work with Tung Nguyen and Paul Seymour.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity