Title: Local and global structure in combinatorics (slides)

Speaker: Alexander Scott (Oxford)

Time: 11:30-12:05 (GMT+0), 2021.08.13

Abstract:

How is the global structure of a graph reflected locally? When does a large graph contain large, highly structured regions? Frank Ramsey showed in 1930 that every graph contains a complete subgraph or independent set of logarithmic size, and random graphs show that this is the right order of magnitude for most graphs. But what if we restrict the local structure by forbidding some induced subgraph? Erdos and Hajnal conjectured in the 1980s that in this case G must have a complete subgraph or independent set of “polynomial” size. We will review recent progress.