University of Cambridge > Talks.cam > Combinatorics Seminar > Graphs with forbidden induced subgraphs

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

Graphs with forbidden induced subgraphs

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Cellular and Molecular Pathology Seminars Combinatorics Seminar Room GS15 at the William Gates Building and on Zoom: https://cl-cam-ac-uk.zoom.us/j/4361570789?pwd=Nkl2T3ZLaTZwRm05bzRTOUUxY3Q4QT09&from=addon

Other talks

A novel hereditary encephalopathy in four related Labrador Retrievers associated with a missense variant in the ALDH5A1 gene’ Am I a Member? Auditing Private Machine Learning Title TBC Morning Tea and Coffee Morning Tea and Coffee Cooperation for Nature
 

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