From Generalized Niceness to Erdős-Hajnal

Let $c\in (0,\frac{1}{2})$, $a_1\ge 1$, and $a_2>0$ be the constants supplied by [L1], and set $\xi :=c^2$. Choose $\delta >0$ from [L2] for the forbidden family $\bar{\mathcal{F}}$ and the parameter $\xi$.

Choose an integer $c_1\ge 1$ so large that $\delta \ge {\xi }^{c_1\mathrm{/}2},\delta \ge 2^{a_1-c_1},c_1\ge 2a_1,$ and set $c_2:=a_2$.

By [L2], the graph $G$ has a $\xi$-restricted induced subgraph $F\subseteq G$ with $\mathrm{\mid }F\mathrm{\mid }\ge \delta \mathrm{\mid }G\mathrm{\mid }$.

Suppose first that $x\ge \xi$. Then $F$ is also $x$-restricted, and $\mathrm{\mid }F\mathrm{\mid }\ge \delta \mathrm{\mid }G\mathrm{\mid }\ge 2^{a_1-c_1}\mathrm{\mid }G\mathrm{\mid }\ge x^{c_1-a_1}\mathrm{\mid }G\mathrm{\mid }\ge x^{c_1}\mathrm{\mid }G\mathrm{\mid },$ because $x\le \frac{1}{2}$ and $a_1\ge 1$. Hence outcome 1 holds.

Assume now that $x<\xi =c^2$. Then [L1] applies to the $c^2$-restricted graph $F$ and yields one of three conclusions: an $x$-restricted induced subgraph $S\subseteq F$ with $\mathrm{\mid }S\mathrm{\mid }\ge x^{a_1}\mathrm{\mid }F\mathrm{\mid }$, a clique or stable set of size at least $(x^{a_1}\mathrm{\mid }F\mathrm{\mid }{)}^{a_2}$, or a complete or anticomplete $(k,\mathrm{\mid }F\mathrm{\mid }\mathrm{/}{k}^{a_1})$-blockade in $F$ for some integer $k\ge 2$.

In the first branch, $x^{a_1}\mathrm{\mid }F\mathrm{\mid }\ge x^{a_1}\delta \mathrm{\mid }G\mathrm{\mid }\ge x^{a_1}{\xi }^{c_1\mathrm{/}2}\mathrm{\mid }G\mathrm{\mid }\ge x^{a_1+c_1\mathrm{/}2}\mathrm{\mid }G\mathrm{\mid }\ge x^{c_1}\mathrm{\mid }G\mathrm{\mid },$ because $x<\xi$ and $c_1\ge 2a_1$. So outcome 1 holds.

In the third branch, $\frac{\mathrm{\mid }F\mathrm{\mid }}{k^{a_1}}\ge \frac{\delta \mathrm{\mid }G\mathrm{\mid }}{k^{a_1}}\ge \frac{2^{a_1-c_1}\mathrm{\mid }G\mathrm{\mid }}{k^{a_1}}\ge \frac{\mathrm{\mid }G\mathrm{\mid }}{k^{c_1}},$ because $k\ge 2$. Thus the same blocks give outcome 2 in $G$.

In the second branch, the same inequality from step 4.1 gives $(x^{a_1}\mathrm{\mid }F\mathrm{\mid }{)}^{a_2}\ge (x^{c_1}\mathrm{\mid }G\mathrm{\mid }{)}^{c_2}$, so outcome 3 holds.

Steps 3.1, 4.1, 4.2, and 5.1 cover all possibilities, so one of the three stated outcomes always holds.

Let $F$ be an induced subgraph of $G$ with $\mathrm{\mid }F\mathrm{\mid }\ge {ϵ}^{2c_1}\mathrm{\mid }G\mathrm{\mid }$, and suppose for contradiction that $F$ has no complete or anticomplete $(k,\mathrm{\mid }F\mathrm{\mid }\mathrm{/}{k}^{c_1})$-blockade for any integer $k\in [2,{ϵ}^{-1}]$.

Apply [L1] to the graph $F$ with the parameter $x$. Because the blockade branch is excluded by step 1.1, either:

Suppose the restricted branch of step 2.1 holds. Then $\mathrm{\mid }S\mathrm{\mid }\ge x^{c_1}\mathrm{\mid }F\mathrm{\mid }\ge x^{c_1}{ϵ}^{2c_1}\mathrm{\mid }G\mathrm{\mid }=x^{c_1+2\mathrm{/}7}\mathrm{\mid }G\mathrm{\mid }=x^{-2c_1+2\mathrm{/}7}\mathrm{.}$ Since $c_1\ge 1$ and $0<x<1$, the exponent $-2c_1+2\mathrm{/}7$ is at most $-1$, so $\mathrm{\mid }S\mathrm{\mid }\ge x^{-1}$. After replacing $S$ by the same set in the complementary graph if necessary, [L3] lets us assume that $S$ is $x$-sparse.

Suppose instead that the blockade branch of step 2.1 holds. Then step 1.1 forces $k>{ϵ}^{-1}$. Choosing one vertex from each block gives a clique or stable set of size $k>{ϵ}^{-1}=\mathrm{\mid }G{\mathrm{\mid }}^{1\mathrm{/}(21c_1^2)}\ge \mathrm{\mid }G{\mathrm{\mid }}^c$, because $c\le (42c_1^2{)}^{-1}$. This contradicts the hypothesis on $G$.

Suppose instead that the clique-or-stable-set branch of step 2.1 holds. Then $(x^{c_1}\mathrm{\mid }F\mathrm{\mid }{)}^{c_2}\ge (x^{c_1}{ϵ}^{2c_1}\mathrm{\mid }G\mathrm{\mid }{)}^{c_2}=(x^{c_1+2\mathrm{/}7}\mathrm{\mid }G\mathrm{\mid }{)}^{c_2}\mathrm{.}$ Since $x=\mathrm{\mid }G{\mathrm{\mid }}^{-1\mathrm{/}(3c_1)}$, the inner factor equals $\mathrm{\mid }G{\mathrm{\mid }}^{1-(c_1+2\mathrm{/}7)\mathrm{/}(3c_1)}$, whose exponent is at least $1\mathrm{/}2$ because $c_1\ge 1$. Therefore $F$ contains a clique or stable set of size at least $\mathrm{\mid }G{\mathrm{\mid }}^{c_2\mathrm{/}2}\ge \mathrm{\mid }G{\mathrm{\mid }}^c$, because $c\le c_2\mathrm{/}2$. This again contradicts the hypothesis on $G$.

By [L2], $\alpha (G[S])\ge \frac{\mathrm{\mid }S\mathrm{\mid }}{x\mathrm{\mid }S\mathrm{\mid }+1}=\frac{1}{x+\mathrm{\mid }S{\mathrm{\mid }}^{-1}}\ge \frac{1}{x+x}\ge x^{-1\mathrm{/}2}\mathrm{.}$ Because $x=\mathrm{\mid }G{\mathrm{\mid }}^{-1\mathrm{/}(3c_1)}$, this gives a clique or stable set of size at least $\mathrm{\mid }G{\mathrm{\mid }}^{1\mathrm{/}(6c_1)}\ge \mathrm{\mid }G{\mathrm{\mid }}^c$, contradicting the hypothesis on $G$ because $c\le q^{-1}=1\mathrm{/}(42c_1^2)\le 1\mathrm{/}(6c_1)$.

All three branches from step 2.1 contradict the hypothesis on $G$, so the assumption in step 1.1 was false. Therefore $F$ has a complete or anticomplete $(k,\mathrm{\mid }F\mathrm{\mid }\mathrm{/}{k}^{c_1})$-blockade for some integer $k\in [2,{ϵ}^{-1}]$.

Let $c_1\ge 1$ and $c_2>0$ be the constants from [L1], put $q:=42c_1^2,m:=2^q,c:=\min \{q^{-1},c_2\mathrm{/}2\},$ and fix a nonempty $\bar{\mathcal{F}}$-free graph $G$. We will prove that $G$ has a clique or stable set of size at least $\mathrm{\mid }G{\mathrm{\mid }}^c$.

If $G$ already has such a clique or stable set, there is nothing to prove. So assume for contradiction that $G$ has no clique or stable set of size $\mathrm{\mid }G{\mathrm{\mid }}^c$. Because $c\le q^{-1}$, one has $m^c=(2^q{)}^c\le 2$. Hence every nonempty graph with at most $m$ vertices already has a clique or stable set of size at least $\mathrm{\mid }G{\mathrm{\mid }}^c$, so this forces $\mathrm{\mid }G\mathrm{\mid }>m$.

Define $x:=\mathrm{\mid }G{\mathrm{\mid }}^{-1\mathrm{/}(3c_1)},ϵ:=x^{1\mathrm{/}(7c_1)}\mathrm{.}$ Then $x\le m^{-1\mathrm{/}(3c_1)}=2^{-14c_1},ϵ\le 2^{-14c_1\mathrm{/}(7c_1)}=\frac{1}{4},$ so in particular $x<ϵ\le \frac{1}{4}$.

By [L2], every induced subgraph $F$ of $G$ with $\mathrm{\mid }F\mathrm{\mid }\ge {ϵ}^{2c_1}\mathrm{\mid }G\mathrm{\mid }$ has a complete or anticomplete $(k,\mathrm{\mid }F\mathrm{\mid }\mathrm{/}{k}^{c_1})$-blockade for some $k\in [2,{ϵ}^{-1}]$. Therefore [L3] applies with $a:=c_1$ and gives an $ϵ$-restricted induced subgraph $S\subseteq G$ with $\mathrm{\mid }S\mathrm{\mid }\ge {ϵ}^{3c_1}\mathrm{\mid }G\mathrm{\mid }$.

Since $ϵ=x^{1\mathrm{/}(7c_1)}=\mathrm{\mid }G{\mathrm{\mid }}^{-1\mathrm{/}(21c_1^2)}$ and $c_1\ge 1$, one has $\mathrm{\mid }S\mathrm{\mid }\ge {ϵ}^{3c_1}\mathrm{\mid }G\mathrm{\mid }={ϵ}^{-21c_1^2+3c_1}\ge {ϵ}^{-1}\mathrm{.}$ After taking complements if necessary, [L4] lets us assume that $S$ is $ϵ$-sparse.

Applying [L4] to the graph $G[S]$ yields $\alpha (G[S])\ge \frac{\mathrm{\mid }S\mathrm{\mid }}{ϵ\mathrm{\mid }S\mathrm{\mid }+1}=\frac{1}{ϵ+\mathrm{\mid }S{\mathrm{\mid }}^{-1}}\ge \frac{1}{2ϵ}\ge {ϵ}^{-1\mathrm{/}2}=\mathrm{\mid }G{\mathrm{\mid }}^{1\mathrm{/}(42c_1^2)}\ge \mathrm{\mid }G{\mathrm{\mid }}^c,$ because $c\le (42c_1^2{)}^{-1}$. This contradicts step 2.1.

Therefore every nonempty $\bar{\mathcal{F}}$-free graph has a clique or stable set of size at least $\mathrm{\mid }G{\mathrm{\mid }}^c$, so the complement class of $\mathcal{F}$ has the Erdős-Hajnal property. By [L5], $\mathcal{F}$ itself has the Erdős-Hajnal property.

Since $x=2^{-43\mathrm{/}3}$, one has $ϵ=x^{1\mathrm{/}7}=2^{-43\mathrm{/}21}>2^{-43\mathrm{/}3}=x\mathrm{.}$ Also $ϵ=2^{-43\mathrm{/}21}<2^{-2}=\frac{1}{4},$ because $43\mathrm{/}21>2$. Thus $x<ϵ\le \frac{1}{4}$.

The first threshold is $\mathrm{\mid }F{\mathrm{\mid }}_{\min }={ϵ}^2\mathrm{\mid }G\mathrm{\mid }=2^{-86\mathrm{/}21}\cdot 2^{43}=2^{817\mathrm{/}21},$ while ${ϵ}^{-1}=2^{43\mathrm{/}21}\mathrm{.}$ Since $817\mathrm{/}21>43\mathrm{/}21$, one gets $\mathrm{\mid }F{\mathrm{\mid }}_{\min }>{ϵ}^{-1}$.

The second threshold is $\mathrm{\mid }S{\mathrm{\mid }}_{\min }={ϵ}^3\mathrm{\mid }G\mathrm{\mid }=2^{-129\mathrm{/}21}\cdot 2^{43}=2^{774\mathrm{/}21}\mathrm{.}$ Again $774\mathrm{/}21>43\mathrm{/}21$, so $\mathrm{\mid }S{\mathrm{\mid }}_{\min }>{ϵ}^{-1}$.

Therefore, in the special case $c_1=1$, this concrete instance satisfies all of the numerical inequalities used in the source Erdős-Hajnal reduction at the next power-of-two graph order above the threshold.

Because each block of a blockade is nonempty, the four choices $v_i\in B_i$ are legitimate.

If $i\mathrm{\ne }j$, then $B_i$ is complete to $B_j$ by [L1], so the chosen vertices $v_i$ and $v_j$ are adjacent.

Therefore every pair among $v_1,v_2,v_3,v_4$ is adjacent, so these four vertices form a clique.

By [L1], after taking complements if necessary we may assume that $S$ is $ϵ$-sparse.

Applying [L2] to the $16$-vertex graph $G[S]$ gives $\alpha (G[S])\ge \frac{16}{ϵ\cdot 16+1}=\frac{16}{5}>3.$ Since $\alpha (G[S])$ is an integer, $\alpha (G[S])\ge 4$.

Because $\mathrm{\mid }G\mathrm{\mid }=2^{84}$, one has $\mathrm{\mid }G{\mathrm{\mid }}^{1\mathrm{/}42}=2^2=4$. Therefore the stable set from step 2.1 already has the same size as the final polynomial bound used in the A-page reduction. If the sparse side had arisen in the complement instead, [L1] would turn the same calculation into a clique of size $4$ in the original graph.