Graphs with forbidden induced subgraphs

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

• Alex Scott (University of Oxford)
• Thursday 06 February 2020, 14:30-15:30
• MR12.

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.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.