University of Cambridge > > Combinatorics Seminar > Graphs with forbidden induced subgraphs

Graphs with forbidden induced subgraphs

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

  • UserAlex Scott (University of Oxford)
  • ClockThursday 06 February 2020, 14:30-15:30
  • HouseMR12.

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

Ramsey’s Theorem tells us that every graph on n vertices contains a complete subgraph or independent set of size about log n. Considering random graphs shows that this is all we can expect: for most graphs, the largest complete subgraph or independent set has size O(log n). But what if we consider graphs G that do not contain some specific induced subgraph H? Erdos and Hajnal conjectured in the 1980s that in this case G must have a complete subgraph or independent set of size at least |G|^c, for some c=c(H). The Erdos-Hajnal conjecture remains open, but we will discuss some recent progress and related results. This talk includes joint work with Maria Chudnovsky, Jacob Fox, Paul Seymour and Sophie Spirkl.

This talk is part of the Combinatorics Seminar 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