Final Oral Public Examination

 

This thesis develops ideas and techniques from extremal, probabilistic, and structural graph theory to investigate the edge distribution of graphs with forbidden induced subgraphs. The thesis’ main focus is the Erdo˝s–Hajnal conjecture from 1977 that says for every graph H there exists c > 0 such that every n-vertex graph with no induced copy of H has a clique or stable set of size at least nc. Partial results on the conjecture presented (all joint with Alex Scott and Paul Seymour) include: a log log improvement over the general bound 2c√log n of Erdo˝s–Hajnal from 1977 (also joint with Matija Buci´c); a proof of the conjecture when H is the five-vertex path, which was the last open case of the problem of proving the conjecture for every H with five vertices (first posed by Gy´arfa´s in 1997); a proof of the conjecture in the setting of graphs of bounded VC-dimension, which was posed independently by Chernikov, Starchenko, and Thomas and by Fox, Pach, and Suk; a proof of the conjecture for infinitely many prime graphs H, which was asked by Chudnovsky in 2014; a proof of the bound 2(log n)1−o(1) when H is an arbitrary path; and a proof of the conjecture for excluding a hole and an antihole, and for excluding an arbitrary induced (≥ 4)-subdivision of H and its complement.

 

The ideas developed in the thesis are also adapted to give applications in the area of χ-boundedness which studies the induced subgraphs of graphs with chromatic number much larger than clique number. These include an approximation of the Gya´rf´as–Sumner conjecture (joint with Alex Scott and Paul Seymour); a proof that graphs with bounded clique number and no induced subdivision of any given graph have polylogarithmic chromatic number (joint with Alex Scott and Paul Seymour), which extends a result of Fox and Pach on the chromatic number of string graphs; several new instances for which the polynomial Gy´arfa´s–Sumner conjecture holds; and a log log improvement over the χ-binding function ωlog ω of graphs with no induced five-vertex path proved by Scott, Seymour, and Spirkl.