Abstract

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

Speaker Intro

Alex Scott is a Professor of Mathematics at the University of Oxford and a fellow of MertonCollege, Oxford. He received his PhD from Cambridge University, and then had positions inCambridge and at UCL before moving to Oxford. He was an invited speaker at the 2022International Congress of Mathematicians. His research lies in extremal and probabilisticcombinatorics, structural graph theory, and related areas of probability and computer science. Moreinformation can be found on his webpage: https://people.maths.ox.ac.uk/scott/