Self-Complementarity and the Erdos-Hajnal Conjecture

Abstract

In this thesis, we take a closer look at the Erdos-Hajnal Conjecture. A Graph $H$ is said to have the Erdos-Hajnal (EH) property if, for some constant $\gamma(H) > 0$, every sufficiently large $H$-free graph $G$ has a homogeneous set of size at least $|G|^{\gamma(H)}$. The Erdos-Hajnal Conjecture claims that every finite graph has the EH-property. It is known that the substitution operation preserves the EH-property, so it suffices to focus our attention only on substitution-prime graphs. We begin by studying the techniques used to prove the EH-property for the few known cases, namely $P_4$, $C_5$ and the Bull graph.

We extend some of these techniques, to show that in order to prove the EH-property for the smallest open case $P_5$, it suffices to look for large homogeneous sets in dense $P_5$-free graphs. We then ask whether these large homogeneous sets can be found in a dense $P_5$-free graph $G$ on making it $P_4$-free, by removing at most $c|G|$ number of vertices. We answer this question in the negative using a construction involving the substitution operation.

Finally, we note the role of 'Self-complementarity' in most of the known proofs of the EH-property and ask whether it is possible to further reduce the conjecture to proving the EH-property for a class of substitution prime self-complementary graphs. We show that this is possible by proving the following results about the self-complementary Paley graphs: Every graph is an induced subgraph of some primitive Paley graph, and all Paley graphs are substitution prime. Thus, we further reduce the Erdos-Hajnal Conjecture, by showing that it suffices to prove the EH-property for primitive Paley graphs. We also prove some simple upper bounds on $\gamma(H)$ for substitution prime graphs $H$.