Recent progress on the Erdos-Hajnal Conjecture | Research seminar in Discrete Mathematics

Time：2024-04-30 Tue 17:05-18:15

Venue：ZOOM: 787 662 9899 BIMSA

Organizer：Benjamin Sudakov

Speaker：Alexander ScottUniversity of Oxford

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/

DATEApril 29, 2024

Related News

0
Uniform Turn density of hypergraphs | Research seminar in Discrete Mathematics
AbstractIn the early 1980s, Erdos and Ss, initiated the study of the classical Turn problem with auniformity condition: the uniform Turn density of a hypergraph H is the infimum over all d for whichany sufficiently large hypergraph with the property that all its linear-size subhypergraphs havedensity at least d contains H. In particular, they raised the questions of determining the uniformTurn ...
1
On rainbow threshold | Research seminar in Discrete Mathematics
AbstractSolving a problem of Bell, Frieze and Marbach, we extend the recent breakthrough of Frankston,Kahn, Narayanan and Park to the rainbow setting.Speaker IntroJie Han is a professor at the School of Mathematics and Statistics of Beijing Institute ofTechnology. He obtained his Ph.D. degree in 2015 at Georgia State University under thesupervision of Prof. Yi Zhao. He then spent his academic l...