On a Model-Theoretic Approach to a Special Case of the Erdős-Hajnal Conjecture

The Erdős-Hajnal Conjecture is a famous open problem in extremal graph combinatorics relating the omission of a subgraph to the existence of a clique or an anti-clique of a given size in a graph. If true, this conjecture improves the well-known Ramsey Theorem. Chernikov and Starchenko proved a special case of this conjecture for certain families of graphs connected to the notion of stability in model theory. The goal of this paper is to provide the full details of their proofs and the necessary background to understand these details so that a first-year student in model theory can understand them. The main theorem in this paper is model-theoretic; its ingredients are some basic tools in local stability theory, such as local 2-rank, and the pseudo-finite dimension. This material is developed in the first few chapters, and then the proof of the main theorem is given in depth. We conclude by explaining how the graph-theoretic statement of the special case of Erdős-Hajnal follows from the aforementioned model theory.