Pure Pairs, Forests and Path–Antipath Classes

By [L1], if $G$ is disconnected then the first alternative of the Statement already holds. Assume instead that $G$ is connected.

Suppose for contradiction that $G$ is also anticonnected. Then [L2] makes $\bar{G}$ connected. Choose a vertex $v\in V(G)$. Because $G$ is connected and nontrivial, [F1] gives a neighbour $x$ of $v$. Because $\bar{G}$ is connected, [F1] also gives a vertex $y$ nonadjacent to $v$. Among all pairs $(a,b)$ with $va\in E(G)$ and $vb\mathrm{\notin }E(G)$, choose one for which the distance from $a$ to $b$ in $G$ is minimal. Let $a=u_0,u_1,\dots ,u_m=b$ be a shortest $a$-$b$ path in $G$.

Since $a$ and $b$ are nonadjacent, one has $m\ge 2$. A shortest path is induced, so $u_0{u}_2\mathrm{\notin }E(G)$ and no nonconsecutive pair among $u_0,u_1,\dots ,u_m$ is adjacent. If some $u_i$ with $1\le i<m$ were adjacent to $v$, then $(u_i,b)$ would be another neighbour/nonneighbour pair for $v$ whose distance is $m-i<m$, contradicting the choice in step 1.2. Hence $v{u}_1,v{u}_2\mathrm{\notin }E(G)$.

The four vertices $v,u_0,u_1,u_2$ therefore induce a path: the edges are $v{u}_0$, $u_0{u}_1$, and $u_1{u}_2$, while the nonedges are $v{u}_1$, $v{u}_2$, and $u_0{u}_2$. This is an induced copy of $P_4$, contradicting [L3].

So a nontrivial $P_4$-free graph cannot be both connected and anticonnected. Since step 1.1 reduced to the connected case, [L2] shows that whenever $G$ is connected, $\bar{G}$ must be disconnected.

We prove by induction on $n$ the stronger statement $\alpha (G)\omega (G)\ge n$. If $n\le 1$, then $\alpha (G)=1$ when $n=1$ and $\alpha (G)=\omega (G)=0$ when $n=0$, so the inequality is immediate.

Assume $n\ge 2$. By [L2], either $G$ is disconnected or $\bar{G}$ is disconnected.

Suppose first that $G$ is disconnected. By [L3], choose a connected component $C$ of $G$ and let $D:=V(G)\setminus C$; then $C$ and $D$ are nonempty, $G[C]$ and $G[D]$ are induced subgraphs of $G$, and [L4] makes $C$ anticomplete to $D$. By [L1] both induced subgraphs are $P_4$-free, so the induction hypothesis gives $\alpha (G[C])\omega (G[C])\ge \mathrm{\mid }C\mathrm{\mid }$ and $\alpha (G[D])\omega (G[D])\ge \mathrm{\mid }D\mathrm{\mid }$. A stable set in $G[C]$ together with a stable set in $G[D]$ is still stable in $G$, while every clique of $G$ lies in one side. Hence $\alpha (G)\ge \alpha (G[C])+\alpha (G[D])$ and $\omega (G)\ge \max \{\omega (G[C]),\omega (G[D])\}$, so $\alpha (G)\omega (G)\ge \alpha (G[C])\omega (G[C])+\alpha (G[D])\omega (G[D])\ge \mathrm{\mid }C\mathrm{\mid }+\mathrm{\mid }D\mathrm{\mid }=n$.

Suppose instead that $\bar{G}$ is disconnected. By [L3], choose an anticomponent $C$ of $G$ and let $D:=V(G)\setminus C$; then $C$ and $D$ are nonempty, the induced subgraphs $G[C]$ and $G[D]$ are $P_4$-free by [L1], and [L4] makes $C$ complete to $D$. The induction hypothesis again yields $\alpha (G[C])\omega (G[C])\ge \mathrm{\mid }C\mathrm{\mid }$ and $\alpha (G[D])\omega (G[D])\ge \mathrm{\mid }D\mathrm{\mid }$. Now a clique in $G[C]$ together with a clique in $G[D]$ is a clique in $G$, while every stable set of $G$ lies in one side. Thus $\omega (G)\ge \omega (G[C])+\omega (G[D])$ and $\alpha (G)\ge \max \{\alpha (G[C]),\alpha (G[D])\}$, and again $\alpha (G)\omega (G)\ge \mathrm{\mid }C\mathrm{\mid }+\mathrm{\mid }D\mathrm{\mid }=n$.

Steps 3.1 and 3.2 prove $\alpha (G)\omega (G)\ge n$. Since $\max \{\alpha (G),\omega (G){\}}^2\ge \alpha (G)\omega (G)$, one obtains $\max \{\alpha (G),\omega (G)\}\ge \sqrt{n}$. By [L5], this says that $G$ has a clique or a stable set of size at least $\sqrt{n}$.

If every nonempty graph in $\mathcal{C}$ has one vertex, then $1$ is already an Erdős–Hajnal constant, so there is nothing to prove. We therefore assume that $\mathcal{C}$ contains some graph with at least two vertices. Let $\eta >0$ be the strong Erdős–Hajnal constant from [L1]. Applying [L1] to one nontrivial graph in $\mathcal{C}$ gives disjoint sets $A$ and $B$ with $\mathrm{\mid }A\mathrm{\mid },\mathrm{\mid }B\mathrm{\mid }\ge \eta \mathrm{\mid }V(G)\mathrm{\mid }$, hence $2\eta \le 1$. Choose $c>0$ so that $2{\eta }^c=1$.

We claim that every nonempty graph $G\in \mathcal{C}$ induces a $P_4$-free subgraph on at least $\mathrm{\mid }V(G){\mathrm{\mid }}^c$ vertices. We prove this by induction on $\mathrm{\mid }V(G)\mathrm{\mid }$, and the case $\mathrm{\mid }V(G)\mathrm{\mid }=1$ is immediate.

Let $G\in \mathcal{C}$ with $n:=\mathrm{\mid }V(G)\mathrm{\mid }\ge 2$, and assume the claim for smaller orders. By [L1], choose disjoint sets $A,B\subseteq V(G)$ with $\mathrm{\mid }A\mathrm{\mid },\mathrm{\mid }B\mathrm{\mid }\ge \eta n$ and $(A,B)$ pure. By [L2], the induced subgraphs $G[A]$ and $G[B]$ both lie in $\mathcal{C}$, so the induction hypothesis gives induced $P_4$-free subgraphs $H_A\subseteq G[A]$ and $H_B\subseteq G[B]$ with $\mathrm{\mid }V(H_A)\mathrm{\mid }\ge \mathrm{\mid }A{\mathrm{\mid }}^c$ and $\mathrm{\mid }V(H_B)\mathrm{\mid }\ge \mathrm{\mid }B{\mathrm{\mid }}^c$.

Let $H:=G[V(H_A)\cup V(H_B)]$. The pair $(V(H_A),V(H_B))$ is still pure because it sits inside the pure pair $(A,B)$. No induced $P_4$ can lie entirely in one side, since $H_A$ and $H_B$ are each $P_4$-free. A $1+3$ split is impossible because the lone vertex would be complete or anticomplete to the three opposite vertices, while a vertex of $P_4$ is neither complete nor anticomplete to the other three. A $2+2$ split is impossible as well: a complete cross-pair gives four cross edges, and an anticomplete cross-pair gives none, whereas $P_4$ has exactly three edges and is connected. Hence $H$ is $P_4$-free.

By [L5], $\mathrm{\mid }V(H)\mathrm{\mid }=\mathrm{\mid }V(H_A)\mathrm{\mid }+\mathrm{\mid }V(H_B)\mathrm{\mid }\ge \mathrm{\mid }A{\mathrm{\mid }}^c+\mathrm{\mid }B{\mathrm{\mid }}^c\ge 2(\eta n{)}^c=2{\eta }^c{n}^c=n^c$. This closes the induction and proves the claim from step 2.1.

Let $G$ be any nonempty graph in $\mathcal{C}$. By step 5.1, $G$ contains an induced $P_4$-free subgraph $H$ with $\mathrm{\mid }V(H)\mathrm{\mid }\ge \mathrm{\mid }V(G){\mathrm{\mid }}^c$. Then [L3] gives a clique or stable set in $H$ of size at least $\mathrm{\mid }V(H){\mathrm{\mid }}^{1\mathrm{/}2}\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{c\mathrm{/}2}$, and the same set is a clique or stable set in $G$. By [L4], the exponent $c\mathrm{/}2$ is an Erdős–Hajnal constant for $\mathcal{C}$.

We first prove the connected-case claim: for each $r\ge 2$ there are constants ${\epsilon }_r>0$ and $c_r>0$ such that every connected graph $J$ on $m\ge 2$ vertices has a vertex of degree greater than ${\epsilon }_{r}m$, or contains an induced $P_r$ starting at every vertex, or has a biclique of size at least $c_{r}m$ in $\bar{J}$. We prove this by induction on $r$.

For $r=2$, choose ${\epsilon }_2:=1\mathrm{/}2$ and $c_2:=1\mathrm{/}4$. Every vertex of a connected graph on at least two vertices is incident with an edge, so every vertex starts an induced $P_2$. Thus the claim holds for $r=2$.

Fix $r>2$, assume the claim for $r-1$, and let ${\epsilon }_r:={\epsilon }_{r-1}\mathrm{/}(2+{\epsilon }_{r-1})$. Since ${\epsilon }_r<1\mathrm{/}2$, choose any constant $0<c_r\le \min \{(1-2{\epsilon }_r)\mathrm{/}4,c_{r-1}(1-{\epsilon }_r)\mathrm{/}2\}$. Now let $J$ be a connected graph on $m\ge 2$ vertices for which the first outcome fails, so every vertex has degree at most ${\epsilon }_{r}m$. Fix a vertex $v_1$ and put $S:=V(J)\setminus (N_J(v_1)\cup \{v_1\})$. Then $\mathrm{\mid }S\mathrm{\mid }\ge (1-{\epsilon }_r)m-1$. Since $J$ is connected, $v_1$ has degree at least $1$, so $m\ge 1\mathrm{/}{\epsilon }_r$ and therefore $\mathrm{\mid }S\mathrm{\mid }\ge (1-2{\epsilon }_r)m$.

Suppose every connected component of $J[S]$ has size at most $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$. Choose components greedily until their union $A$ has size in the interval $[\mathrm{\mid }S\mathrm{\mid }\mathrm{/}4,\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2]$: if the running union first reaches $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}4$ before it exceeds $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$, stop there; otherwise the next component itself has size in $[\mathrm{\mid }S\mathrm{\mid }\mathrm{/}4,\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2]$ and we take that one alone. Let $B:=S\setminus A$. Then $\mathrm{\mid }A\mathrm{\mid },\mathrm{\mid }B\mathrm{\mid }\ge \mathrm{\mid }S\mathrm{\mid }\mathrm{/}4$, and [L3] makes $A$ anticomplete to $B$ in $J$. Hence $A$ and $B$ form a biclique of size at least $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}4\ge c_{r}m$ in $\bar{J}$.

Suppose instead that $J[S]$ has a connected component $S^{\mathrm{\prime }}$ with $\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }>\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$. Because $J$ is connected, some vertex $v_2\in N_J(v_1)$ has a neighbour in $S^{\mathrm{\prime }}$. Let $J_2:=J[S^{\mathrm{\prime }}\cup \{v_2\}]$, which is connected. Every vertex of $J_2$ still has degree at most ${\epsilon }_{r}m$, and ${\epsilon }_{r}m={\epsilon }_{r-1}(1-{\epsilon }_r)m\mathrm{/}2<{\epsilon }_{r-1}(\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }+1)={\epsilon }_{r-1}\mathrm{\mid }V(J_2)\mathrm{\mid }$ because $\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }+1>\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2+1\ge (1-{\epsilon }_r)m\mathrm{/}2$. So the first outcome of the induction hypothesis is false for $J_2$.

Apply the induction hypothesis to $J_2$ with parameter $r-1$. If outcome 2 holds there, then $J_2$ contains an induced $P_{r-1}$ starting at $v_2$, and prefixing this path with $v_1$ gives an induced $P_r$ in $J$ starting at $v_1$ because $v_1$ is adjacent to $v_2$ and has no neighbours in $S^{\mathrm{\prime }}$. If outcome 3 holds there, then $\overline{J_2}$ contains a biclique of size at least $c_{r-1}\mathrm{\mid }V(J_2)\mathrm{\mid }\ge c_{r-1}(1-{\epsilon }_r)m\mathrm{/}2\ge c_{r}m$, and the same biclique lies in $\bar{J}$. Thus, whenever outcome 1 fails for $J$, either outcome 2 or outcome 3 follows. This completes the induction and proves the connected-case claim.

Let $\epsilon :={\epsilon }_k\mathrm{/}8$. Because $P_k$ is the standard $k$-vertex path, [L1] applied to $H=P_k$ yields a constant $\delta >0$ such that every nonempty $P_k$-free graph has a vertex set of size at least $\delta n$ whose self-density is at most $\epsilon$ or at least $1-\epsilon$.

Let $G$ be a graph with no induced $P_k$ and no induced $\overline{P_k}$, and let $n:=\mathrm{\mid }V(G)\mathrm{\mid }\ge 2$. If $G$ has a set of size at least $\delta n$ and self-density at least $1-\epsilon$, apply the same argument to $\bar{G}$: an induced $P_k$ in $\bar{G}$ would be an induced $\overline{P_k}$ in $G$, and an induced $\overline{P_k}$ in $\bar{G}$ would be an induced $P_k$ in $G$. So $\bar{G}$ belongs to the same forbidden class. Replacing $G$ by $\bar{G}$ if necessary, we may assume that $G$ has a set $S_0$ with $\mathrm{\mid }{S}_0\mathrm{\mid }\ge \delta n$ and self-density at most $\epsilon$.

By [L2], the set $S_0$ contains a subset $S$ with $\mathrm{\mid }S\mathrm{\mid }\ge \mathrm{\mid }{S}_0\mathrm{\mid }\mathrm{/}2\ge \delta n\mathrm{/}2$ such that $S$ is $4\epsilon$-sparse. By [F1], every vertex of $G[S]$ therefore has degree at most $4\epsilon \mathrm{\mid }S\mathrm{\mid }={\epsilon }_k\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$.

If every connected component of $G[S]$ has size at most $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$, then the same greedy argument as in step 4.1 partitions those components into anticomplete sets $A,B\subseteq S$ with $\mathrm{\mid }A\mathrm{\mid },\mathrm{\mid }B\mathrm{\mid }\ge \mathrm{\mid }S\mathrm{\mid }\mathrm{/}4\ge \delta n\mathrm{/}8$. This is already a pure pair in $G$.

Otherwise $G[S]$ has a connected component $S^{\mathrm{\prime }}$ with $\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }>\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$. Every vertex of $G[S^{\mathrm{\prime }}]$ has degree at most ${\epsilon }_k\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2<{\epsilon }_k\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }$, and $G[S^{\mathrm{\prime }}]$ is $P_k$-free because induced subgraphs preserve forbidden induced paths. Applying the connected-case claim from step 5.1 to the connected graph $G[S^{\mathrm{\prime }}]$, outcome 1 is false by the degree bound and outcome 2 is false because $G[S^{\mathrm{\prime }}]$ contains no induced $P_k$ at all. Hence outcome 3 holds, so $\overline{G[S^{\mathrm{\prime }}]}$ has a biclique with both sides of size at least $c_k\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }\ge c_k\delta n\mathrm{/}4$. Equivalently, $G$ has an anticomplete pair of that size.

Let ${\gamma }_k:=\min \{\delta \mathrm{/}8,c_k\delta \mathrm{/}4\}$. Steps 9.1 and 9.2 show that every graph with no induced $P_k$ or $\overline{P_k}$ and at least two vertices contains a pure pair with both sides of size at least ${\gamma }_{k}n$. By [L4], the class forbidding $P_k$ and $\overline{P_k}$ has the strong Erdős–Hajnal property.

The previous theorem gives the strong Erdős–Hajnal property for the hereditary class of graphs forbidding $P_k$ and $\overline{P_k}$.

Applying [L2] to that class yields the Erdős–Hajnal property.