Erdős and Hajnal showed that graphs satisfying any fixed hereditary property contain much larger cliques or independent sets than what is guaranteed by (the quantitative form of) Ramsey's theorem. We start with a whirlwind tour of the history of this observation, and then we present some new results for ordered graphs, that is, for graphs with a linear ordering on their vertex sets. In particular, we prove that for every positive integer $k$, there exists a constant $c=c(k)>0$ such that any ordered graph $G$ on $n$ vertices with the property that neither $G$ nor its complement contains an induced monotone path of size $k$, has either a clique or an independent set of size at least $n^c$. This strengthens a theorem of Bousquet, Lagoutte, and Thomassé, who proved the analogous statement for unordered graphs. Joint work with István Tomon.


Recording:https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=daebf834-6e24-4c88-bd0d-ac8600e77b38