Introduction
A clique (stable set ) is a vertex set whose vertices are pairwise adjacent (nonadjacent, resp.). Ramsey [13 ] proved that for every integer k ≥ 1 k \ge1 k ≥ 1 , there exists a positive integer R ( k , k ) R(k,k) R ( k , k ) such that every graph on at least R ( k , k ) R(k,k) R ( k , k ) vertices contains a clique or stable set of size k k k . This shows that a sufficiently large graph must contain a large clique or stable set. Erdős [6 ] proved via the probabilistic method that for large n n n , there exists an n n n -vertex graph with no cliques or stable sets of size at least 2 log n 2\log n 2 log n . This shows that general graphs do not necessarily contain a clique or stable set of polynomial size. However, H H H -free graphs might behave differently.
Let G , H G,H G , H be graphs. We say that G G G is H H H -free if G G G has no induced subgraph that is isomorphic to H H H . In 1989, Erdős and Hajnal [7 ] showed that for any graph H H H , there exists a constant c = c ( H ) > 0 c=c(H)>0 c = c ( H ) > 0 such that any n n n -vertex H H H -free graph has a clique or stable set of size at least e c log n e^{c\sqrt{\log n}} e c l o g n . Erdős and Hajnal [7 ] further conjectured that one can improve the bound to a polynomial of n n n , which has become known as the Erdős-Hajnal conjecture.
Conjecture 1. (Erdős-Hajnal [7 ] ) For every graph H H H , there exists c = c ( H ) > 0 c=c(H)>0 c = c ( H ) > 0 such that every n n n -vertex H H H -free graph has a clique or stable set of size at least n c n^c n c .
We say a graph H H H has the Erdős-Hajnal property if H H H satisfies Conjecture 1. The property is preserved under complementation and, by a theorem of Alon, Pach and Solymosi [1 ] , under substitution. It holds for all graphs with at most four vertices, for the bull [4 ] , for the five-cycle [5 ] and for the five-vertex path P 5 P_5 P 5 [12 ] . The last result completed the case of all five-vertex graphs. Huang, Ju and Zhou [9 ] developed the method of [12 ] into a general framework and used it for two six-vertex graphs. We refer to [3 ] for a survey.
Paths are a natural family to consider next. Nguyen, Scott and Seymour [11 ] proved that every P s P_s P s -free graph on n n n vertices has a clique or stable set of size 2 ( log n ) 1 − o ( 1 ) 2^{(\log n)^{1-o(1)}} 2 ( l o g n ) 1 − o ( 1 ) . We prove the conjecture for all paths.
Theorem 1.1. For every integer s ≥ 1 s \ge1 s ≥ 1 there is τ s > 0 \tau_s > 0 τ s > 0 such that every P s P_s P s -free graph G G G has a clique or a stable set of size at least ∣ G ∣ τ s |G|^{\tau_s} ∣ G ∣ τ s .
Independent work. The proof of Theorem 1.1 , together with its Lean formalization, was made public on 7 October 2026 and archived on Zenodo on 9 October 2026 [16 ] . Later, on 17 October 2026, Nguyen [10 ] posted on arXiv an independent proof of the Erdős–Hajnal property for all paths, by a different method. As reported in [10 ] , a team at Google Research and Google DeepMind has also announced an independent proof.
Preliminaries
Notation
All graphs are finite and simple. For a graph G G G we write ∣ G ∣ |G| ∣ G ∣ for its number of vertices, G ‾ \overline{G} G for its complement and G [ S ] G[S] G [ S ] for the subgraph induced on S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) . We write N ( v ) N(v) N ( v ) for the set of neighbors of v v v in G G G . P r P_r P r is the path with r r r vertices. A class of graphs is hereditary if it is closed under taking induced subgraphs. A hereditary class C \mathcal{C} C has the Erdős–Hajnal property if there is τ > 0 \tau> 0 τ > 0 such that every G ∈ C G \in\mathcal{C} G ∈ C has a clique or a stable set of size at least ∣ G ∣ τ |G|^\tau ∣ G ∣ τ . We call τ \tau τ an Erdős–Hajnal exponent of C \mathcal{C} C , and for a graph H H H we write EH ( H ) \operatorname{EH}(H) EH ( H ) for the statement that the class of H H H -free graphs has this property. We write hom ( G ) \operatorname{hom}(G) hom ( G ) for the largest size of a clique or a stable set of G G G and [ k ] = { 1 , … , k } [k] = \{1, \ldots, k\} [ k ] = { 1 , … , k } for an integer k ≥ 1 k \ge1 k ≥ 1 .
Let A , B ⊆ V ( G ) A, B \subseteq V(G) A , B ⊆ V ( G ) be disjoint. A A A is complete (anticomplete ) to B B B if every vertex of A A A is adjacent (nonadjacent) to every vertex of B B B . A vertex v ∉ A v \notin A v ∈ / A is mixed on A A A if it has a neighbor and a nonneighbor in A A A . For x > 0 x > 0 x > 0 , B B B is x x x -sparse to A A A if every vertex of B B B has at most x ∣ A ∣ x|A| x ∣ A ∣ neighbors in A A A , and ( A , B ) (A, B) ( A , B ) is weakly x x x -sparse if the number of edges between A A A and B B B is at most x ∣ A ∣ ∣ B ∣ x|A||B| x ∣ A ∣∣ B ∣ . If B B B is x x x -sparse to A A A , then ( A , B ) (A, B) ( A , B ) is weakly x x x -sparse.
G G G is x x x -sparse if its maximum degree is at most x ∣ G ∣ x|G| x ∣ G ∣ , and x x x -restricted if G G G or G ‾ \overline{G} G is x x x -sparse. A set S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) is x x x -sparse (x x x -restricted) if G [ S ] G[S] G [ S ] is. A graph is anticonnected if its complement is connected, and the anticonnected components of G G G are the subgraphs induced on the vertex sets of the components of G ‾ \overline{G} G .
A blockade in G G G is a sequence B = ( B 1 , … , B k ) \mathcal{B} = (B_1, \ldots, B_k) B = ( B 1 , … , B k ) of disjoint subsets of V ( G ) V(G) V ( G ) . Its length is k k k and its width is min i ∣ B i ∣ \min_i |B_i| min i ∣ B i ∣ . It is a ( k , w ) (k,w) ( k , w ) -blockade if its length is at least k k k and its width is at least w w w . It is pure if every pair ( B i , B j ) (B_i, B_j) ( B i , B j ) is complete or anticomplete, and complete (anticomplete ) if every pair is complete (anticomplete). We write V ( B ) = ⋃ i = 1 k B i V(\mathcal{B}) = \bigcup_{i=1}^k B_i V ( B ) = ⋃ i = 1 k B i . We call a blockade B \mathcal{B} B
x x x -semisparse if for all i < j i < j i < j , either B j B_j B j is complete to B i B_i B i , or B j B_j B j is x x x -sparse to B i B_i B i ;
weakly x x x -semisparse if for all distinct i , j i,j i , j the pair ( B i , B j ) (B_i, B_j) ( B i , B j ) is complete or weakly x x x -sparse.
Following [12 , 9 ] , an ( ℓ , w ) (\ell,w) ( ℓ , w ) -comb in G G G is a sequence ( ( a i , B i ) : i ∈ [ ℓ ] ) ((a_i,B_i): i \in[\ell]) (( a i , B i ) : i ∈ [ ℓ ]) such that ( B 1 , … , B ℓ ) (B_1,\ldots,B_\ell) ( B 1 , … , B ℓ ) is an ( ℓ , w ) (\ell,w) ( ℓ , w ) -blockade, the vertices a 1 , … , a ℓ a_1,\ldots,a_\ell a 1 , … , a ℓ are distinct and do not belong to B 1 ∪ ⋯ ∪ B ℓ B_1 \cup\cdots\cup B_\ell B 1 ∪ ⋯ ∪ B ℓ , and for all distinct i , j i,j i , j the apex a i a_i a i is complete to B i B_i B i and anticomplete to B j B_j B j . A special vertex for the comb is a vertex v v v outside the comb that is complete to B 1 ∪ ⋯ ∪ B ℓ B_1 \cup\cdots\cup B_\ell B 1 ∪ ⋯ ∪ B ℓ and anticomplete to { a 1 , … , a ℓ } \{a_1,\ldots,a_\ell\} { a 1 , … , a ℓ } .
Results we use
The following results are used later.
Theorem 2.1 (Rödl [14 ] ). For every graph H H H and every ε ∈ ( 0 , 1 2 ) \varepsilon\in(0,\frac{1}{2}) ε ∈ ( 0 , 2 1 ) there exists δ > 0 \delta> 0 δ > 0 such that every H H H -free graph G G G has an ε \varepsilon ε -restricted induced subgraph with at least δ ∣ G ∣ \delta|G| δ ∣ G ∣ vertices.
Theorem 2.2 (Statement 3.1 of Nguyen–Scott–Seymour [11 ] ). Let s ≥ 2 s \ge2 s ≥ 2 and 0 < z ≤ 1 / ( 60 s ) 0 < z \le1/(60s) 0 < z ≤ 1/ ( 60 s ) . Every z 2 z^2 z 2 -sparse P s P_s P s -free graph G G G with ∣ G ∣ ≥ z − 2 |G| \ge z^{-2} ∣ G ∣ ≥ z − 2 has an anticomplete ( 1 / z , ⌊ z 2 ∣ G ∣ ⌋ ) (1/z,\lfloor z^2|G|\rfloor) ( 1/ z , ⌊ z 2 ∣ G ∣ ⌋) -blockade.
(In [11 ] there is no lower bound on ∣ G ∣ |G| ∣ G ∣ , and then the blocks may be empty. We add the hypothesis ∣ G ∣ ≥ z − 2 |G| \ge z^{-2} ∣ G ∣ ≥ z − 2 , which gives ⌊ z 2 ∣ G ∣ ⌋ ≥ 1 \lfloor z^2|G|\rfloor\ge1 ⌊ z 2 ∣ G ∣ ⌋ ≥ 1 , so that the blocks are nonempty. With this extra hypothesis the statement is a special case of the one in [11 ] .)
Lemma 2.3 (Lemma 4.1 of Nguyen–Scott–Seymour [12 ] ). Let k ≥ 2 k \ge2 k ≥ 2 be an integer, and let G G G be a graph whose anticonnected components all have fewer than ∣ G ∣ / k |G|/k ∣ G ∣/ k vertices. Then G G G has a complete ( k , ∣ G ∣ / k 2 ) (k,|G|/k^2) ( k , ∣ G ∣/ k 2 ) -blockade.
Lemma 2.4 (Lemma 2.10 of Huang–Ju–Zhou [9 ] , contained in Lemma 5.2 of [12 ] ). Let 0 < x ≤ y ≤ 2 − 8 0 < x \le y \le2^{-8} 0 < x ≤ y ≤ 2 − 8 . For every y 3 y^3 y 3 -sparse graph G G G with ∣ G ∣ ≥ y − 4 |G| \ge y^{-4} ∣ G ∣ ≥ y − 4 , one of the following holds:
there are disjoint X , Z ⊆ V ( G ) X,Z \subseteq V(G) X , Z ⊆ V ( G ) with ∣ X ∣ ≥ y 4 ∣ G ∣ |X| \ge y^4|G| ∣ X ∣ ≥ y 4 ∣ G ∣ and ∣ Z ∣ ≥ ( 1 − 4 y ) ∣ G ∣ |Z| \ge(1-4y)|G| ∣ Z ∣ ≥ ( 1 − 4 y ) ∣ G ∣ such that Z Z Z is x x x -sparse to X X X ;
G G G is 2 y 4 2y^4 2 y 4 -*sparse; or
for some integer ℓ ∈ [ y − 1 , x − 2 ] \ell\in[y^{-1},x^{-2}] ℓ ∈ [ y − 1 , x − 2 ] there is an ( ℓ , y 4 ∣ G ∣ / ℓ 2 ) (\ell,y^4|G|/\ell^2) ( ℓ , y 4 ∣ G ∣/ ℓ 2 ) -comb in G G G with a special vertex.
The first two outcomes are directly useful for iterative sparsification. The comb is the main case, and in the proof of the local alternative for P s ‾ \overline{P_s} P s -free graphs it is the only case that uses the forbidden graph. In [12 , 9 ] the comb is turned into a pure blockade. For P s P_s P s we turn it into a weakly semisparse blockade or a restricted set in Lemma 6.2.
Theorem 2.5 (Alon–Pach–Solymosi [1 ] , see also [9 Theorem 1.4] ). If H 1 H_1 H 1 and H 2 H_2 H 2 have the Erdős–Hajnal property, then so does every graph obtained from H 1 H_1 H 1 by substituting H 2 H_2 H 2 for a vertex.
Theorem 2.6 (Chvátal [2 ] ). Let G G G be a graph with a linear order < < < of V ( G ) V(G) V ( G ) such that there is no induced path a b c d abcd ab c d of G G G with a < b a < b a < b and d < c d < c d < c . Then χ ( G ) = ω ( G ) \chi(G)=\omega(G) χ ( G ) = ω ( G ) . In particular G G G has a clique or a stable set of size at least ∣ G ∣ 1 / 2 |G|^{1/2} ∣ G ∣ 1/2 .
(The second statement follows from ∣ G ∣ ≤ α ( G ) χ ( G ) = α ( G ) ω ( G ) |G| \le\alpha(G)\chi(G)=\alpha(G)\omega(G) ∣ G ∣ ≤ α ( G ) χ ( G ) = α ( G ) ω ( G ) .) A graph with a linear order as in Theorem 2.6 is called perfectly orderable [2 ] .
The reduction of Huang, Ju and Zhou
The last step of our proof is the reduction of Huang, Ju and Zhou [9 ] , which refines the final part of [12 ] . We recall their definitions, specialised to a single forbidden graph and to a hereditary class.
Definition 2.7 ([9 ] ). Let C \mathcal{C} C be a hereditary class of graphs. We say C \mathcal{C} C is generalized nice if there are constants c 1 ≥ 3 c_1 \ge3 c 1 ≥ 3 , c 2 ≥ 8 c_2 \ge8 c 2 ≥ 8 , c 3 , c 4 , c 5 , c 8 > 0 c_3,c_4,c_5,c_8 > 0 c 3 , c 4 , c 5 , c 8 > 0 , c 6 ≥ 1 c_6 \ge1 c 6 ≥ 1 , c 7 ≥ 4 c_7 \ge4 c 7 ≥ 4 such that for every G ∈ C G \in\mathcal{C} G ∈ C and every 0 < ε < 1 2 0 < \varepsilon< \frac{1}{2} 0 < ε < 2 1 , either
G G G has an ( ε − 1 , ε c 1 ∣ G ∣ ) (\varepsilon^{-1},\varepsilon^{c_1}|G|) ( ε − 1 , ε c 1 ∣ G ∣ ) -blockade whose blocks are pairwise complete or weakly ε c 2 \varepsilon^{c_2} ε c 2 -sparse;
G G G has a clique or stable set of size at least ( ε c 3 ∣ G ∣ ) c 4 (\varepsilon^{c_3}|G|)^{c_4} ( ε c 3 ∣ G ∣ ) c 4 ;
G G G has a complete or anticomplete ( k , ∣ G ∣ / k c 5 ) (k,|G|/k^{c_5}) ( k , ∣ G ∣/ k c 5 ) -blockade with k ≥ ε − c 6 k \ge\varepsilon^{-c_6} k ≥ ε − c 6 ; or
G G G has an ε c 7 \varepsilon^{c_7} ε c 7 -restricted induced subgraph with at least ε c 8 ∣ G ∣ \varepsilon^{c_8}|G| ε c 8 ∣ G ∣ vertices.
Our proof will produce only the first two outcomes. We retain all four outcomes to match the definition in [9 ] .
Definition 2.8 ([9 ] ). A graph H H H is wonderful if there is a constant a ≥ 6 a \ge6 a ≥ 6 such that the following holds for every y ∈ ( 0 , 1 2 ) y \in(0,\frac{1}{2}) y ∈ ( 0 , 2 1 ) and every H ‾ \overline{H} H -free graph G G G . If ( B 1 , … , B ℓ ) (B_1,\ldots,B_\ell) ( B 1 , … , B ℓ ) is an ( ℓ , w ) (\ell,w) ( ℓ , w ) -blockade in G G G with ℓ ≥ y − a \ell\ge y^{-a} ℓ ≥ y − a , whose blocks are anticonnected and of the same size, and every two blocks are complete or y a y^a y a -sparse to each other, then either
G G G has a y 4 y^4 y 4 -restricted induced subgraph with at least w w w vertices; or
there is i ∈ [ ℓ ] i \in[\ell] i ∈ [ ℓ ] such that at most y ∣ G ∣ y|G| y ∣ G ∣ vertices v ∈ V ( G ) ∖ ( B 1 ∪ ⋯ ∪ B ℓ ) v \in V(G) \setminus(B_1 \cup\cdots\cup B_\ell) v ∈ V ( G ) ∖ ( B 1 ∪ ⋯ ∪ B ℓ ) satisfy 0 < ∣ N ( v ) ∩ B i ∣ < 1 2 ∣ B i ∣ 0 < |N(v) \cap B_i| < \frac{1}{2}|B_i| 0 < ∣ N ( v ) ∩ B i ∣ < 2 1 ∣ B i ∣ .
The graphs in this definition are H ‾ \overline{H} H -free. For H = P s H=P_s H = P s they are the graphs of the class of P s ‾ \overline{P_s} P s -free graphs, so densities and blockades are in G G G , while the induced copies of P s P_s P s that give contradictions are found in G ‾ \overline{G} G .
A graph H H H is leaf-reducible if it has a vertex v v v of degree one such that H ∖ v H \setminus v H ∖ v has the Erdős–Hajnal property [9 ] . For example, P s P_s P s is leaf-reducible whenever EH ( P s − 1 ) \operatorname{EH}(P_{s-1}) EH ( P s − 1 ) holds.
Theorem 2.9 (A hereditary version of Lemma 1.12 of [9 ] ). Let H H H be leaf-reducible and wonderful , and let C \mathcal{C} C be a hereditary class of H ‾ \overline{H} H -free graphs. If C \mathcal{C} C is generalized nice, then C \mathcal{C} C has the Erdős–Hajnal property.
In the reduction in [9 ] , Section 3, generalized niceness is applied only to the graph under consideration and its induced subgraphs. These graphs remain in C \mathcal{C} C by heredity, while the remaining hypotheses follow from the leaf-reducibility and wonderfulness of H H H and the fact that every graph in C \mathcal{C} C is H ‾ \overline{H} H -free. When the complement is sparse, [9 ] Lemma 2.7 applies to the H H H -free complement, without requiring it to belong to C \mathcal{C} C . All constants depend only on H H H and the constants in Definition 2.7, so the resulting Erdős–Hajnal exponent is uniform over C \mathcal{C} C .
Wonderfulness of paths
In this section we prove that P s P_s P s is wonderful whenever EH ( P s − 1 ) \operatorname{EH}(P_{s-1}) EH ( P s − 1 ) holds. This is the first of our two new ingredients. Throughout this section, let s ≥ 3 s \ge3 s ≥ 3 be an integer and put h = s − 1 h=s-1 h = s − 1 .
We begin with some definitions. For a graph H H H and an integer c ≥ 1 c \ge1 c ≥ 1 , we define R ( H , c ) R(H,c) R ( H , c ) recursively. Set R ( H , 1 ) = H R(H,1)=H R ( H , 1 ) = H . For c ≥ 2 c \ge2 c ≥ 2 , let R ( H , c ) R(H,c) R ( H , c ) be the graph obtained from H H H by substituting a copy of R ( H , c − 1 ) R(H,c-1) R ( H , c − 1 ) for every vertex. We also define a graph H ( c ) H^{(c)} H ( c ) as follows. First construct pairwise vertex-disjoint graphs S h , S h − 1 , … , S 1 S_h,S_{h-1},\ldots,S_1 S h , S h − 1 , … , S 1 in this order. Set c h = 2 h − 1 c_h=2^{h-1} c h = 2 h − 1 and let S h S_h S h be a copy of R ( H , c h ) R(H,c_h) R ( H , c h ) . For i = h − 1 , h − 2 , … , 1 i=h-1,h-2,\ldots,1 i = h − 1 , h − 2 , … , 1 , once S i + 1 , … , S h S_{i+1},\ldots,S_h S i + 1 , … , S h have been constructed, set c i = 2 i − 1 + ∑ j = i + 1 h ∣ S j ∣ c_i=2^{i-1+\sum_{j=i+1}^{h}|S_j|} c i = 2 i − 1 + ∑ j = i + 1 h ∣ S j ∣ and let S i S_i S i be a copy of R ( H , c i ) R(H,c_i) R ( H , c i ) . Let H ( h ) H^{(h)} H ( h ) be obtained from the path P h = 1 2 ⋯ h P_h=1\,2\cdots h P h = 1 2 ⋯ h by substituting S i S_i S i for vertex i i i for each i ∈ [ h ] i\in[h] i ∈ [ h ] . Thus, for distinct i , j ∈ [ h ] i,j\in[h] i , j ∈ [ h ] , the sets V ( S i ) V(S_i) V ( S i ) and V ( S j ) V(S_j) V ( S j ) are complete to each other if ∣ i − j ∣ = 1 |i-j|=1 ∣ i − j ∣ = 1 , and anticomplete otherwise. We call S 1 , … , S h S_1,\ldots,S_h S 1 , … , S h the fibres of H ( h ) H^{(h)} H ( h ) .
We then give two useful properties.
Lemma 3.1. Let H H H be a graph and let c ≥ 1 c\ge1 c ≥ 1 be an integer. Every coloring of V ( R ( H , c ) ) V(R(H,c)) V ( R ( H , c )) with at most c c c colors has a monochromatic induced copy of H H H .
Proof. We prove this lemma by induction on c c c . If c = 1 c=1 c = 1 , then R ( H , 1 ) = H R(H,1)=H R ( H , 1 ) = H , and the conclusion holds. Suppose that c ≥ 2 c\ge2 c ≥ 2 , and let φ \varphi φ be a c c c -coloring of R ( H , c ) R(H,c) R ( H , c ) . For each v ∈ V ( H ) v\in V(H) v ∈ V ( H ) , let R v R_v R v be the copy of R ( H , c − 1 ) R(H,c-1) R ( H , c − 1 ) indexed by v v v in the construction of R ( H , c ) R(H,c) R ( H , c ) . If some R v R_v R v uses at most c − 1 c-1 c − 1 colors, then by the induction hypothesis, R v R_v R v contains a monochromatic induced copy of H H H . So we may assume that every R v R_v R v uses all c c c colors. For each v ∈ V ( H ) v\in V(H) v ∈ V ( H ) , choose a vertex x v ∈ V ( R v ) x_v\in V(R_v) x v ∈ V ( R v ) with φ ( x v ) = 1 \varphi(x_v)=1 φ ( x v ) = 1 . By construction, { x v : v ∈ V ( H ) } \{x_v:v\in V(H)\} { x v : v ∈ V ( H )} induces a copy of H H H whose vertices all have color 1. □ \square □
Lemma 3.2. For every spanning subgraph M M M of H ( h ) H^{(h)} H ( h ) , there are induced copies H i H_i H i of H H H in S i S_i S i (i ∈ [ h ] i\in[h] i ∈ [ h ] ) such that every pair ( H i , H j ) (H_i,H_j) ( H i , H j ) is complete or anticomplete in M M M .
Proof. For each i ∈ [ h ] i\in[h] i ∈ [ h ] , put T i = ⋃ j = i + 1 h V ( S j ) T_i=\bigcup_{j=i+1}^{h}V(S_j) T i = ⋃ j = i + 1 h V ( S j ) . We choose induced copies H i H_i H i of H H H in S i S_i S i successively for i = 1 , … , h i=1,\ldots,h i = 1 , … , h . Throughout the construction, we require that N M ( v ) ∩ T j N_M(v)\cap T_j N M ( v ) ∩ T j is the same for every v ∈ V ( H j ) v\in V(H_j) v ∈ V ( H j ) whenever H j H_j H j has been chosen.
Suppose that H 1 , … , H i − 1 H_1,\ldots,H_{i-1} H 1 , … , H i − 1 have been chosen. For each j < i j<i j < i , since V ( S i ) ⊆ T j V(S_i)\subseteq T_j V ( S i ) ⊆ T j , the sets N M ( w ) ∩ V ( S i ) N_M(w)\cap V(S_i) N M ( w ) ∩ V ( S i ) are equal for all w ∈ V ( H j ) w\in V(H_j) w ∈ V ( H j ) . Consequently, every vertex v ∈ V ( S i ) v\in V(S_i) v ∈ V ( S i ) is complete or anticomplete to V ( H j ) V(H_j) V ( H j ) in M M M . Let b j ( v ) = 1 b_j(v)=1 b j ( v ) = 1 if v v v is complete to V ( H j ) V(H_j) V ( H j ) in M M M , and let b j ( v ) = 0 b_j(v)=0 b j ( v ) = 0 otherwise. Color each vertex v ∈ V ( S i ) v\in V(S_i) v ∈ V ( S i ) by the tuple ( b 1 ( v ) , … , b i − 1 ( v ) , N M ( v ) ∩ T i ) (b_1(v),\ldots,b_{i-1}(v),N_M(v)\cap T_i) ( b 1 ( v ) , … , b i − 1 ( v ) , N M ( v ) ∩ T i ) . There are at most 2 i − 1 2^{i-1} 2 i − 1 possibilities for the first i − 1 i-1 i − 1 entries and at most 2 ∣ T i ∣ 2^{|T_i|} 2 ∣ T i ∣ possibilities for the last entry. Thus at most 2 i − 1 + ∣ T i ∣ = c i 2^{i-1+|T_i|}=c_i 2 i − 1 + ∣ T i ∣ = c i colors occur. Since S i S_i S i is a copy of R ( H , c i ) R(H,c_i) R ( H , c i ) , Lemma 3.1 gives a monochromatic induced copy H i H_i H i of H H H in S i S_i S i .
For each j < i j<i j < i , the value b j ( v ) b_j(v) b j ( v ) is constant over v ∈ V ( H i ) v\in V(H_i) v ∈ V ( H i ) , so V ( H i ) V(H_i) V ( H i ) and V ( H j ) V(H_j) V ( H j ) are complete or anticomplete to each other in M M M . Moreover, N M ( v ) ∩ T i N_M(v)\cap T_i N M ( v ) ∩ T i is the same for every v ∈ V ( H i ) v\in V(H_i) v ∈ V ( H i ) , preserving the required condition. Continuing to i = h i=h i = h gives the desired copies. □ \square □
Definition 3.3. Let Q Q Q be a graph with vertex set [ q ] [q] [ q ] . A two-labeled lift of Q Q Q is a graph L L L with vertex set { v , z 1 , … , z q , b 1 , … , b q } \{v,z_1,\ldots,z_q,b_1,\ldots,b_q\} { v , z 1 , … , z q , b 1 , … , b q } (all distinct) such that
v v v is adjacent to every z i z_i z i and to no b i b_i b i ;
for distinct i , j i,j i , j : z i z j z_i z_j z i z j and b i b j b_i b_j b i b j are edges if and only if i j ∈ E ( Q ) ij\in E(Q) ij ∈ E ( Q ) ;
for distinct i , j i,j i , j : if b i b j b_i b_j b i b j is an edge then i j ∈ E ( Q ) ij\in E(Q) ij ∈ E ( Q ) .
The adjacency between z i z_i z i and b i b_i b i is arbitrary, and so is the set of edges b i b j b_i b_j b i b j with i j ∈ E ( Q ) ij\in E(Q) ij ∈ E ( Q ) . We call z 1 , … , z q z_1,\ldots,z_q z 1 , … , z q the z z z -vertices, b 1 , … , b q b_1,\ldots,b_q b 1 , … , b q the b b b -vertices, and i i i the index of z i z_i z i and of b i b_i b i .
Figure 1. A two-labeled lift of Q = P 4 Q = P_4 Q = P 4 . Solid edges are forced by Q Q Q . Dashed b i b j b_i b_j b i b j edges are optional (allowed only on edges of Q Q Q ). Dotted z i b i z_i b_i z i b i edges are arbitrary.
An r r r -arm in a two-labeled lift is an induced path p 1 p 2 ⋯ p r p_1p_2\cdots p_r p 1 p 2 ⋯ p r of the lift such that p 1 p_1 p 1 is a z z z -vertex and p 2 , … , p r p_2,\ldots,p_r p 2 , … , p r are b b b -vertices. Since v v v is adjacent to p 1 p_1 p 1 and to no b b b -vertex, v p 1 p 2 ⋯ p r vp_1p_2\cdots p_r v p 1 p 2 ⋯ p r is an induced P r + 1 P_{r+1} P r + 1 . The arm is index-transversal if its vertices have distinct indices. We then give a graph Q h Q_h Q h such that EH ( Q h ) \operatorname{EH}(Q_h) EH ( Q h ) if EH ( P h ) \operatorname{EH}(P_h) EH ( P h ) and prove that every two-labeled lift of Q h Q_h Q h contains an induced P h + 1 P_{h+1} P h + 1 .
Lemma 3.4. For every h ≥ 2 h \ge2 h ≥ 2 there is a graph Q h Q_h Q h such that
EH ( Q h ) \operatorname{EH}(Q_h) EH ( Q h ) if EH ( P h ) \operatorname{EH}(P_h) EH ( P h ) ; and
every two-labeled lift of Q h Q_h Q h contains an induced P h + 1 P_{h+1} P h + 1 .
Proof. Let Q 2 = P 2 Q_2=P_2 Q 2 = P 2 on { 1 , 2 } \{1,2\} { 1 , 2 } . For 2 ≤ r < h 2 \le r < h 2 ≤ r < h , let Q r + 1 = H ( h ) Q_{r+1}=H^{(h)} Q r + 1 = H ( h ) with H = Q r H=Q_r H = Q r . We claim that Q h Q_h Q h suffices. Since Q h Q_h Q h is obtained from P h P_h P h and P 2 P_2 P 2 by repeated substitution, by [1 ] , EH ( Q h ) \operatorname{EH}(Q_h) EH ( Q h ) if EH ( P h ) \operatorname{EH}(P_h) EH ( P h ) .
For 2 ≤ r ≤ h 2 \le r \le h 2 ≤ r ≤ h , say that a graph Q Q Q is r r r -forcing if every two-labeled lift of Q Q Q contains an induced P h + 1 P_{h+1} P h + 1 or an index-transversal r r r -arm. We claim that for 2 ≤ r ≤ h 2 \le r \le h 2 ≤ r ≤ h , Q r Q_r Q r is r r r -forcing. Since Q 2 = P 2 Q_2=P_2 Q 2 = P 2 , in every two-labeled lift of Q 2 Q_2 Q 2 , z 1 b 2 z_1b_2 z 1 b 2 is an edge. So z 1 b 2 z_1b_2 z 1 b 2 is an index-transversal 2-arm. Thus Q 2 Q_2 Q 2 is 2-forcing. Now let 2 ≤ r < h 2 \le r < h 2 ≤ r < h and suppose Q r Q_r Q r is r r r -forcing. We then prove Q r + 1 Q_{r+1} Q r + 1 is ( r + 1 ) (r+1) ( r + 1 ) -forcing.
Suppose to the contrary that Q r + 1 Q_{r+1} Q r + 1 is not ( r + 1 ) (r+1) ( r + 1 ) -forcing. Let L L L be a two-labeled lift of Q r + 1 Q_{r+1} Q r + 1 with no induced P h + 1 P_{h+1} P h + 1 . Let M M M be the graph on V ( Q r + 1 ) V(Q_{r+1}) V ( Q r + 1 ) in which distinct indices i , j i,j i , j are adjacent if and only if b i b j ∈ E ( L ) b_i b_j \in E(L) b i b j ∈ E ( L ) . So M M M is a spanning subgraph of Q r + 1 Q_{r+1} Q r + 1 . By Lemma 3.2 , there are induced copies H 1 , … , H h H_1,\ldots,H_h H 1 , … , H h of Q r Q_r Q r , with H i H_i H i in the i i i -th fibre of Q r + 1 Q_{r+1} Q r + 1 , that are pairwise complete or anticomplete in M M M . Note that the vertices of L L L with indices in H i H_i H i (containing both b b b -vertices and z z z -vertices), together with v v v , induce a two-labeled lift of Q r Q_r Q r . So each H i H_i H i carries an index-transversal r r r -arm. For i < h i<h i < h , let e i = 1 e_i=1 e i = 1 if H i H_i H i is complete to H i + 1 H_{i+1} H i + 1 in M M M and e i = 0 e_i=0 e i = 0 if H i H_i H i is anticomplete to H i + 1 H_{i+1} H i + 1 in M M M .
Claim 3.4.1. e 1 = ⋯ = e r − 1 = 1 e_1=\cdots=e_{r-1}=1 e 1 = ⋯ = e r − 1 = 1 .
Proof of Claim 3.4.1. Suppose e i = 0 e_i=0 e i = 0 for some i ≤ r − 1 i\le r-1 i ≤ r − 1 . Take an r r r -arm z ′ , b 1 ′ , … , b r − 1 ′ z',b'_1,\ldots,b'_{r-1} z ′ , b 1 ′ , … , b r − 1 ′ with indices in H i H_i H i , any b b b -vertex b ^ \hat{b} b ^ with index in H i + 1 H_{i+1} H i + 1 , and a z z z -vertex z ^ j \hat{z}_j z ^ j with index in H j H_j H j for each j = i + 2 , … , h j=i+2,\ldots,h j = i + 2 , … , h . Then b r − 1 ′ , … , b 1 ′ , z ′ , b ^ , z ^ i + 2 , … , z ^ h b'_{r-1},\ldots,b'_1,z',\hat{b},\hat{z}_{i+2},\ldots,\hat{z}_h b r − 1 ′ , … , b 1 ′ , z ′ , b ^ , z ^ i + 2 , … , z ^ h is an induced path of L L L . Its vertices have distinct indices (the arm is index-transversal, and the other vertices lie in other fibres). Recall that two indices in distinct fibres are adjacent in Q r + 1 Q_{r+1} Q r + 1 if and only if their fibres are consecutive. Also, for distinct indices k , m k,m k , m , the pair b k b m b_kb_m b k b m is an edge of L L L if and only if k m ∈ E ( M ) km\in E(M) k m ∈ E ( M ) . We check all pairs:
b ^ r − 1 , … , b ^ 1 , z ^ ′ \hat{b}_{r-1},\ldots,\hat{b}_{1},\hat{z}' b ^ r − 1 , … , b ^ 1 , z ^ ′ is an induced path, being an arm;
z ^ ′ b ^ \hat{z}'\hat{b} z ^ ′ b ^ is an edge, since their indices lie in the consecutive fibres i i i and i + 1 i+1 i + 1 ;
b ^ \hat{b} b ^ is nonadjacent to every b ^ k ′ \hat{b}'_k b ^ k ′ , since ( H i , H i + 1 ) (H_i,H_{i+1}) ( H i , H i + 1 ) is anticomplete in M M M (e i = 0 e_i=0 e i = 0 );
b ^ z ^ i + 2 \hat{b}\hat{z}_{i+2} b ^ z ^ i + 2 and z ^ j z ^ j + 1 \hat{z}_j\hat{z}_{j+1} z ^ j z ^ j + 1 (i + 2 ≤ j < h i+2\leq j<h i + 2 ≤ j < h ) are edges, since their indices lie in consecutive fibres;
every other pair consists of some z ^ j \hat{z}_j z ^ j and a vertex whose index lies in a fibre at distance at least two from fibre j j j , so it is a nonedge.
The path has r + h − i ≥ h + 1 r+h-i\geq h+1 r + h − i ≥ h + 1 vertices (as i ≤ r − 1 i\leq r-1 i ≤ r − 1 ), so L L L contains an induced P h + 1 P_{h+1} P h + 1 , a contradiction. ■
By Claim 3.4.1, choose a z z z -vertex z ^ \hat{z} z ^ with index in H r + 1 H_{r+1} H r + 1 (this fibre exists as r + 1 ≤ h r+1\leq h r + 1 ≤ h ) and a b b b -vertex b ^ i \hat{b}_i b ^ i with index in H i H_i H i for i = 1 , … , r i=1,\ldots,r i = 1 , … , r . Then z ^ , b ^ r , b ^ r − 1 , … , b ^ 1 \hat{z},\hat{b}_r,\hat{b}_{r-1},\ldots,\hat{b}_1 z ^ , b ^ r , b ^ r − 1 , … , b ^ 1 is an induced path: consecutive b b b -vertices are adjacent since e i = 1 e_i=1 e i = 1 , nonconsecutive ones lie in nonconsecutive fibres, and z ^ \hat{z} z ^ is adjacent to b ^ r \hat{b}_r b ^ r only. Its vertices have distinct indices, so it is an index-transversal ( r + 1 ) (r+1) ( r + 1 ) -arm. This contradicts the choice of L L L , so Q r + 1 Q_{r+1} Q r + 1 is ( r + 1 ) (r+1) ( r + 1 ) -forcing.
Since an h h h -arm together with v v v is an induced P h + 1 P_{h+1} P h + 1 in L L L , the graph Q h Q_h Q h is then as required. This proves Lemma 3.4. □
We are now ready to prove P s P_s P s is wonderful if EH ( P h ) \operatorname{EH}(P_h) EH ( P h ) .
Lemma 3.5. P s P_s P s is wonderful if EH ( P h ) \operatorname{EH}(P_h) EH ( P h ) .
Proof. Let Q h Q_h Q h be the graph given by Lemma 3.4 and let q h = ∣ Q h ∣ q_h=|Q_h| q h = ∣ Q h ∣ , c c c be the Erdős–Hajnal constant of Q h Q_h Q h . We claim that a = max { 2 q h , 2 + 5 / c , 6 } a=\max\{2q_h,2+5/c,6\} a = max { 2 q h , 2 + 5/ c , 6 } suffices. Let y ∈ ( 0 , 1 / 2 ) y\in(0,1/2) y ∈ ( 0 , 1/2 ) and G G G be P s ‾ \overline{P_s} P s -free. Let B = ( B 1 , … , B ℓ ) \mathcal{B}=(B_1,\ldots,B_\ell) B = ( B 1 , … , B ℓ ) be a ( ℓ , w ) (\ell,w) ( ℓ , w ) -blockade where ℓ \ell ℓ is an integer at least y − a y^{-a} y − a , each block of B \mathcal{B} B has the same size, and every two blocks are complete or y a y^a y a -sparse.
Let I ( v ) I(v) I ( v ) be the set of indices i ∈ [ ℓ ] i\in[\ell] i ∈ [ ℓ ] such that ∣ N ( v ) ∩ B i ∣ ∈ ( 0 , 1 2 ∣ B i ∣ ) |N(v)\cap B_i|\in(0,\frac{1}{2}|B_i|) ∣ N ( v ) ∩ B i ∣ ∈ ( 0 , 2 1 ∣ B i ∣ ) . If ∣ I ( v ) ∣ ≤ y ℓ |I(v)|\leq y\ell ∣ I ( v ) ∣ ≤ y ℓ for every vertex v ∈ V ( G ) ∖ V ( B ) v\in V(G)\setminus V(\mathcal{B}) v ∈ V ( G ) ∖ V ( B ) , then the second bullet of wonderfulness holds by double counting. So we may suppose that there exists v ∈ V ( G ) ∖ V ( B ) v\in V(G)\setminus V(\mathcal{B}) v ∈ V ( G ) ∖ V ( B ) with ∣ I ( v ) ∣ ≥ y ℓ |I(v)|\geq y\ell ∣ I ( v ) ∣ ≥ y ℓ . Without loss of generality, we may assume that I ( v ) = [ ∣ I ( v ) ∣ ] I(v)=[|I(v)|] I ( v ) = [ ∣ I ( v ) ∣ ] . Let J J J be the graph with V ( J ) = I ( v ) V(J)=I(v) V ( J ) = I ( v ) and i j ∈ E ( J ) ij\in E(J) ij ∈ E ( J ) if and only if B i B_i B i is complete to B j B_j B j .
Claim 3.5.1. The graph J J J is Q h ‾ \overline{Q_h} Q h -free. Consequently, J J J has a clique or a stable set of size at least ⌈ ∣ J ∣ c ⌉ \lceil|J|^c\rceil ⌈ ∣ J ∣ c ⌉ .
Proof of Claim 3.5.1. Let W W W be the common size of the blocks. For each i ∈ I ( v ) i\in I(v) i ∈ I ( v ) , choose b i ∈ N G ( v ) ∩ B i b_i\in N_G(v)\cap B_i b i ∈ N G ( v ) ∩ B i and let C i = B i ∖ N G ( v ) C_i=B_i\setminus N_G(v) C i = B i ∖ N G ( v ) . By the definition of I ( v ) I(v) I ( v ) , the vertex b i b_i b i exists and ∣ C i ∣ > W / 2 |C_i|>W/2 ∣ C i ∣ > W /2 .
Suppose that J [ I ′ ] ≅ Q h ‾ J[I']\cong\overline{Q_h} J [ I ′ ] ≅ Q h for some I ′ ⊆ I ( v ) I'\subseteq I(v) I ′ ⊆ I ( v ) . Identify the vertices of Q h Q_h Q h with the indices in I ′ I' I ′ so that, for distinct i , j ∈ I ′ i,j\in I' i , j ∈ I ′ , we have i j ∈ E ( Q h ) ij\in E(Q_h) ij ∈ E ( Q h ) if and only if i j ∉ E ( J ) ij\notin E(J) ij ∈ / E ( J ) . Thus, if i j ∈ E ( Q h ) ij\in E(Q_h) ij ∈ E ( Q h ) , then B i B_i B i and B j B_j B j are not complete to each other and hence are y a y^a y a -sparse to each other. If i j ∉ E ( Q h ) ij\notin E(Q_h) ij ∈ / E ( Q h ) , then B i B_i B i and B j B_j B j are complete to each other.
We choose vertices z i ∈ C i z_i\in C_i z i ∈ C i for i ∈ I ′ i\in I' i ∈ I ′ one at a time. When choosing z i z_i z i , exclude the neighbors in G G G of every b j b_j b j with j ∈ I ′ j\in I' j ∈ I ′ and i j ∈ E ( Q h ) ij\in E(Q_h) ij ∈ E ( Q h ) , and also the neighbors in G G G of every previously chosen z j z_j z j with i j ∈ E ( Q h ) ij\in E(Q_h) ij ∈ E ( Q h ) . Each such vertex has at most y a ⋅ W y^a\cdot W y a ⋅ W neighbors in B i B_i B i , since B j B_j B j
is y a y^a y a -sparse to B i B_i B i . There are at most 2 ( q h − 1 ) 2(q_h-1) 2 ( q h − 1 ) such vertices, so at most 2 ( q h − 1 ) y a ⋅ W 2(q_h-1)y^a\cdot W 2 ( q h − 1 ) y a ⋅ W vertices of C i C_i C i are excluded. Since y < 1 / 2 y<1/2 y < 1/2 and a ≥ 2 q h a\ge2q_h a ≥ 2 q h , we have y a < 2 − a ≤ 2 − 2 q h y^a<2^{-a}\le2^{-2q_h} y a < 2 − a ≤ 2 − 2 q h and hence 2 ( q h − 1 ) y a < 2 q h 2 − 2 q h ≤ 1 / 2 2(q_h-1)y^a<2q_h2^{-2q_h}\le1/2 2 ( q h − 1 ) y a < 2 q h 2 − 2 q h ≤ 1/2 . Thus fewer than W / 2 W/2 W /2 vertices are excluded, and the choice of z i z_i z i is possible because ∣ C i ∣ > W / 2 |C_i|>W/2 ∣ C i ∣ > W /2 .
Let L L L be the subgraph of G ‾ \overline{G} G induced by { v } ∪ { z i , b i : i ∈ I ′ } \{v\}\cup\{z_i,b_i:i\in I'\} { v } ∪ { z i , b i : i ∈ I ′ } . These vertices are distinct, since the blocks are pairwise disjoint, v v v lies outside the blockade, and z i ∉ N G ( v ) z_i\notin N_G(v) z i ∈ / N G ( v ) whereas b i ∈ N G ( v ) b_i\in N_G(v) b i ∈ N G ( v ) . We verify that L L L is a two-labeled lift of Q ‾ h \overline{Q}_h Q h . By construction, v v v is adjacent in L L L to every z i z_i z i and to no b i b_i b i . For each i j ∈ E ( Q h ) ij\in E(Q_h) ij ∈ E ( Q h ) , the choices of z i z_i z i and z j z_j z j ensure that z i z j z_iz_j z i z j , z i b j z_ib_j z i b j , and z j b i z_jb_i z j b i are edges of L L L . For distinct i , j ∈ I ′ i,j\in I' i , j ∈ I ′ with i j ∉ E ( Q h ) ij\notin E(Q_h) ij ∈ / E ( Q h ) , the blocks B i B_i B i and B j B_j B j are complete in G G G , so there are no edges of L L L between { z i , b i } \{z_i,b_i\} { z i , b i } and { z j , b j } \{z_j,b_j\} { z j , b j } . No further condition is required on the pairs z i b i z_ib_i z i b i , or on the pairs b i b j b_ib_j b i b j with i j ∈ E ( Q h ) ij\in E(Q_h) ij ∈ E ( Q h ) . Thus L L L satisfies the definition of a two-labeled lift. By Lemma 3.4, L L L contains an induced P s P_s P s , contrary to G G G being P ‾ s \overline{P}_s P s -free. Therefore J ‾ \overline{J} J is Q ‾ h \overline{Q}_h Q h -free.
It follows that J ‾ \overline{J} J is Q h Q_h Q h -free. By the choice of c c c , the graph J ‾ \overline{J} J , and hence also J J J , has a clique or a stable set of size at least ∣ J ∣ c |J|^c ∣ J ∣ c .
By Claim 3.5.1, J J J has a clique or a stable set R R R of size r = ⌈ ∣ J ∣ c ⌉ r=\lceil|J|^c\rceil r = ⌈ ∣ J ∣ c ⌉ . By taking complement if necessary, we may assume that R R R is a stable set. Let S = ⋃ i ∈ R B i S=\bigcup_{i\in R}B_i S = ⋃ i ∈ R B i . Since each block of B \mathcal{B} B has the same size, each vertex v ∈ B i ⊆ S v\in B_i\subseteq S v ∈ B i ⊆ S has at most r − 1 ∣ S ∣ r^{-1}|S| r − 1 ∣ S ∣ neighbors in B i B_i B i and at most y a ∣ S ∣ y^a|S| y a ∣ S ∣ neighbors in S ∖ B i S\setminus B_i S ∖ B i . Since
r − 1 + y a ≤ ( y ℓ ) − c + y a ( r ≥ ( y ℓ ) c ) ≤ y c ( a − 1 ) + y a ( ℓ ≥ y − a ) ≤ y 5 + y 5 ( a ≥ 5 c + 2 ≥ 6 ) ≤ y 4 , ( y < 1 / 2 ) \begin{aligned}
r^{-1}+y^a &\le(y\ell)^{-c}+y^a && (r\ge(y\ell)^c)\\
&\le y^{c(a-1)}+y^a && (\ell\ge y^{-a})\\
&\le y^5+y^5 && \left(a\ge\frac{5}{c}+2\ge6\right)\\
&\le y^4, && (y<1/2)
\end{aligned} r − 1 + y a ≤ ( y ℓ ) − c + y a ≤ y c ( a − 1 ) + y a ≤ y 5 + y 5 ≤ y 4 , ( r ≥ ( y ℓ ) c ) ( ℓ ≥ y − a ) ( a ≥ c 5 + 2 ≥ 6 ) ( y < 1/2 )
S S S is y 4 y^4 y 4 -restricted. This gives the first outcome of Lemma 3.5.
Reducing the Erdős–Hajnal property to the local alternative
This section turns a local statement about sparse graphs into the Erdős–Hajnal property, by the iterative sparsification method of [12 ] (see also [9 ] ).
Definition 4.1. Let C \mathcal{C} C be a hereditary class. We say C \mathcal{C} C has the local alternative with constant D ≥ 4 D\ge4 D ≥ 4 if for all 0 < x ≤ y ≤ 2 − D 0<x\le y\le2^{-D} 0 < x ≤ y ≤ 2 − D , every y 3 y^3 y 3 -sparse F ∈ C F\in\mathcal{C} F ∈ C with ∣ F ∣ ≥ x − D |F|\ge x^{-D} ∣ F ∣ ≥ x − D satisfies one of the following:
(O1) F F F is 2 y 4 2y^4 2 y 4 -sparse;
(O2) F F F has a weakly x x x -semisparse ( k , ∣ F ∣ / k D ) (k,|F|/k^D) ( k , ∣ F ∣/ k D ) -blockade for some integer k ∈ [ 1 / y , x − D ] k\in[1/y,x^{-D}] k ∈ [ 1/ y , x − D ] ;
(O3) there are disjoint X , Z ⊆ V ( F ) X,Z\subseteq V(F) X , Z ⊆ V ( F ) with ∣ X ∣ ≥ y D ∣ F ∣ |X|\ge y^D|F| ∣ X ∣ ≥ y D ∣ F ∣ and ∣ Z ∣ ≥ ( 1 − 4 y ) ∣ F ∣ |Z|\ge(1-4y)|F| ∣ Z ∣ ≥ ( 1 − 4 y ) ∣ F ∣ such that Z Z Z is x x x -sparse to X X X ;
(O4) for some z ∈ [ x D , y ] z\in[x^D,y] z ∈ [ x D , y ] the graph F F F has a z 4 z^4 z 4 -restricted set of at least z D ∣ F ∣ z^D|F| z D ∣ F ∣ vertices.
The main result of this section is the following.
Theorem 4.2. Let s ≥ 3 s \ge3 s ≥ 3 and assume EH(P s − 1 P_{s-1} P s − 1 ). Let C \mathcal{C} C be a hereditary class of P s ‾ \overline{P_s} P s -free graphs with the local alternative with constant D ≥ 4 D \ge4 D ≥ 4 . Then C \mathcal{C} C has the Erdős–Hajnal property.
Throughout this section, fix s s s , C \mathcal{C} C and D D D as in Theorem 4.2.
Put c 0 = 2 − 12 c_0=2^{-12} c 0 = 2 − 12 , y 0 = min ( c 0 4 / 2 , 1 / ( 60 s ) , 2 − D ) y_0=\min(c_0^4/2,1/(60s),2^{-D}) y 0 = min ( c 0 4 /2 , 1/ ( 60 s ) , 2 − D ) , λ = 6 ( D + 1 ) \lambda=6(D+1) λ = 6 ( D + 1 ) and D ∗ = 12 D 2 + 12 D + 3 D^*=12D^2+12D+3 D ∗ = 12 D 2 + 12 D + 3 . Note that c 0 < e − 8 c_0<e^{-8} c 0 < e − 8 and D ∗ = 2 D λ + 3 D^*=2D\lambda+3 D ∗ = 2 D λ + 3 .
We first derive weakly semisparse blockades from the local alternative.
Lemma 4.3 (Iterative sparsification). Let 0 < x < y 0 0<x<y_0 0 < x < y 0 . Every c 0 y 0 3 c_0y_0^3 c 0 y 0 3 -sparse G ∈ C G\in\mathcal{C} G ∈ C with n = ∣ G ∣ ≥ x − D ∗ n=|G|\ge x^{-D^*} n = ∣ G ∣ ≥ x − D ∗ has a weakly x x x -semisparse ( k , n / k D ∗ ) (k,n/k^{D^*}) ( k , n / k D ∗ ) -blockade for some integer k k k with 2 ≤ k ≤ x − ( 2 D + 1 ) 2\le k\le x^{-(2D+1)} 2 ≤ k ≤ x − ( 2 D + 1 ) .
Proof. Call y ∈ [ x 2 D , y 0 ] y\in[x^{2D},y_0] y ∈ [ x 2 D , y 0 ] admissible, if G G G has a c 0 y 3 c_0y^3 c 0 y 3 -sparse induced subgraph F F F with ∣ F ∣ ≥ y λ n |F|\ge y^\lambda n ∣ F ∣ ≥ y λ n . If y y y is admissible, we call the c 0 y 3 c_0y^3 c 0 y 3 -sparse induced subgraph F F F with ∣ F ∣ ≥ y λ n |F|\ge y^\lambda n ∣ F ∣ ≥ y λ n a witness for y y y . Every witness is an induced subgraph of the finite graph G G G . So there are at most 2 n 2^n 2 n candidate witnesses. For a fixed F F F , every y y y in
[ max { x 2 D , ( Δ ( F ) c 0 ∣ F ∣ ) 1 / 3 } , min { y 0 , ( ∣ F ∣ n ) 1 / λ } ] \left[\max\left\{x^{2D},\left(\frac{\Delta(F)}{c_0|F|}\right)^{1/3}\right\},\min\left\{y_0,\left(\frac{|F|}{n}\right)^{1/\lambda}\right\}\right] [ max { x 2 D , ( c 0 ∣ F ∣ Δ ( F ) ) 1/3 } , min { y 0 , ( n ∣ F ∣ ) 1/ λ } ]
is admissible for F F F . Since there are finitely many F F F , the admissible values form a finite union of closed intervals, hence a closed set, which contains y 0 y_0 y 0 . Let y y y be the smallest admissible value and F F F be its witness.
Suppose first that y ≥ x y\ge x y ≥ x . We build disjoint sets X 0 , X 1 , … X_0,X_1,\ldots X 0 , X 1 , … and a decreasing sequence F = F 0 ⊇ F 1 ⊇ ⋯ F=F_0\supseteq F_1\supseteq\cdots F = F 0 ⊇ F 1 ⊇ ⋯ with ∣ F j ∣ ≥ ( 1 − 4 y ) j ∣ F ∣ |F_j|\ge(1-4y)^j|F| ∣ F j ∣ ≥ ( 1 − 4 y ) j ∣ F ∣ , as long as j < K : = ⌈ 1 / y ⌉ j<K:=\lceil1/y\rceil j < K := ⌈ 1/ y ⌉ . Since j < 1 / y j<1/y j < 1/ y and 4 y ≤ 1 / 2 4y\le1/2 4 y ≤ 1/2 , ∣ F j ∣ ≥ ( 1 − 4 y ) j ∣ F ∣ ≥ e − 8 ∣ F ∣ > c 0 ∣ F ∣ |F_j|\ge(1-4y)^j|F|\ge e^{-8}|F|>c_0|F| ∣ F j ∣ ≥ ( 1 − 4 y ) j ∣ F ∣ ≥ e − 8 ∣ F ∣ > c 0 ∣ F ∣ . So F j F_j F j is y 3 y^3 y 3 -sparse and ∣ F j ∣ ≥ c 0 y λ n ≥ x λ + 1 n ≥ x − D |F_j|\ge c_0y^\lambda n\ge x^{\lambda+1}n\ge x^{-D} ∣ F j ∣ ≥ c 0 y λ n ≥ x λ + 1 n ≥ x − D , which satisfies the condition of Definition 4.1. Apply the local alternative to F j F_j F j .
If Definition 4.1 (O3) holds for F j F_j F j , then set X j = X X_j=X X j = X and F j + 1 = Z F_{j+1}=Z F j + 1 = Z . Since ∣ Z ∣ ≥ ( 1 − 4 y ) ∣ F j ∣ |Z|\ge(1-4y)|F_j| ∣ Z ∣ ≥ ( 1 − 4 y ) ∣ F j ∣ , the bound on ∣ F j + 1 ∣ |F_{j+1}| ∣ F j + 1 ∣ is maintained, and we continue. If this happens for all j < K j<K j < K , then ( X 0 , … , X K − 1 ) (X_0,\ldots,X_{K-1}) ( X 0 , … , X K − 1 ) is a blockade in which every later block is x x x -sparse to every earlier one. In particular it is weakly x x x -semisparse. Since c 0 ≥ y 2 c_0\ge y^2 c 0 ≥ y 2 and y ≥ 1 / K y\ge1/K y ≥ 1/ K , its width is at least c 0 y D + λ n ≥ y D + λ + 2 n ≥ n / K D ∗ c_0y^{D+\lambda}n\ge y^{D+\lambda+2}n\ge n/K^{D^*} c 0 y D + λ n ≥ y D + λ + 2 n ≥ n / K D ∗ and its length is K K K with 2 ≤ K ≤ 2 / x ≤ x − 2 2\le K\le2/x\le x^{-2} 2 ≤ K ≤ 2/ x ≤ x − 2 .
If Definition 4.1 (O1) holds for F j F_j F j , then since 2 y 4 ≤ c 0 4 y 3 2y^4\le c_0^4y^3 2 y 4 ≤ c 0 4 y 3 , F j F_j F j is c 0 ( c 0 y ) 3 c_0(c_0y)^3 c 0 ( c 0 y ) 3 -sparse and ∣ F j ∣ ≥ c 0 y λ n ≥ ( c 0 y ) λ n |F_j|\ge c_0y^\lambda n\ge(c_0y)^\lambda n ∣ F j ∣ ≥ c 0 y λ n ≥ ( c 0 y ) λ n . Since c 0 y ≥ c 0 x ≥ x 2 ≥ x 2 D c_0y\ge c_0x\ge x^2\ge x^{2D} c 0 y ≥ c 0 x ≥ x 2 ≥ x 2 D , the value c 0 y < y c_0y<y c 0 y < y is admissible, a contradiction.
If Definition 4.1 (O2) holds for F j F_j F j , then there is a weakly x x x -semisparse ( k , ∣ F j ∣ / k D ) (k,|F_j|/k^D) ( k , ∣ F j ∣/ k D ) -blockade for some integer k ∈ [ 1 / y , x − D ] k\in[1/y,x^{-D}] k ∈ [ 1/ y , x − D ] . Since c 0 ≥ y ≥ 1 / k c_0\ge y\ge1/k c 0 ≥ y ≥ 1/ k , its width is at least c 0 y λ n / k D ≥ n / k D + λ + 1 ≥ n / k D ∗ c_0y^\lambda n/k^D\ge n/k^{D+\lambda+1}\ge n/k^{D^*} c 0 y λ n / k D ≥ n / k D + λ + 1 ≥ n / k D ∗ .
If Definition 4.1 (O4) holds for F j F_j F j , then let T T T be the restricted set with ∣ T ∣ ≥ z D ∣ F j ∣ ≥ c 0 z λ + D n |T|\ge z^D|F_j|\ge c_0z^{\lambda+D}n ∣ T ∣ ≥ z D ∣ F j ∣ ≥ c 0 z λ + D n , where z ∈ [ x D , y ] z\in[x^D,y] z ∈ [ x D , y ] . If G [ T ] G[T] G [ T ] is z 4 z^{4} z 4 -sparse, put y ′ = z 7 / 6 y'=z^{7/6} y ′ = z 7/6 . Then since z ≤ c 0 2 z\le c_0^2 z ≤ c 0 2 and λ = 6 ( D + 1 ) \lambda=6(D+1) λ = 6 ( D + 1 ) , z 4 ≤ c 0 ( y ′ ) 3 z^4\le c_0(y')^3 z 4 ≤ c 0 ( y ′ ) 3 and ∣ T ∣ ≥ z λ + D n = ( y ′ ) λ n |T|\ge z^{\lambda+D}n=(y')^\lambda n ∣ T ∣ ≥ z λ + D n = ( y ′ ) λ n . Also x 2 D ≤ z 7 / 6 < y x^{2D}\le z^{7/6}<y x 2 D ≤ z 7/6 < y . So y ′ y' y ′ is admissible, contradicting minimality.
Thus, G ‾ [ T ] \overline{G}[T] G [ T ] is P s P_s P s -free and ( z 2 ) 2 (z^2)^2 ( z 2 ) 2 -sparse with z 2 ≤ 1 / ( 60 s ) z^2\le1/(60s) z 2 ≤ 1/ ( 60 s ) and z 4 ∣ T ∣ ≥ z λ + D + 5 n ≥ x D ( λ + D + 5 ) n ≥ x − 1 ≥ 2 z^4|T|\ge z^{\lambda+D+5}n\ge x^{D(\lambda+D+5)}n\ge x^{-1}\ge2 z 4 ∣ T ∣ ≥ z λ + D + 5 n ≥ x D ( λ + D + 5 ) n ≥ x − 1 ≥ 2 . By Theorem 2.2, there is an anticomplete blockade of G ‾ [ T ] \overline{G}[T] G [ T ] , that is, a complete blockade of G [ T ] G[T] G [ T ] , of length K ′ = ∣ z − 2 ∣ K'=|z^{-2}| K ′ = ∣ z − 2 ∣ and width at least ∣ z 4 ∣ T ∣ ∣ ≥ z 4 ∣ T ∣ / 2 ≥ z λ + D + 6 n ≥ n / ( K ′ ) ( λ + D + 6 ) / 2 ≥ n / ( K ′ ) D ∗ |z^4|T||\ge z^4|T|/2\ge z^{\lambda+D+6}n\ge n/(K')^{(\lambda+D+6)/2}\ge n/(K')^{D^*} ∣ z 4 ∣ T ∣∣ ≥ z 4 ∣ T ∣/2 ≥ z λ + D + 6 n ≥ n / ( K ′ ) ( λ + D + 6 ) /2 ≥ n / ( K ′ ) D ∗ with 2 ≤ K ′ ≤ 2 z − 2 ≤ x − ( 2 D + 1 ) 2\le K'\le2z^{-2}\le x^{-(2D+1)} 2 ≤ K ′ ≤ 2 z − 2 ≤ x − ( 2 D + 1 ) .
So we may assume that y < x y < x y < x . Since y ≥ x 2 D y \ge x^{2D} y ≥ x 2 D , ∣ F ∣ ≥ x 2 D λ n |F| \ge x^{2D}\lambda n ∣ F ∣ ≥ x 2 D λn and F F F has maximum degree at most c 0 x 3 ∣ F ∣ c_0x^3|F| c 0 x 3 ∣ F ∣ . Split F F F into K = ⌈ 1 / x ⌉ K = \lceil1/x\rceil K = ⌈ 1/ x ⌉ disjoint sets of size ⌊ ∣ F ∣ / K ⌋ ≥ x ∣ F ∣ / 4 \lfloor|F|/K\rfloor\ge x|F|/4 ⌊ ∣ F ∣/ K ⌋ ≥ x ∣ F ∣/4 . Every vertex has at most c 0 x 3 ∣ F ∣ ≤ x ⋅ x ∣ F ∣ / 4 c_0x^3|F| \le x \cdot x|F|/4 c 0 x 3 ∣ F ∣ ≤ x ⋅ x ∣ F ∣/4 neighbors in each set, so this is an x x x -semisparse blockade of width at least x 2 D λ + 3 n ≥ n / K D ∗ x^{2D\lambda+3}n \ge n/K^{D^*} x 2 D λ + 3 n ≥ n / K D ∗ .
As in [12 Lemma 5.5] and [9 Lemma 4.4] , we then use Rödl’s theorem to remove the sparsity hypothesis of Lemma 4.3.
Lemma 4.4. There is a constant D 0 ≥ 1 D_0 \ge1 D 0 ≥ 1 such that for every 0 < x < y 0 0 < x < y_0 0 < x < y 0 , every G ∈ C G \in\mathcal{C} G ∈ C with ∣ G ∣ ≥ x − D 0 |G| \ge x^{-D_0} ∣ G ∣ ≥ x − D 0 has a weakly x x x -semisparse ( k , ∣ G ∣ / k D 0 ) (k, |G|/k^{D_0}) ( k , ∣ G ∣/ k D 0 ) -blockade for some integer k k k with 2 ≤ k ≤ x − ( 2 D + 1 ) 2 \le k \le x^{-(2D+1)} 2 ≤ k ≤ x − ( 2 D + 1 ) .
Proof. Let δ \delta δ be given by Theorem 2.1 for H = P s ‾ H = \overline{P_s} H = P s and ε = c 0 y 0 3 \varepsilon= c_0y_0^3 ε = c 0 y 0 3 . Put L = ⌈ log 2 ( 1 / δ ) ⌉ L = \lceil\log_2(1/\delta)\rceil L = ⌈ log 2 ( 1/ δ )⌉ and D 0 = D ∗ + L + ⌈ log 2 ( 2 ( 60 s ) 2 ) ⌉ D_0 = D^* + L + \lceil\log_2(2(60s)^2)\rceil D 0 = D ∗ + L + ⌈ log 2 ( 2 ( 60 s ) 2 )⌉ . Let n = ∣ G ∣ ≥ x − D 0 n = |G| \ge x^{-D_0} n = ∣ G ∣ ≥ x − D 0 , and let F F F be an ε \varepsilon ε -restricted induced subgraph with ∣ F ∣ ≥ δ n ≥ x − D ∗ |F| \ge\delta n \ge x^{-D^*} ∣ F ∣ ≥ δ n ≥ x − D ∗ (as δ ≥ 2 − L ≥ x L \delta\ge2^{-L} \ge x^L δ ≥ 2 − L ≥ x L and D 0 ≥ D ∗ + L D_0 \ge D^* + L D 0 ≥ D ∗ + L ). If F F F is ε \varepsilon ε -sparse, Lemma 4.3 applies to F ∈ C F \in\mathcal{C} F ∈ C and gives a weakly x x x -semisparse blockade of F F F , hence of G G G , of some length k k k with 2 ≤ k ≤ x − ( 2 D + 1 ) 2 \le k \le x^{-(2D+1)} 2 ≤ k ≤ x − ( 2 D + 1 ) and width at least
∣ F ∣ / k D ∗ ≥ δ n / k D ∗ ≥ 2 − L n / k D ∗ ≥ n / k D ∗ + L ≥ n / k D 0 . |F|/k^{D^*} \ge\delta n/k^{D^*} \ge2^{-L}n/k^{D^*} \ge n/k^{D^*+L} \ge n/k^{D_0}. ∣ F ∣/ k D ∗ ≥ δ n / k D ∗ ≥ 2 − L n / k D ∗ ≥ n / k D ∗ + L ≥ n / k D 0 .
using δ ≥ 2 − L \delta\ge2^{-L} δ ≥ 2 − L and k ≥ 2 k \ge2 k ≥ 2 . So we may assume that G ‾ [ F ] \overline{G}[F] G [ F ] is ε \varepsilon ε -sparse. Then it is P s P_s P s -free and ( 60 s ) − 2 (60s)^{-2} ( 60 s ) − 2 -sparse since ε ≤ y 0 3 \varepsilon\le y_0^3 ε ≤ y 0 3 . Since ∣ F ∣ ≥ x − D ∗ ≥ ( 60 s ) 2 |F| \ge x^{-D^*} \ge(60s)^2 ∣ F ∣ ≥ x − D ∗ ≥ ( 60 s ) 2 , Theorem 2.2 with z = 1 / ( 60 s ) z = 1/(60s) z = 1/ ( 60 s ) gives two blocks forming a complete ( 2 , δ n / ( 2 ( 60 s ) 2 ) ) (2,\delta n/(2(60s)^2)) ( 2 , δ n / ( 2 ( 60 s ) 2 )) -blockade in G G G and δ / ( 2 ( 60 s ) 2 ) ≥ 2 − D 0 \delta/(2(60s)^2) \ge2^{-D_0} δ / ( 2 ( 60 s ) 2 ) ≥ 2 − D 0 .
Lemma 4.5 (Layout). Let D 0 , γ ≥ 1 D_0,\gamma\ge1 D 0 , γ ≥ 1 and x 0 > 0 x_0 > 0 x 0 > 0 and suppose that for every 0 < x < x 0 0 < x < x_0 0 < x < x 0 every G ∈ C G \in\mathcal{C} G ∈ C with ∣ G ∣ ≥ x − D 0 |G| \ge x^{-D_0} ∣ G ∣ ≥ x − D 0 has a weakly x x x -semisparse ( k , ∣ G ∣ / k D 0 ) (k, |G|/k^{D_0}) ( k , ∣ G ∣/ k D 0 ) -blockade for some integer k k k with 2 ≤ k ≤ x − γ 2 \le k \le x^{-\gamma} 2 ≤ k ≤ x − γ . Let q ≥ 8 D 0 + 8 q \ge8D_0 + 8 q ≥ 8 D 0 + 8 be an integer with 2 − q < x 0 2^{-q} < x_0 2 − q < x 0 . Then for every G ∈ C G \in\mathcal{C} G ∈ C and every 0 < ε < 1 2 0 < \varepsilon< \frac12 0 < ε < 2 1 , either
hom ( G ) ≥ ε ( q + 2 ) D 0 ∣ G ∣ \operatorname{hom}(G) \ge\varepsilon^{(q+2)D_0}|G| hom ( G ) ≥ ε ( q + 2 ) D 0 ∣ G ∣ ; or
G G G has a ( ⌈ 1 / ε ⌉ , ε ( γ q + 2 ) D 0 ∣ G ∣ ) (\lceil1/\varepsilon\rceil,\varepsilon^{(\gamma q+2)D_0}|G|) (⌈ 1/ ε ⌉ , ε ( γ q + 2 ) D 0 ∣ G ∣ ) -blockade whose blocks are pairwise complete or weakly ε 8 \varepsilon^8 ε 8 -sparse.
In particular C \mathcal{C} C is generalized nice.
Proof. Let n = ∣ G ∣ n = |G| n = ∣ G ∣ . If n < ε − ( q + 2 ) D 0 n < \varepsilon^{-(q+2)D_0} n < ε − ( q + 2 ) D 0 , then ε ( q + 2 ) D 0 ∣ G ∣ < 1 \varepsilon^{(q+2)D_0}|G| < 1 ε ( q + 2 ) D 0 ∣ G ∣ < 1 and so the first outcome holds. So we may assume n ≥ ε − ( q + 2 ) D 0 n \ge\varepsilon^{-(q+2)D_0} n ≥ ε − ( q + 2 ) D 0 . Put x = ε q x = \varepsilon^q x = ε q , ℓ = ⌈ 1 / ε ⌉ ≤ 2 / ε \ell= \lceil1/\varepsilon\rceil\le2/\varepsilon ℓ = ⌈ 1/ ε ⌉ ≤ 2/ ε and σ = ε 4 D 0 \sigma= \varepsilon^{4D_0} σ = ε 4 D 0 .
As in [12 ] , a layout is a family of disjoint nonempty sets A 1 , … , A p A_1,\ldots,A_p A 1 , … , A p together with a graph Π \Pi Π on [ p ] [p] [ p ] (the pattern ) such that A i A_i A i is complete to A j A_j A j whenever i j ∈ E ( Π ) ij \in E(\Pi) ij ∈ E ( Π ) . The pattern records the pairs of sets known to be complete. A pair of distinct vertices is undecided if both lie in the same A i A_i A i , and decided otherwise. In particular, a pair involving a vertex in no A i A_i A i is decided, so discarding vertices from the sets A i A_i A i never decreases the number of decided pairs. A decided pair is wrong if it is an edge of G G G between some A i A_i A i and A j A_j A j with i j ∉ E ( Π ) ij \notin E(\Pi) ij ∈ / E ( Π ) .
Choose a layout with the maximum number p p p of sets subject to
∣ A i ∣ ≥ σ n ( i ∈ [ p ] ) , ∑ i ∣ A i ∣ 1 / D 0 ≥ n 1 / D 0 , # w r o n g ≤ x ⋅ # d e c i d e d . |A_i| \ge\sigma n\ (i \in[p]), \qquad\sum_i |A_i|^{1/D_0} \ge n^{1/D_0}, \qquad\#\mathrm{wrong} \le x \cdot\#\mathrm{decided}. ∣ A i ∣ ≥ σ n ( i ∈ [ p ]) , i ∑ ∣ A i ∣ 1/ D 0 ≥ n 1/ D 0 , # wrong ≤ x ⋅ # decided .
Such a layout exists since the layout with the single set V ( G ) V(G) V ( G ) qualifies. If p ≥ ℓ p \ge\ell p ≥ ℓ , take ℓ \ell ℓ of the sets. For i j ∉ E ( Π ) ij \notin E(\Pi) ij ∈ / E ( Π ) , every edge between A i A_i A i and A j A_j A j is a wrong pair. So the pair ( A i , A j ) (A_i,A_j) ( A i , A j ) has at most x ⋅ # decided ≤ x n 2 / 2 x \cdot\#\text{decided} \le xn^2/2 x ⋅ # decided ≤ x n 2 /2 edges. Hence density is at most x / ( 2 σ 2 ) = ε q − 8 D 0 / 2 ≤ ε 8 x/(2\sigma^2)=\varepsilon^{q-8D_0}/2 \le\varepsilon^8 x / ( 2 σ 2 ) = ε q − 8 D 0 /2 ≤ ε 8 . If i j ∈ E ( Π ) ij \in E(\Pi) ij ∈ E ( Π ) , then A i A_i A i is complete to A j A_j A j . This gives the second outcome of Lemma 4.5 with width σ n \sigma n σ n .
So we may assume that p < ℓ p<\ell p < ℓ . Then since ∑ i ∣ A i ∣ 1 / D 0 ≥ n 1 / D 0 \sum_i |A_i|^{1/D_0} \ge n^{1/D_0} ∑ i ∣ A i ∣ 1/ D 0 ≥ n 1/ D 0 , some set A A A has ∣ A ∣ 1 / D 0 ≥ n 1 / D 0 / ℓ |A|^{1/D_0} \ge n^{1/D_0}/\ell ∣ A ∣ 1/ D 0 ≥ n 1/ D 0 / ℓ and so ∣ A ∣ ≥ ( ε / 2 ) D 0 n ≥ ε 2 D 0 n ≥ x − D 0 |A| \ge(\varepsilon/2)^{D_0}n \ge\varepsilon^{2D_0}n \ge x^{-D_0} ∣ A ∣ ≥ ( ε /2 ) D 0 n ≥ ε 2 D 0 n ≥ x − D 0 . By hypothesis G [ A ] G[A] G [ A ] has a weakly x x x -semisparse blockade ( A 1 ′ , … , A k ′ ) (A'_1,\ldots,A'_k) ( A 1 ′ , … , A k ′ ) with 2 ≤ k ≤ x − γ 2 \le k \le x^{-\gamma} 2 ≤ k ≤ x − γ and width at least ∣ A ∣ / k D 0 |A|/k^{D_0} ∣ A ∣/ k D 0 . If k ≥ ℓ k \ge\ell k ≥ ℓ , any ℓ \ell ℓ of its blocks give the second outcome of Lemma 4.5 since ∣ A ∣ / k D 0 ≥ ε 2 D 0 x γ D 0 n |A|/k^{D_0} \ge\varepsilon^{2D_0}x^{\gamma D_0}n ∣ A ∣/ k D 0 ≥ ε 2 D 0 x γ D 0 n and x ≤ ε 8 x \le\varepsilon^8 x ≤ ε 8 . So we may assume that k < ℓ k<\ell k < ℓ . Replace A A A by A 1 ′ , … , A k ′ A'_1,\ldots,A'_k A 1 ′ , … , A k ′ , joining A i ′ , A j ′ A'_i,A'_j A i ′ , A j ′ in the pattern when they are complete, and giving each A i ′ A'_i A i ′ the same pattern relations as A A A to the other sets. This is again a layout. Since k < ℓ ≤ 2 / ε k<\ell\le2/\varepsilon k < ℓ ≤ 2/ ε , each new set has at least ∣ A ∣ / k D 0 ≥ ε 2 D 0 ( ε / 2 ) D 0 n ≥ σ n |A|/k^{D_0} \ge\varepsilon^{2D_0}(\varepsilon/2)^{D_0}n \ge\sigma n ∣ A ∣/ k D 0 ≥ ε 2 D 0 ( ε /2 ) D 0 n ≥ σ n vertices and ∑ i ∣ A i ′ ∣ 1 / D 0 ≥ k ⋅ ( ∣ A ∣ / k D 0 ) 1 / D 0 = ∣ A ∣ 1 / D 0 \sum_i |A'_i|^{1/D_0} \ge k\cdot(|A|/k^{D_0})^{1/D_0}=|A|^{1/D_0} ∑ i ∣ A i ′ ∣ 1/ D 0 ≥ k ⋅ ( ∣ A ∣/ k D 0 ) 1/ D 0 = ∣ A ∣ 1/ D 0 . Old wrong pairs stay wrong or stop being wrong. New wrong pairs join two blocks A i ′ , A j ′ A'_i,A'_j A i ′ , A j ′ forming a weakly x x x -sparse pair, so there are at most x ∣ A i ′ ∣ ∣ A j ′ ∣ x|A'_i||A'_j| x ∣ A i ′ ∣∣ A j ′ ∣ of them, while all these pairs were undecided and are now decided. So the new layout satisfies the constraints and has more sets, a contradiction.
The two outcomes are the first two outcomes of Definition 2.7, with c 1 = ( γ q + 2 ) D 0 ≥ 3 c_1=(\gamma q+2)D_0 \ge3 c 1 = ( γ q + 2 ) D 0 ≥ 3 , c 2 = 8 c_2=8 c 2 = 8 , c 3 = ( q + 2 ) D 0 c_3=(q+2)D_0 c 3 = ( q + 2 ) D 0 and c 4 = 1 c_4=1 c 4 = 1 . In particular C \mathcal{C} C is generalized nice. □
Now we are ready to prove Theorem 4.2 .
Proof of Theorem 4.2. Let D 0 D_0 D 0 be given by Lemma 4.4 . Apply Lemma 4.5 with this D 0 D_0 D 0 , γ = 2 D + 1 \gamma=2D+1 γ = 2 D + 1 , x 0 = y 0 x_0=y_0 x 0 = y 0 and q = max ( ⌈ 8 D 0 + 8 ⌉ , ⌈ log 2 ( 1 / y 0 ) ⌉ + 1 ) q=\max(\lceil8D_0+8\rceil,\lceil\log_2(1/y_0)\rceil+1) q = max (⌈ 8 D 0 + 8 ⌉ , ⌈ log 2 ( 1/ y 0 )⌉ + 1 ) , which satisfies q ≥ 8 D 0 + 8 q\ge8D_0+8 q ≥ 8 D 0 + 8 and 2 − q < y 0 2^{-q}<y_0 2 − q < y 0 . So C \mathcal{C} C is generalized nice. Since EH ( P s − 1 , P s ) \operatorname{EH}(P_{s-1},P_s) EH ( P s − 1 , P s ) is leaf-reducible and wonderful by Lemma 3.5. Then, Theorem 2.9 with H = P s H=P_s H = P s shows that C \mathcal{C} C has the Erdős–Hajnal property. □
Rooted purification
This section contains our second new ingredient, a family of statements R r R_r R r (r ≥ 5 r \ge5 r ≥ 5 ) that replaces the purity argument of [12 ] for long paths.
Throughout this section, densities (sparse, complete, restricted, clean) are measured in G G G , while the forbidden induced paths live in G ‾ \overline{G} G . We write “G ‾ \overline{G} G -edge” and “induced path of G ‾ \overline{G} G ” whenever we mean the complement.
The statement
In what follows, U U U and Y Y Y are disjoint sets of vertices, and the vertices of U U U are called roots. For x > 0 x>0 x > 0 , a set S ⊆ Y S \subseteq Y S ⊆ Y is x x x -clean for U U U if every root is complete to S S S or has fewer than x ∣ S ∣ / 4 x|S|/4 x ∣ S ∣/4 neighbors in S . ( T h e f a c t o r $ 1 / 4 S. (The factor \$1/4 S . ( T h e f a c t or $1/4 is only for convenience in the cut tree below.)
Let u ∈ V ( G ) ∖ Y u \in V(G)\setminus Y u ∈ V ( G ) ∖ Y and r ≥ 2 r \ge2 r ≥ 2 . A rooted P r P_r P r from u u u into Y Y Y is an induced path of G ‾ \overline{G} G with r r r vertices, one of whose ends is u u u and whose other r − 1 r-1 r − 1 vertices lie in Y Y Y . We say that u u u sends no rooted P r P_r P r into Y Y Y if there is no such path. If u u u sends no rooted P r P_r P r into Y Y Y , then it sends no rooted P r P_r P r into any subset of Y Y Y , and no rooted P r ′ P_{r'} P r ′ into Y Y Y for any r ′ ≥ r r' \ge r r ′ ≥ r (an induced P r ′ P_{r'} P r ′ starting at u u u begins with an induced P r P_r P r starting at u u u ). The following observation is used many times.
Lemma 5.1 (Prefixing). Let r ≥ 3 r \ge3 r ≥ 3 and u ∉ Y u \notin Y u ∈ / Y send no rooted P r P_r P r into Y Y Y . Let Z ⊆ Y Z \subseteq Y Z ⊆ Y and p ∈ Y ∖ Z p \in Y \setminus Z p ∈ Y ∖ Z be such that u u u is complete to Z Z Z and nonadjacent to p p p . Then p p p sends no rooted P r − 1 P_{r-1} P r − 1 into Z Z Z .
Proof. In G ‾ \overline{G} G the vertex u u u is adjacent to p p p and to no vertex of Z Z Z . Thus, a rooted P r − 1 P_{r-1} P r − 1 from p p p into Z Z Z , together with u u u , would be a rooted P r P_r P r from u u u into Y Y Y . □
Definition 5.2. Let r ≥ 5 r \ge5 r ≥ 5 and let C \mathcal{C} C be a hereditary class. We say C \mathcal{C} C satisfies R r R_r R r with constant d ≥ 1 d \ge1 d ≥ 1 if the following holds for all x , y x,y x , y with 0 < x ≤ y ≤ 2 − d 0 < x \le y \le2^{-d} 0 < x ≤ y ≤ 2 − d . Let G ∈ C G \in\mathcal{C} G ∈ C and let U , Y ⊆ V ( G ) U,Y \subseteq V(G) U , Y ⊆ V ( G ) be disjoint with ∣ Y ∣ = n ≥ x − d |Y| = n \ge x^{-d} ∣ Y ∣ = n ≥ x − d , such that every root u ∈ U u \in U u ∈ U sends no rooted P r P_r P r into Y Y Y . Then
(R1) there is S ⊆ Y S \subseteq Y S ⊆ Y with ∣ S ∣ ≥ y d n |S| \ge y^d n ∣ S ∣ ≥ y d n that is x x x -clean for U U U ; or
(R2) for some z ∈ [ x d , y ] z \in[x^d,y] z ∈ [ x d , y ] there is a z 4 z^4 z 4 -restricted T ⊆ Y T \subseteq Y T ⊆ Y with ∣ T ∣ ≥ z d n |T| \ge z^d n ∣ T ∣ ≥ z d n ; or
(R3) for some integer K ∈ [ 1 / y , x − d ] K \in[1/y,x^{-d}] K ∈ [ 1/ y , x − d ] there is an x x x -semisparse ( K , n / K d ) (K,n/K^d) ( K , n / K d ) -blockade in G [ Y ] G[Y] G [ Y ] .
We say C \mathcal{C} C satisfies R r R_r R r if it does so with some constant d d d .
Increasing d d d weakens every outcome and strengthens every hypothesis, so a statement R r R_r R r with constant d d d also holds with every d ′ ≥ d d' \ge d d ′ ≥ d .
We also need the classes in which the “rooted condition” holds along a vertex ordering.
Definition 5.3. For r ≥ 2 r \ge2 r ≥ 2 and a hereditary class C \mathcal{C} C , let O r ( C ) \mathcal{O}_r(\mathcal{C}) O r ( C ) be the class of graphs G ∈ C G \in\mathcal{C} G ∈ C whose vertices can be ordered v 1 , … , v n v_1,\ldots,v_n v 1 , … , v n so that each vertex v i v_i v i sends no rooted P r P_r P r into { v i + 1 , … , v n } \{v_{i+1},\ldots,v_n\} { v i + 1 , … , v n } . This class is hereditary.
We are now ready to state the main results in this section.
Theorem 5.4. Every hereditary class satisfies R 5 R_5 R 5 with constant 2127.
Theorem 5.5. Let r ≥ 6 r \ge6 r ≥ 6 and let C \mathcal{C} C be a hereditary class. Suppose that C \mathcal{C} C satisfies R r − 1 R_{r-1} R r − 1 and R max ( r − 2 , 5 ) R_{\max(r-2,5)} R m a x ( r − 2 , 5 ) , and that O r − 1 ( C ) \mathcal{O}_{r-1}(\mathcal{C}) O r − 1 ( C ) has the Erdős–Hajnal property. Then C \mathcal{C} C satisfies R r R_r R r .
Rooted P 4 P_4 P 4 and modular decomposition
A module of a graph G G G (called a homogeneous set in [9 ] or geschlossen in [8 ] ) is a nonempty set M ⊆ V ( G ) M \subseteq V(G) M ⊆ V ( G ) such that every vertex outside M M M is complete or anticomplete to M M M . A module is strong if it is disjoint from or comparable (under inclusion) with every other module. A strong module is prime if it is connected and its complement is connected. We use the following standard facts on modular decomposition [8 ] .
Lemma 5.6. [8 ] The following hold for modules in G G G .
The strong modules form a tree T T T under inclusion, whose top node is V ( G ) V(G) V ( G ) and in which the children of each non-singleton node partition it.
Disjoint modules are complete or anticomplete to each other.
Let N N N be a nontrivial node of T T T . Then one of the following holds.
If G [ N ] G[N] G [ N ] is disconnected, then the children of N N N are the vertex sets of its components; or
if G ‾ [ N ] \overline{G}[N] G [ N ] is disconnected, then the children of N N N are the vertex sets of its anticonnected components; or
if N N N is prime, then every module of G G G properly contained in N N N lies in a single child of N N N .
Lemma 5.7. Let Y ⊆ V ( G ) Y \subseteq V(G) Y ⊆ V ( G ) and u ∉ Y u \notin Y u ∈ / Y . Then u u u sends no rooted P 4 P_4 P 4 into Y Y Y if and only if every anticonnected component of G [ N ( u ) ∩ Y ] G[N(u) \cap Y] G [ N ( u ) ∩ Y ] is a module of G [ Y ] G[Y] G [ Y ] .
Proof. Let C C C be (the vertex set of) an anticonnected component of G [ N ( u ) ∩ Y ] G[N(u) \cap Y] G [ N ( u ) ∩ Y ] , and suppose C C C is not a module of G [ Y ] G[Y] G [ Y ] , so some p ∈ Y ∖ C p \in Y \setminus C p ∈ Y ∖ C is mixed on C C C . Then p ∉ N ( u ) p \notin N(u) p ∈ / N ( u ) , since a vertex of N ( u ) ∩ Y N(u) \cap Y N ( u ) ∩ Y outside C C C is complete to C C C . As G ‾ [ C ] \overline{G}[C] G [ C ] is connected and p p p is mixed on C C C , there is a G ‾ \overline{G} G -edge q q ′ qq' q q ′ inside C C C with p p p nonadjacent to q q q and adjacent to q ′ q' q ′ in G G G . Then u p q q ′ upqq' u pq q ′ is an induced path of G ‾ \overline{G} G , a rooted P 4 P_4 P 4 from u u u into Y Y Y . Conversely, if u p q q ′ upqq' u pq q ′ is a rooted P 4 P_4 P 4 from u u u into Y Y Y , then q , q ′ ∈ N ( u ) q,q' \in N(u) q , q ′ ∈ N ( u ) lie in the same anticonnected component C C C of G [ N ( u ) ∩ Y ] G[N(u) \cap Y] G [ N ( u ) ∩ Y ] , and p p p is mixed on C C C . □
Lemma 5.8. Let 0 < ξ ≤ 2 − 30 0 < \xi\le2^{-30} 0 < ξ ≤ 2 − 30 , let m m m be an integer with 2 16 ≤ m ≤ 2 ξ − 1 / 2 2^{16} \le m \le2^{\xi^{-1/2}} 2 16 ≤ m ≤ 2 ξ − 1/2 , and let Y ⊆ V ( G ) Y \subseteq V(G) Y ⊆ V ( G ) with ∣ Y ∣ = n ≥ 16 ξ − 3 |Y| = n \ge16\xi^{-3} ∣ Y ∣ = n ≥ 16 ξ − 3 . Let U ⊆ V ( G ) ∖ Y U \subseteq V(G) \setminus Y U ⊆ V ( G ) ∖ Y be such that every root u ∈ U u \in U u ∈ U sends no rooted P 4 P_4 P 4 into Y Y Y . Then one of the following holds:
(M1) G [ Y ] G[Y] G [ Y ] has a pure ( K , n / K 4 ) (K,n/K^4) ( K , n / K 4 ) -blockade for some integer K ∈ [ m 1 / 4 , 1 / ξ ] K \in[m^{1/4},1/\xi] K ∈ [ m 1/4 , 1/ ξ ] ;
(M2) G [ Y ] G[Y] G [ Y ] has a pure ( K , n / ( 2 m ) ) (K,n/(2m)) ( K , n / ( 2 m )) -blockade for some integer K K K with ( 8 K ) 4 ≤ m 3 ≤ ( 9 K ) 4 (8K)^4 \le m^3 \le(9K)^4 ( 8 K ) 4 ≤ m 3 ≤ ( 9 K ) 4 ;
(M3) G [ Y ] G[Y] G [ Y ] has a complete or anticomplete ( ⌊ 1 / ξ ⌋ , ξ 2 n / m ) (\lfloor1/\xi\rfloor,\xi^2n/m) (⌊ 1/ ξ ⌋ , ξ 2 n / m ) -blockade;
(M4) G [ Y ] G[Y] G [ Y ] has a complete ( ⌊ 1 / ( ξ m ) ⌋ , ξ 3 n / 4 ) (\lfloor1/(\xi m) \rfloor,\xi^3n/4) (⌊ 1/ ( ξ m )⌋ , ξ 3 n /4 ) -blockade; or
(M5) there is S ⊆ Y S \subseteq Y S ⊆ Y with ∣ S ∣ ≥ n / m |S| \ge n/m ∣ S ∣ ≥ n / m that is ξ \xi ξ -clean for U U U .
Proof. Suppose to the contrary that none of the outcomes of Lemma 5.8 holds. Note that m 2 ξ ≤ 4 m^2\xi\le4 m 2 ξ ≤ 4 and ξ m ≤ 2 ξ 1 / 2 ≤ 2 − 9 \xi m \le2^{\xi^{1/2}} \le2^{-9} ξ m ≤ 2 ξ 1/2 ≤ 2 − 9 . Put ν = ξ 2 n / 4 \nu= \xi^2n/4 ν = ξ 2 n /4 , τ = n / m \tau= n/m τ = n / m , K 1 = ⌊ 1 / ξ ⌋ K_1 = \lfloor1/\xi\rfloor K 1 = ⌊ 1/ ξ ⌋ . Then ν ≥ 4 / ξ \nu\ge4/\xi ν ≥ 4/ ξ and ν ≤ ξ τ ≤ τ \nu\le\xi\tau\le\tau ν ≤ ξ τ ≤ τ .
Now we choose K 0 K_0 K 0 . Let K 0 K_0 K 0 be the least integer with K 0 4 ≥ m K_0^4 \ge m K 0 4 ≥ m , and put a = K 0 − 1 a = K_0 - 1 a = K 0 − 1 . Then a ≥ 15 a \ge15 a ≥ 15 and a 4 < m a^4 < m a 4 < m . Also K 0 ≤ K 1 K_0 \le K_1 K 0 ≤ K 1 : from a 4 < m a^4 < m a 4 < m and m 2 ξ ≤ 4 m^2\xi\le4 m 2 ξ ≤ 4 we get a 8 ξ < 4 a^8\xi< 4 a 8 ξ < 4 , hence 2 a ξ < 1 2a\xi< 1 2 a ξ < 1 and K 0 = a + 1 ≤ 2 a < 1 / ξ K_0 = a + 1 \le2a < 1/\xi K 0 = a + 1 ≤ 2 a < 1/ ξ .
By Lemma 5.6, the strong modules of Y Y Y form a tree under inclusion. Let L \mathcal{L} L be the set of strong modules of G [ Y ] G[Y] G [ Y ] with at least ν \nu ν vertices. It follows that L \mathcal{L} L contains Y Y Y . For X ∈ L X \in\mathcal{L} X ∈ L , call a child of X X X small if it is not in L \mathcal{L} L , and let the remainder S ( X ) S(X) S ( X ) be the union of the small children of X X X . Every vertex of Y Y Y lies in the remainder of its lowest ancestor in L \mathcal{L} L , so the remainders partition Y Y Y . For nested X ′ ⊂ X X' \subset X X ′ ⊂ X in L \mathcal{L} L , the remainder S ( X ) S(X) S ( X ) is disjoint from X ′ X' X ′ , and every vertex outside X ′ X' X ′ is complete or anticomplete to X ′ X' X ′ . By Lemma 5.7, for every u ∈ U u \in U u ∈ U , every anticonnected component of G [ N ( u ) ∩ Y ] G[N(u) \cap Y] G [ N ( u ) ∩ Y ] is a module of G [ Y ] G[Y] G [ Y ] .
Claim 5.8.1. Let F \mathcal{F} F be a family of disjoint subsets of Y Y Y , each of size at most τ \tau τ . If for every integer K ∈ [ K 0 , K 1 ] K \in[K_0,K_1] K ∈ [ K 0 , K 1 ] , fewer than K K K members of F \mathcal{F} F have size at least n / K 4 n/K^4 n / K 4 , then
∑ A ∈ F ∣ A ∣ ≤ ( K 0 − 1 ) τ + n K 0 − 1 + ∣ F ∣ n K 1 4 . \sum_{A\in\mathcal{F}} |A| \le(K_0-1)\tau+ \frac{n}{K_0-1} + \frac{|\mathcal{F}|n}{K_1^4}. A ∈ F ∑ ∣ A ∣ ≤ ( K 0 − 1 ) τ + K 0 − 1 n + K 1 4 ∣ F ∣ n .
Proof of Claim 5.8.1. We split F \mathcal{F} F by size. By the counting condition for K 0 K_0 K 0 , fewer than K 0 K_0 K 0 members have size at least n / K 0 4 n/K_0^4 n / K 0 4 , contributing at most ( K 0 − 1 ) τ (K_0-1)\tau ( K 0 − 1 ) τ . For K 0 ≤ K < K 1 K_0 \le K < K_1 K 0 ≤ K < K 1 , the counting condition for K + 1 K+1 K + 1 (≤ K 1 \le K_1 ≤ K 1 ) says that fewer than K + 1 K+1 K + 1 members have size at least n / ( K + 1 ) 4 n/(K+1)^4 n / ( K + 1 ) 4 . So at most K K K members have size in [ n / ( K + 1 ) 4 , n / K 4 ) [n/(K+1)^4,n/K^4) [ n / ( K + 1 ) 4 , n / K 4 ) , and they contribute at most K n / K 4 = n / K 3 Kn/K^4=n/K^3 K n / K 4 = n / K 3 . Summing over K K K and using K − 3 ≤ 1 K ( K − 1 ) = 1 K − 1 − 1 K K^{-3} \le\frac{1}{K(K-1)}=\frac{1}{K-1}-\frac{1}{K} K − 3 ≤ K ( K − 1 ) 1 = K − 1 1 − K 1 , these members contribute at most n ∑ K ≥ K 0 ( 1 K − 1 − 1 K ) = n K 0 − 1 n\sum_{K\ge K_0}\left(\frac{1}{K-1}-\frac{1}{K}\right)=\frac{n}{K_0-1} n ∑ K ≥ K 0 ( K − 1 1 − K 1 ) = K 0 − 1 n . The remaining members have size less than n / K 1 4 n/K_1^4 n / K 1 4 , and there are at most ∣ F ∣ |\mathcal{F}| ∣ F ∣ of them. ■
Call a strong module of Y Y Y heavy if it has at least τ \tau τ vertices. Since τ ≥ ν \tau\ge\nu τ ≥ ν , a heavy strong module is also an element of L \mathcal{L} L . A heavy node is minimal if every child of it is not heavy. Minimal heavy nodes are disjoint modules, hence pairwise complete or anticomplete. If there are at least K 0 K_0 K 0 of them we obtain Lemma 5.8 (M1) with K = K 0 K=K_0 K = K 0 , since τ = n / m ≥ n / K 0 4 \tau=n/m\ge n/K_0^4 τ = n / m ≥ n / K 0 4 . So we may assume that there are at most a a a minimal heavy nodes.
Similarly, we call a non-heavy node of L \mathcal{L} L maximal if its parent node is heavy. The maximal non-heavy nodes are disjoint, have sizes in [ ν , τ ) [\nu,\tau) [ ν , τ ) , and number at most n / ν n/\nu n / ν . If for some K ∈ [ K 0 , K 1 ] K \in[K_0,K_1] K ∈ [ K 0 , K 1 ] at least K K K of them have size at least n / K 4 n/K^4 n / K 4 , we obtain Lemma 5.8 (M1). The set of maximal non-heavy nodes satisfies the condition of Claim 5.8.1, which gives their total size by
a n / m + n / a + ( n / ν ) n / K 1 4 ≤ n / a 3 + n / 15 + 64 ξ 2 n ≤ n / 4 ; an/m+n/a+(n/\nu)n/K_1^4 \le n/a^3+n/15+64\xi^2n \le n/4; an / m + n / a + ( n / ν ) n / K 1 4 ≤ n / a 3 + n /15 + 64 ξ 2 n ≤ n /4 ;
here a n / m ≤ n / a 3 an/m\le n/a^3 an / m ≤ n / a 3 as a 4 < m a^4<m a 4 < m , a ≥ 15 a\ge15 a ≥ 15 , and ( n / ν ) n / K 1 4 ≤ ( 4 / ξ 2 ) ( 2 ξ ) 4 n (n/\nu)n/K_1^4\le(4/\xi^2)(2\xi)^4n ( n / ν ) n / K 1 4 ≤ ( 4/ ξ 2 ) ( 2 ξ ) 4 n as K 1 ≥ 1 / ( 2 ξ ) K_1\ge1/(2\xi) K 1 ≥ 1/ ( 2 ξ ) . All remainders of non-heavy nodes lie in maximal non-heavy nodes, so the remainders of heavy nodes have total size at least 3 n / 4 3n/4 3 n /4 . Every heavy node contains a minimal heavy node, and the heavy nodes containing a fixed minimal heavy node form a chain. Hence some chain K \mathcal{K} K of heavy nodes has total remainder size at least 3 n / ( 4 a ) 3n/(4a) 3 n / ( 4 a ) .
Claim 5.8.2. For every X ∈ K X \in\mathcal{K} X ∈ K , ∣ S ( X ) ∣ < τ |S(X)|<\tau ∣ S ( X ) ∣ < τ .
Proof of Claim 5.8.2. Suppose to the contrary that some X ∈ K X \in\mathcal{K} X ∈ K has ∣ S ( X ) ∣ ≥ τ |S(X)|\ge\tau ∣ S ( X ) ∣ ≥ τ , and let S = S ( X ) S=S(X) S = S ( X ) . If G [ X ] G[X] G [ X ] is disconnected, then by Lemma 5.6 , the components of G [ S ] G[S] G [ S ] are small children of X X X , each with fewer than ν ≤ ξ ∣ S ∣ ≤ ∣ S ∣ / K 1 \nu\le\xi|S|\le|S|/K_1 ν ≤ ξ ∣ S ∣ ≤ ∣ S ∣/ K 1 vertices. Applying Lemma 2.3 to G [ S ] G[S] G [ S ] gives an anticomplete ( K 1 , ∣ S ∣ / K 1 2 ) (K_1,|S|/K_1^2) ( K 1 , ∣ S ∣/ K 1 2 ) -blockade in G [ S ] G[S] G [ S ] . Since ∣ S ∣ / K 1 2 ≥ ξ 2 n / m |S|/K_1^2\ge\xi^2n/m ∣ S ∣/ K 1 2 ≥ ξ 2 n / m , this gives outcome (M3) of Lemma 5.8 , a contradiction. If G ‾ [ X ] \overline{G}[X] G [ X ] is disconnected we obtain a complete blockade in the same way. So we may assume that X X X is prime. Let K ′ = 1 / ( ξ m ) ≥ 2 K'=1/(\xi m)\ge2 K ′ = 1/ ( ξ m ) ≥ 2 . If S S S is ξ \xi ξ -clean for U U U , then ∣ S ∣ ≥ τ = n / m |S|\ge\tau=n/m ∣ S ∣ ≥ τ = n / m gives Lemma 5.8 (M5), a contradiction. So we may assume that some u ∈ U u\in U u ∈ U is not complete to S S S but has q ≥ ξ ∣ S ∣ / 4 q\ge\xi|S|/4 q ≥ ξ ∣ S ∣/4 neighbors in S S S . Let A A A be an anticomnected component of G [ N ( u ) ∩ Y ] G[N(u)\cap Y] G [ N ( u ) ∩ Y ] that meets S S S . By Lemma 5.7 , A A A is a module. Since X X X is strong, A ⊇ X A\supseteq X A ⊇ X or A ⊆ X A\subseteq X A ⊆ X . The former would make u u u complete to S S S . So A ⊂ X A\subset X A ⊂ X , hence A A A lies in one child of X X X . This child meets S S S , so it is small, and A ⊆ S A\subseteq S A ⊆ S with ∣ A ∣ < ν |A|<\nu ∣ A ∣ < ν by Lemma 5.6 . Consequently N ( u ) ∩ S N(u)\cap S N ( u ) ∩ S is the union of the anticomnected components of G [ N ( u ) ∩ Y ] G[N(u)\cap Y] G [ N ( u ) ∩ Y ] that meet S S S , and these are exactly the anticomnected components of G [ N ( u ) ∩ S ] G[N(u)\cap S] G [ N ( u ) ∩ S ] , each with fewer than ν ≤ q / K ′ \nu\le q/K' ν ≤ q / K ′ vertices (as q ξ m ≥ ξ 2 τ m / 4 = ν q\xi m\ge\xi^2\tau m/4=\nu q ξ m ≥ ξ 2 τ m /4 = ν ). Lemma 2.3 gives a complete ( K ′ , q / K ′ 2 ) (K',q/K'^2) ( K ′ , q / K ′2 ) -blockade with q / K ′ 2 ≥ ξ τ ( ξ m ) 2 / 4 ≥ ξ 3 n / 4 q/K'^2\ge\xi\tau(\xi m)^2/4\ge\xi^3n/4 q / K ′2 ≥ ξ τ ( ξ m ) 2 /4 ≥ ξ 3 n /4 , which is Lemma 5.8 (M4), a contradiction. ■
By Claim 5.8.2 , ∣ S ( X ) ∣ < τ |S(X)| < \tau ∣ S ( X ) ∣ < τ for all X ∈ K X \in\mathcal{K} X ∈ K . Let K K K be the largest integer with ( 8 K ) 4 ≤ m 3 (8K)^4 \le m^3 ( 8 K ) 4 ≤ m 3 . Then K ≥ 8 K \ge8 K ≥ 8 and m 3 ≤ ( 9 K ) 4 m^3 \le(9K)^4 m 3 ≤ ( 9 K ) 4 . Since ( 8 K a ) 4 ≤ m 3 a 4 < m 4 (8Ka)^4 \le m^3a^4 < m^4 ( 8 K a ) 4 ≤ m 3 a 4 < m 4 , we have 8 K a < m 8Ka < m 8 K a < m and hence 2 K τ < n / ( 4 a ) < 3 n / ( 4 a ) 2K\tau< n/(4a) < 3n/(4a) 2 K τ < n / ( 4 a ) < 3 n / ( 4 a ) . Since ∣ S ( X ) ∣ < τ |S(X)| < \tau ∣ S ( X ) ∣ < τ for all X ∈ K X \in\mathcal{K} X ∈ K , we could combine all S ( X ) S(X) S ( X ) into a blockade ( Γ 1 , Γ 2 , … , Γ K ) (\Gamma_1,\Gamma_2,\ldots,\Gamma_K) ( Γ 1 , Γ 2 , … , Γ K ) such that
for each i ≤ K − 1 i \le K-1 i ≤ K − 1 , τ < ∣ Γ i ∣ < 2 τ \tau< |\Gamma_i| < 2\tau τ < ∣ Γ i ∣ < 2 τ ;
for each X ∈ K X \in\mathcal{K} X ∈ K , S ( X ) ⊆ Γ i S(X) \subseteq\Gamma_i S ( X ) ⊆ Γ i for some i ∈ [ K ] i \in[K] i ∈ [ K ] ;
for every pair X 1 , X 2 ∈ K X_1,X_2 \in\mathcal{K} X 1 , X 2 ∈ K with X 1 ⊇ X 2 X_1 \supseteq X_2 X 1 ⊇ X 2 such that S ( X 1 ) ⊆ Γ i S(X_1) \subseteq\Gamma_i S ( X 1 ) ⊆ Γ i and S ( X 2 ) ⊆ Γ j S(X_2) \subseteq\Gamma_j S ( X 2 ) ⊆ Γ j , i ≤ j i \le j i ≤ j .
Since 2 K τ < 3 n / ( 4 a ) 2K\tau< 3n/(4a) 2 K τ < 3 n / ( 4 a ) and ∣ Γ i ∣ < 2 τ |\Gamma_i| < 2\tau ∣ Γ i ∣ < 2 τ for every i ≤ K − 1 i \le K-1 i ≤ K − 1 , ∣ Γ K ∣ > τ |\Gamma_K| > \tau ∣ Γ K ∣ > τ . For every i ≤ K − 1 i \le K-1 i ≤ K − 1 , ⋃ i < j ≤ K Γ j \bigcup_{i<j\le K}\Gamma_j ⋃ i < j ≤ K Γ j is contained in a module S S S such that S ∩ Γ i = ∅ S \cap\Gamma_i = \varnothing S ∩ Γ i = ∅ . So every vertex in Γ i \Gamma_i Γ i is complete or anticomplete to ⋃ i < j ≤ K Γ j \bigcup_{i<j\le K}\Gamma_j ⋃ i < j ≤ K Γ j . By keeping the majority kind in each Γ i \Gamma_i Γ i for i ≤ K − 1 i \le K-1 i ≤ K − 1 , the resulting sets have at least τ / 2 = n / ( 2 m ) \tau/2 = n/(2m) τ /2 = n / ( 2 m ) vertices and form a pure blockade of length K K K , which gives Lemma 5.8 (M2).
This completes the proof of Lemma 5.8 . □
A sampling lemma
For a graph G G G with a partition B = ( B 1 , B 2 , … , B n ) \mathcal{B} = (B_1,B_2,\ldots,B_n) B = ( B 1 , B 2 , … , B n ) where each B i B_i B i is nonempty, we call B i B_i B i a layer of G G G .
Lemma 5.9. Let 0 < κ ≤ 1 0 < \kappa\le1 0 < κ ≤ 1 and g = max ( 2 , 1 / κ ) g = \max(2,1/\kappa) g = max ( 2 , 1/ κ ) . Let G G G be a graph whose vertex set has size M M M and is partitioned into B = ( B 1 , B 2 , … , B n ) \mathcal{B} = (B_1,B_2,\ldots,B_n) B = ( B 1 , B 2 , … , B n ) such that for every integer j j j and every set S S S of size j j j , if ∣ S ∩ B i ∣ ≤ 1 |S \cap B_i| \le1 ∣ S ∩ B i ∣ ≤ 1 for every i ∈ [ n ] i \in[n] i ∈ [ n ] , then G [ S ] G[S] G [ S ] has a clique or stable set of size at least j κ j^\kappa j κ . If
0 < ε ≤ 2 − 4 ( g + 10 ) and φ : = max { ∣ B i ∣ } M ≤ ε 4 g + 4 , 0 < \varepsilon\le2^{-4(g+10)} \quad\text{and}\quad\varphi:= \frac{\max\{|B_i|\}}{M} \le\varepsilon^{4g+4}, 0 < ε ≤ 2 − 4 ( g + 10 ) and φ := M max { ∣ B i ∣ } ≤ ε 4 g + 4 , then G G G has an ε \varepsilon ε -restricted set of at least ε 2 g + 2 M \varepsilon^{2g+2}M ε 2 g + 2 M vertices.
Proof. Suppose to the contrary that Lemma 5.9 does not hold. Put
q = ⌈ ε − 2 ⌉ , k = ⌈ q g ⌉ , δ = q 512 k , L = ln ( 1 / ε ) , ℓ = ⌈ ε − 1 ln ( 1 / δ ) ⌉ . q = \lceil\varepsilon^{-2}\rceil,\quad k = \lceil q^g\rceil,\quad\delta= \frac{q}{512k},\quad L = \ln(1/\varepsilon),\quad\ell= \lceil\varepsilon^{-1}\ln(1/\delta)\rceil. q = ⌈ ε − 2 ⌉ , k = ⌈ q g ⌉ , δ = 512 k q , L = ln ( 1/ ε ) , ℓ = ⌈ ε − 1 ln ( 1/ δ )⌉ .
Since q ≤ 2 ε − 2 q \le2\varepsilon^{-2} q ≤ 2 ε − 2 and k ≤ 2 g + 1 ε − 2 g k \le2^{g+1}\varepsilon^{-2g} k ≤ 2 g + 1 ε − 2 g , we have 32 k 2 φ ≤ 2 2 g + 7 ε 4 ≤ 1 32k^2\varphi\le2^{2g+7}\varepsilon^4 \le1 32 k 2 φ ≤ 2 2 g + 7 ε 4 ≤ 1 . Since each B i B_i B i is nonempty, φ ≥ 1 / M \varphi\ge1/M φ ≥ 1/ M , and so M ≥ 32 k 2 M \ge32k^2 M ≥ 32 k 2 and δ M ≥ 1 \delta M \ge1 δ M ≥ 1 .
Claim 5.9.1. By taking complement of G G G if necessary, there are at least 1 4 ( M / ( 2 k ) ) q \frac{1}{4}(M/(2k))^q 4 1 ( M / ( 2 k ) ) q stable sets of size q q q .
Proof of Claim 5.9.1. Choose a set X X X of 2 k 2k 2 k distinct vertices uniformly at random. The expected number of pairs of X X X inside one layer is at most ( 2 k 2 ) φ ≤ 2 k 2 φ ≤ 1 / 16 \binom{2k}{2}\varphi\le2k^2\varphi\le1/16 ( 2 2 k ) φ ≤ 2 k 2 φ ≤ 1/16 , so by Markov’s inequality, with probability at least 15 / 16 15/16 15/16 no two vertices of X X X lie in one layer. Then any k k k vertices of X X X lie in distinct layers, and so contain a clique or stable set of size k κ ≥ q k^\kappa\ge q k κ ≥ q . So at least half of the ( M 2 k ) \binom{M}{2k} ( 2 k M ) sets X X X contain a clique or stable set of size q q q . A fixed q q q -set lies in exactly ( M − q 2 k − q ) \binom{M-q}{2k-q} ( 2 k − q M − q ) sets X X X , so the number of q q q -sets that are cliques or stable sets is at least
1 2 ( M 2 k ) / ( M − q 2 k − q ) = 1 2 ( M q ) / ( 2 k q ) ≥ 1 2 ( M 2 k ) q , \frac{1}{2}\binom{M}{2k}\bigg/\binom{M-q}{2k-q}
= \frac{1}{2}\binom{M}{q}\bigg/\binom{2k}{q}
\ge\frac{1}{2}\binom{M}{2k}^{q}, 2 1 ( 2 k M ) / ( 2 k − q M − q ) = 2 1 ( q M ) / ( q 2 k ) ≥ 2 1 ( 2 k M ) q ,
where the identity is ( M 2 k ) ( 2 k q ) = ( M q ) ( M − q 2 k − q ) \binom{M}{2k}\binom{2k}{q}=\binom{M}{q}\binom{M-q}{2k-q} ( 2 k M ) ( q 2 k ) = ( q M ) ( 2 k − q M − q ) and the inequality holds termwise in ( M q ) / ( 2 k q ) = ∏ i < q M − i 2 k − i \binom{M}{q}/\binom{2k}{q}=\prod_{i<q}\frac{M-i}{2k-i} ( q M ) / ( q 2 k ) = ∏ i < q 2 k − i M − i . By taking complement of G G G if necessary, at least 1 4 ( M / ( 2 k ) ) q \frac{1}{4}(M/(2k))^q 4 1 ( M / ( 2 k ) ) q of them are stable sets. This proves Claim 5.9.1 .
Claim 5.9.2. If ℓ ≤ q \ell\le q ℓ ≤ q , then the number I q I_q I q of stable q q q -sets satisfies I q ≤ ( M ℓ ) ( N 0 q − ℓ ) I_q\le\binom{M}{\ell}\binom{N_0}{q-\ell} I q ≤ ( ℓ M ) ( q − ℓ N 0 ) , where N 0 = ⌈ δ M ⌉ ≤ 2 δ M N_0=\lceil\delta M\rceil\le2\delta M N 0 = ⌈ δ M ⌉ ≤ 2 δ M .
Proof of Claim 5.9.2. Note that no set of at least δ M \delta M δ M vertices is ε \varepsilon ε -sparse in G G G since δ = q / ( 512 k ) ≥ 2 − ( g + 9 ) ε 2 g − 2 ≥ ε 2 g + 2 \delta=q/(512k)\ge2^{-(g+9)}\varepsilon^{2g-2}\ge\varepsilon^{2g+2} δ = q / ( 512 k ) ≥ 2 − ( g + 9 ) ε 2 g − 2 ≥ ε 2 g + 2 , where the last inequality follows from ε 4 ≤ 2 − 16 ( g + 10 ) ≤ 2 − ( g + 9 ) \varepsilon^4\le2^{-16(g+10)}\le2^{-(g+9)} ε 4 ≤ 2 − 16 ( g + 10 ) ≤ 2 − ( g + 9 ) . Fix a linear order of V ( G ) V(G) V ( G ) and a stable q q q -set I I I . Run the following procedure. Start with X = V ( G ) X=V(G) X = V ( G ) and W = ∅ W=\varnothing W = ∅ . While ∣ X ∣ > N 0 |X|>N_0 ∣ X ∣ > N 0 , let p p p be the first vertex of maximum degree in G [ X ] G[X] G [ X ] . If p ∉ I p\notin I p ∈ / I , then delete p p p from X X X while if p ∈ I p\in I p ∈ I , put p p p into W W W and delete p p p and all its neighbors from X X X . Note that a vertex v v v of I I I is deleted if and only if v ∈ W v\in W v ∈ W . So, in the end, I = W ∪ ( I ∩ X ) I=W\cup(I\cap X) I = W ∪ ( I ∩ X ) , where X X X has at most N 0 N_0 N 0 vertices. Since G [ X ] G[X] G [ X ] is not ε \varepsilon ε -sparse while ∣ X ∣ > N 0 |X|>N_0 ∣ X ∣ > N 0 , each step when p ∈ I p\in I p ∈ I , we delete more than ε ∣ X ∣ \varepsilon|X| ε ∣ X ∣ vertices. Since ( 1 − ε ) ℓ M ≤ δ M (1-\varepsilon)^\ell M\le\delta M ( 1 − ε ) ℓ M ≤ δ M , at most ℓ \ell ℓ vertices of I I I are put into W W W . Given W W W , we can rerun the procedure without knowing I I I , since at each step, p ∈ I p\in I p ∈ I if and only if p ∈ W p\in W p ∈ W . So W W W determines the final X X X . Pad W W W to exactly ℓ \ell ℓ vertices by adding vertices of I ∩ X I\cap X I ∩ X . The added vertices lie in the final X X X , so they are never chosen as p p p , hence rerunning the procedure with the padded set in place of W W W gives the same run and the same final X X X . Then I I I is determined by an ℓ \ell ℓ -subset of V ( G ) V(G) V ( G ) together with a ( q − ℓ ) (q-\ell) ( q − ℓ ) -subset of X X X . This proves Claim 5.9.2.
Put Λ = ln ( 1 / δ ) \Lambda=\ln(1/\delta) Λ = ln ( 1/ δ ) and Λ ′ = ln ( 1 / ( 2 δ ) ) \Lambda'=\ln(1/(2\delta)) Λ ′ = ln ( 1/ ( 2 δ )) . Since δ = q / ( 512 k ) \delta=q/(512k) δ = q / ( 512 k ) , k ≤ 2 q g k\le2q^g k ≤ 2 q g , and q ≤ 2 ε − 2 q\le2\varepsilon^{-2} q ≤ 2 ε − 2 , we have Λ ≤ ( g + 9 ) ln 2 + 2 ( g − 1 ) L ≤ 2 g L \Lambda\le(g+9)\ln2+2(g-1)L\le2gL Λ ≤ ( g + 9 ) ln 2 + 2 ( g − 1 ) L ≤ 2 g L , where the last inequality follows from L ≥ 4 ( g + 10 ) ln 2 L\ge4(g+10)\ln2 L ≥ 4 ( g + 10 ) ln 2 .
We first show that ℓ < q \ell<q ℓ < q and ( ℓ / q ) Λ ′ < 1 (\ell/q)\Lambda'<1 ( ℓ / q ) Λ ′ < 1 . Since g ≥ 2 g\ge2 g ≥ 2 and L ≥ 4 ( g + 10 ) ln 2 L\ge4(g+10)\ln2 L ≥ 4 ( g + 10 ) ln 2 , we have L > 24 L>24 L > 24 and 2 g < L 2g<L 2 g < L . Using ℓ / q ≤ ε Λ + ε 2 \ell/q\le\varepsilon\Lambda+\varepsilon^2 ℓ / q ≤ ε Λ + ε 2 and ε = e − L \varepsilon=e^{-L} ε = e − L , we obtain
2 g L ℓ q ≤ 4 g 2 ε L 2 + 2 g ε 2 L ≤ 2 L 4 e − L < 2 ⋅ 24 4 e − 24 < 1 , 2gL\frac{\ell}{q}\le4g^2\varepsilon L^2+2g\varepsilon^2L\le2L^4e^{-L}<2\cdot24^4e^{-24}<1, 2 g L q ℓ ≤ 4 g 2 ε L 2 + 2 g ε 2 L ≤ 2 L 4 e − L < 2 ⋅ 2 4 4 e − 24 < 1 ,
where we used that t 4 e − t t^4e^{-t} t 4 e − t is decreasing for t ≥ 24 t\ge24 t ≥ 24 . As 2 g L > 1 2gL>1 2 g L > 1 and Λ ′ ≤ 2 g L \Lambda'\le2gL Λ ′ ≤ 2 g L , it follows that ℓ < q \ell<q ℓ < q and ( ℓ / q ) Λ ′ < 1 (\ell/q)\Lambda'<1 ( ℓ / q ) Λ ′ < 1 . Now by Claim 5.9.2, the number of stable q q q -sets satisfies
I q ≤ ( M ℓ ) ( N 0 q − ℓ ) ≤ ( q ℓ ) M ℓ N 0 q − ℓ q ! ≤ ( 2 e q ) q M ℓ ( 2 δ M ) q − ℓ . I_q\le\binom{M}{\ell}\binom{N_0}{q-\ell}\le\binom{q}{\ell}\frac{M^\ell N_0^{q-\ell}}{q!}\le\left(\frac{2e}{q}\right)^qM^\ell(2\delta M)^{q-\ell}. I q ≤ ( ℓ M ) ( q − ℓ N 0 ) ≤ ( ℓ q ) q ! M ℓ N 0 q − ℓ ≤ ( q 2 e ) q M ℓ ( 2 δ M ) q − ℓ .
where we used ( q ℓ ) ≤ 2 q \binom{q}{\ell}\le2^q ( ℓ q ) ≤ 2 q , q ! ≥ ( q / e ) q q!\ge(q/e)^q q ! ≥ ( q / e ) q , and N 0 ≤ 2 δ M N_0\le2\delta M N 0 ≤ 2 δ M . Comparing this with I q ≥ 1 4 ( M / ( 2 k ) ) q I_q\ge\frac14(M/(2k))^q I q ≥ 4 1 ( M / ( 2 k ) ) q by Claim 5.9.1 and taking q q q -th roots yields ( 1 / ( 2 δ ) ) 1 − ℓ / q ≤ 4 e ( k / q ) 4 / q ≤ 8 e k / q (1/(2\delta))^{1-\ell/q}\le4e(k/q)^{4/q}\le8ek/q ( 1/ ( 2 δ ) ) 1 − ℓ / q ≤ 4 e ( k / q ) 4/ q ≤ 8 e k / q , since q ≥ 2 q\ge2 q ≥ 2 . Then by taking logarithms and using Λ ′ = ln ( 256 k / q ) \Lambda'=\ln(256k/q) Λ ′ = ln ( 256 k / q ) , we obtain ( 1 − ℓ / q ) Λ ′ ≤ ln ( 8 e k / q ) = Λ ′ − ln ( 32 / e ) (1-\ell/q)\Lambda'\le\ln(8ek/q)=\Lambda'-\ln(32/e) ( 1 − ℓ / q ) Λ ′ ≤ ln ( 8 e k / q ) = Λ ′ − ln ( 32/ e ) . Hence ( ℓ / q ) Λ ′ ≥ ln ( 32 / e ) > 1 (\ell/q)\Lambda'\ge\ln(32/e)>1 ( ℓ / q ) Λ ′ ≥ ln ( 32/ e ) > 1 , a contradiction.
The cut tree
In this subsection, fix r ≥ 5 r\ge5 r ≥ 5 , a graph G G G and disjoint U , Y ⊆ V ( G ) U,Y\subseteq V(G) U , Y ⊆ V ( G ) with ∣ Y ∣ = n |Y|=n ∣ Y ∣ = n such that every root u ∈ U u\in U u ∈ U sends no rooted P r P_r P r into Y Y Y . Set x ∈ ( 0 , 1 ) x\in(0,1) x ∈ ( 0 , 1 ) , an integer ℓ ≥ 2 16 \ell\ge2^{16} ℓ ≥ 2 16 and let μ = n / ℓ 6 \mu=n/\ell^6 μ = n / ℓ 6 .
The cut tree is a tree whose nodes are subsets of Y Y Y with the children of each node ordered such that the following hold.
The children of a node S S S are the vertex sets of the anticonnected components of G [ N ( u S ) ∩ S ] G[N(u_S) \cap S] G [ N ( u S ) ∩ S ] (in any order), followed by S ∖ N ( u S ) S \setminus N(u_S) S ∖ N ( u S ) , where u S u_S u S is a root in U U U such that x ∣ S ∣ / 4 ≤ ∣ N ( u S ) ∩ S ∣ < ∣ S ∣ x|S|/4 \le|N(u_S) \cap S| < |S| x ∣ S ∣/4 ≤ ∣ N ( u S ) ∩ S ∣ < ∣ S ∣ .
A node S S S is large if ∣ S ∣ ≥ μ |S| \ge\mu ∣ S ∣ ≥ μ and small otherwise. We call the vertex sets of the anticonnected components of G [ N ( u S ) ∩ S ] G[N(u_S) \cap S] G [ N ( u S ) ∩ S ] the neighbor children of S S S and S ∖ N ( u S ) S \setminus N(u_S) S ∖ N ( u S ) the non-neighbor child of S S S . It follows that distinct neighbor children of S S S are complete to each other and u S u_S u S is complete to every neighbor child of S S S but anticomplete to its non-neighbor child. Since children are proper subsets, the tree is finite. Any two nodes are nested or disjoint and the left-to-right order of the tree induces a linear order on any family of pairwise disjoint nodes.
Definition 5.10. A rooted frontier of order r r r in Y Y Y is a blockade ( Z 1 , … , Z m ) (Z_1,\ldots,Z_m) ( Z 1 , … , Z m ) in G [ Y ] G[Y] G [ Y ] with nonempty blocks, together with sets R 1 , … , R m ⊆ V ( G ) ∖ Y R_1,\ldots,R_m \subseteq V(G) \setminus Y R 1 , … , R m ⊆ V ( G ) ∖ Y of at most m m m roots each and a graph J J J with vertex set [ m ] [m] [ m ] , such that:
(F1) every vertex of R 1 ∪ ⋯ ∪ R m R_1 \cup\cdots\cup R_m R 1 ∪ ⋯ ∪ R m sends no rooted P r P_r P r into Y Y Y , and R j R_j R j is complete to Z j Z_j Z j for each j j j ; and
(F2) for i < j i < j i < j , every vertex of Z j Z_j Z j sends no rooted P r − 1 P_{r-1} P r − 1 into Z i Z_i Z i ; and
(F3) if i < j i < j i < j and i j ∉ E ( J ) ij \notin E(J) ij ∈ / E ( J ) , then Z i Z_i Z i is complete to Z j Z_j Z j ; and
(F4) if j , ℓ j,\ell j , ℓ with j < ℓ j < \ell j < ℓ both lie on a path j = i 1 − i 2 − ⋯ − i p = ℓ j = i_1-i_2-\cdots-i_p = \ell j = i 1 − i 2 − ⋯ − i p = ℓ in J J J such that i 1 < i 2 < ⋯ < i p i_1 < i_2 < \cdots< i_p i 1 < i 2 < ⋯ < i p , then some vertex of R j R_j R j is anticomplete to Z ℓ Z_\ell Z ℓ .
Lemma 5.11. One of the following holds:
(T1) some S ⊆ Y S \subseteq Y S ⊆ Y with ∣ S ∣ ≥ μ |S| \ge\mu ∣ S ∣ ≥ μ is x x x -clean for U U U ;
(T2) G [ Y ] G[Y] G [ Y ] has a complete ( t , n / t 7 ) (t,n/t^7) ( t , n / t 7 ) -blockade ;
(T3) there is a rooted frontier of order r r r in Y Y Y with t t t blocks, each with at least n / t 6 n/t^6 n / t 6 vertices ;
(T4) for some integer m m m with t ≤ m ≤ 4 t 6 / x t \le m \le4t^6/x t ≤ m ≤ 4 t 6 / x , there is a rooted frontier of order r r r in Y Y Y with m m m blocks, each with at least n / m 3 n/m^3 n / m 3 vertices ;
(T5) there are disjoint nonempty sets L 1 , … , L p ⊆ Y L_1,\ldots,L_p \subseteq Y L 1 , … , L p ⊆ Y , each with fewer than n / t 6 n/t^6 n / t 6 vertices and with total size at least 3 n / ( 8 t ) 3n/(8t) 3 n / ( 8 t ) such that for every set X ⊆ L 1 ∪ ⋯ ∪ L p X \subseteq L_1 \cup\cdots\cup L_p X ⊆ L 1 ∪ ⋯ ∪ L p with ∣ X ∩ L i ∣ ≤ 1 |X \cap L_i| \le1 ∣ X ∩ L i ∣ ≤ 1 for each i i i , the vertex in X ∩ L i X \cap L_i X ∩ L i (if it exists) sends no rooted P r − 1 P_{r-1} P r − 1 into X ∩ ( L i + 1 ∪ ⋯ ∪ L p ) X \cap(L_{i+1} \cup\cdots\cup L_p) X ∩ ( L i + 1 ∪ ⋯ ∪ L p ) .
In particular, if G G G belongs to a hereditary class C \mathcal{C} C , then G [ X ] ∈ O r − 1 ( C ) G[X] \in\mathcal{O}_{r-1}(\mathcal{C}) G [ X ] ∈ O r − 1 ( C ) .
Proof. Suppose to the contrary that none of the outcomes of Lemma 5.11 holds. Build the cut tree of Y Y Y . If some large node is x x x -clean for U U U , then we have Lemma 5.11 (T1). So we may assume that every node without children is small. We use the following terms.
Let S S S be a unary node. If its large child is the non-neighbor child, the positive layer of S S S is N ( u S ) ∩ S N(u_S) \cap S N ( u S ) ∩ S , the union of its neighbor children. If its large child is a neighbor child, the negative layer of S S S is its non-neighbor child S ∖ N ( u S ) S \setminus N(u_S) S ∖ N ( u S ) , and the fringe of S S S is the union of its other small neighbor children.
Claim 5.11.1. There are at most t − 1 t-1 t − 1 pairwise disjoint large nodes.
Proof of Claim 5.11.1 . Suppose to the contrary that there are t t t pairwise disjoint large nodes Z 1 , … , Z t Z_1,\ldots,Z_t Z 1 , … , Z t , listed in the left-to-right order of the cut tree. In this case, we claim that Lemma 5.11 (T3) holds, that is, there is a rooted frontier of order r r r in Y Y Y with t t t blocks, each with at least n / t 6 n/t^6 n / t 6 vertices. For j < ℓ j<\ell j < ℓ , let S S S be the lowest common ancestor of Z j Z_j Z j and Z ℓ Z_\ell Z ℓ . Since the non-neighbor child comes last, either Z j , Z ℓ Z_j,Z_\ell Z j , Z ℓ lie in distinct neighbor children of S S S , and then they are complete to each other, or Z j Z_j Z j lies in a neighbor child, Z ℓ Z_\ell Z ℓ lies in the non-neighbor child and u S u_S u S is complete to Z j Z_j Z j but anticomplete to Z ℓ Z_\ell Z ℓ . In the second case put u S u_S u S into R j R_j R j and j ℓ j\ell j ℓ into E ( J ) E(J) E ( J ) . Then ∣ R j ∣ ≤ t − 1 |R_j|\leq t-1 ∣ R j ∣ ≤ t − 1 and (F1) and (F3) hold. For (F2), in the first case a vertex of Z ℓ Z_\ell Z ℓ has no G G G -neighbor in Z j Z_j Z j , and in the second case we use Lemma 5.1 with u = u S u=u_S u = u S . For (F4), let i 1 < ⋯ < i p i_1<\cdots<i_p i 1 < ⋯ < i p be an increasing path of J J J , j = i 1 j=i_1 j = i 1 , ℓ = i p \ell=i_p ℓ = i p and S S S be the lowest common ancestor of Z j , Z ℓ Z_j,Z_\ell Z j , Z ℓ . Note that for any block Z i ∩ S ≠ ∅ Z_i\cap S\neq\varnothing Z i ∩ S = ∅ , Z i Z_i Z i lies inside a child of S S S . Since the blocks are listed in the left-to-right order of the cut tree, the indices of the blocks inside S S S form an interval.
Suppose Z j Z_j Z j and Z ℓ Z_\ell Z ℓ were in distinct neighbor children C ≠ C ′ C\neq C' C = C ′ of S S S . Then every index between j j j and ℓ \ell ℓ belongs to a child lying between C C C and C ′ C' C ′ in the order, hence to a neighbor child of S S S . In particular all of i 1 , i 2 , … , i p i_1,i_2,\ldots,i_p i 1 , i 2 , … , i p lie in neighbor children of S S S with i 1 i_1 i 1 in C C C and i p i_p i p in C ′ C' C ′ . Taking the least c ≥ 1 c\geq1 c ≥ 1 with Z i c + 1 ⊈ C Z_{i_{c+1}}\not\subseteq C Z i c + 1 ⊆ C , then the blocks Z i c Z_{i_c} Z i c and Z i c + 1 Z_{i_{c+1}} Z i c + 1 lie in distinct neighbor children of their lowest common ancestor S S S . So i c i c + 1 ∉ E ( J ) i_ci_{c+1}\notin E(J) i c i c + 1 ∈ / E ( J ) by construction, contradicting that the path uses edges of J J J .
Since the non-neighbor child comes last, we may therefore assume that Z j Z_j Z j is in a neighbor child and Z ℓ Z_\ell Z ℓ in the non-neighbor child, and the root recorded in R j R_j R j is anticomplete to Z ℓ Z_\ell Z ℓ . This gives (F4) and hence gives Lemma 5.11 (T3). ■
Nodes of the retained tree without large children are pairwise disjoint. Hence we may assume that the retained tree has fewer than t t t nodes without large children by Claim 5.11.1 . In a finite rooted tree the number of nodes with at least two children is less than the number of leaves, so the retained tree also has fewer than t t t nodes with at least two large children. Thus, there are fewer than 2 t 2t 2 t exceptional nodes, and every other large node is unary.
Suppose some large node has a set D D D of small neighbor children of total size at least t μ t\mu t μ . The anticonnected components of G [ D ] G[D] G [ D ] are these children, each smaller than μ ≤ ∣ D ∣ / t \mu\leq|D|/t μ ≤ ∣ D ∣/ t . By Lemma 2.3, there is a complete ( t , ∣ D ∣ / t 2 ) (t,|D|/t^2) ( t , ∣ D ∣/ t 2 ) -blockade with ∣ D ∣ / t 2 ≥ μ / t = n / t 7 |D|/t^2\geq\mu/t=n/t^7 ∣ D ∣/ t 2 ≥ μ / t = n / t 7 , which gives Lemma 5.11 (T2). So we may assume that the pieces that are children of any one large node have total size less than ( t + 1 ) μ (t+1)\mu ( t + 1 ) μ . Then the exceptional nodes have pieces of total size less than 2 t ( t + 1 ) μ 2t(t+1)\mu 2 t ( t + 1 ) μ , and so the unary nodes have pieces of total size at least n − 2 t ( t + 1 ) μ n-2t(t+1)\mu n − 2 t ( t + 1 ) μ . Since there are at most t t t top-to-bottom paths of the retained tree, one such path P P P carries pieces of unary nodes of total size at least n / t − 2 ( t + 1 ) μ n/t-2(t+1)\mu n / t − 2 ( t + 1 ) μ .
By the definition of fringe sets, fringe sets of different unary nodes of P P P are complete to each other. If the fringe sets of unary nodes of P P P have total size at least t μ t\mu t μ , then by Lemma 2.3 again, Lemma 5.11 (T2) holds. Since t ≥ 2 t \ge2 t ≥ 2 and μ = n / t 6 \mu= n/t^{6} μ = n / t 6 , n / t − ( 3 t + 2 ) μ ≥ n / t − 4 t μ = n / t − 4 n / ( t 5 ) ≥ n / t − n / ( 4 t ) = 3 n / ( 4 t ) n/t - (3t+2)\mu\ge n/t - 4t\mu= n/t - 4n/(t^{5}) \ge n/t - n/(4t) = 3n/(4t) n / t − ( 3 t + 2 ) μ ≥ n / t − 4 t μ = n / t − 4 n / ( t 5 ) ≥ n / t − n / ( 4 t ) = 3 n / ( 4 t ) . So we may assume that the positive and negative layers of unary nodes of P \mathcal{P} P have total size at least 3 n / ( 4 t ) 3n/(4t) 3 n / ( 4 t ) . Thus, either the positive layers or the negative layers have total size at least 3 n / ( 8 t ) 3n/(8t) 3 n / ( 8 t ) .
Suppose first that the negative layers L 1 , … , L p L_1,\ldots,L_p L 1 , … , L p (in the order of P \mathcal{P} P ) have total size at least 3 n / ( 8 t ) 3n/(8t) 3 n / ( 8 t ) . So ∣ L i ∣ < μ |L_i| < \mu ∣ L i ∣ < μ for each i ∈ [ p ] i \in[p] i ∈ [ p ] . Let X X X be a set such that ∣ X ∩ L i ∣ ≤ 1 |X \cap L_i| \le1 ∣ X ∩ L i ∣ ≤ 1 and let p i ∈ X ∩ L i p_i \in X \cap L_i p i ∈ X ∩ L i if p i p_i p i exists. The root u i u_i u i of the node of L i L_i L i is anticomplete to L i L_i L i and complete to every later layer. Since u i u_i u i sends no rooted P r P_r P r into Y Y Y , by Lemma 5.1 , p i p_i p i sends no rooted P r − 1 P_{r-1} P r − 1 into the later vertices of X ∩ ( L i + 1 ∪ ⋯ ∪ L p ) X \cap(L_{i+1} \cup\cdots\cup L_p) X ∩ ( L i + 1 ∪ ⋯ ∪ L p ) . This gives Lemma 5.11 (T5), a contradiction.
So we may assume that the positive layers have total size at least 3 n / ( 8 t ) 3n/(8t) 3 n / ( 8 t ) . Since they are disjoint and each has at least x μ / 4 x\mu/4 xμ /4 vertices, there are at most 4 t 6 / x 4t^{6}/x 4 t 6 / x of them. We claim that for some integer m ≥ t m \ge t m ≥ t , at least m m m positive layers have at least n / m 3 n/m^{3} n / m 3 vertices each. Otherwise, listing their sizes as a 1 ≥ a 2 ≥ ⋯ a_1 \ge a_2 \ge\cdots a 1 ≥ a 2 ≥ ⋯ (with a i = 0 a_i = 0 a i = 0 beyond the number of positive layers), we have a m < n / m 3 a_m < n/m^{3} a m < n / m 3 for all m ≥ t m \ge t m ≥ t and a i < t μ = n / t 5 a_i < t\mu= n/t^{5} a i < t μ = n / t 5 for i < t i < t i < t since every positive layer has fewer than t μ t\mu t μ vertices. So the total size is
∑ i ≥ 1 a i < ∑ i < t n t 5 + ∑ m ≥ t n m 3 ≤ n t 4 + n ∫ t − 1 ∞ d z z 3 = n t 4 + n 2 ( t − 1 ) 2 < n 8 t , \sum_{i \ge1} a_i < \sum_{i < t} \frac{n}{t^{5}} + \sum_{m \ge t} \frac{n}{m^{3}} \le\frac{n}{t^{4}} + n \int_{t-1}^{\infty} \frac{dz}{z^{3}} = \frac{n}{t^{4}} + \frac{n}{2(t-1)^{2}} < \frac{n}{8t}, i ≥ 1 ∑ a i < i < t ∑ t 5 n + m ≥ t ∑ m 3 n ≤ t 4 n + n ∫ t − 1 ∞ z 3 d z = t 4 n + 2 ( t − 1 ) 2 n < 8 t n ,
the last inequality since t ≥ 2 16 t \ge2^{16} t ≥ 2 16 . This contradicts the total size being at least 3 n / ( 8 t ) 3n/(8t) 3 n / ( 8 t ) . Keep m m m such positive layers Z 1 , … , Z m Z_1,\ldots,Z_m Z 1 , … , Z m in the order of P \mathcal{P} P and let R j R_j R j consist of the root of the node of Z j Z_j Z j , J J J be the complete graph. Then the root of Z j Z_j Z j is complete to Z j Z_j Z j and anticomplete to all later positive layers, which gives (F1), (F3) and (F4), and (F2) follows from Lemma 5.1 . This gives Lemma 5.11 (T4), a contradiction.
This completes the proof of Lemma 5.11 . □ \square □
Frontiers of order five
Definition 5.12. Let r ≥ 5 r \ge5 r ≥ 5 , c ≥ 16 c \ge16 c ≥ 16 and C \mathcal{C} C be a hereditary class. We say C \mathcal{C} C has the frontier property of order r r r with constant c c c if the following holds for every G ∈ C G \in\mathcal{C} G ∈ C , every Y ⊆ V ( G ) Y \subseteq V(G) Y ⊆ V ( G ) , every n > 0 n > 0 n > 0 , every integer m ≥ 2 c m \ge2^{c} m ≥ 2 c , every ρ ∈ ( 0 , 1 ] \rho\in(0,1] ρ ∈ ( 0 , 1 ] and every b ∈ { 3 , 6 } b \in\{3,6\} b ∈ { 3 , 6 } . If ( Z 1 , … , Z m ) (Z_1,\ldots,Z_m) ( Z 1 , … , Z m ) is a rooted frontier of order r r r in Y Y Y with ∣ Z i ∣ ≥ ( m / ρ ) c |Z_i| \ge(m/\rho)^c ∣ Z i ∣ ≥ ( m / ρ ) c and ∣ Z i ∣ ≥ n / m b |Z_i| \ge n/m^b ∣ Z i ∣ ≥ n / m b for every i i i , then either
for some z ∈ [ ( ρ / m ) c , 1 / m ] z \in[(\rho/m)^c,1/m] z ∈ [( ρ / m ) c , 1/ m ] , there is a z 4 z^4 z 4 -restricted T ⊆ Z 1 ∪ ⋯ ∪ Z m T \subseteq Z_1 \cup\cdots\cup Z_m T ⊆ Z 1 ∪ ⋯ ∪ Z m with ∣ T ∣ ≥ z c + b n |T| \ge z^{c+b}n ∣ T ∣ ≥ z c + b n ; or
for some integer K ∈ [ m 1 / 4 , ( m / ρ ) c ] K \in[m^{1/4},(m/\rho)^c] K ∈ [ m 1/4 , ( m / ρ ) c ] , there is a ρ \rho ρ -semisparse ( K , n / K c + 4 b ) (K,n/K^{c+4b}) ( K , n / K c + 4 b ) -blockade in G [ Z 1 ∪ ⋯ ∪ Z m ] G[Z_1 \cup\cdots\cup Z_m] G [ Z 1 ∪ ⋯ ∪ Z m ] .
Let G G G be a graph with blockade W = ( W 1 , … , W m ) \mathcal{W} = (W_1,\ldots,W_m) W = ( W 1 , … , W m ) and β > 0 \beta> 0 β > 0 such that for every vertex w ∈ W j w \in W_j w ∈ W j and every i < j i < j i < j , w w w is either complete to W i W_i W i or has fewer than β ∣ W i ∣ \beta|W_i| β ∣ W i ∣ neighbors in W i W_i W i . We say that w w w is *complete (sparse) towards i i i . The ambiguity graph of W \mathcal{W} W is the graph A A A on [ m ] [m] [ m ] in which i < j i < j i < j are adjacent if W j W_j W j contains both a vertex complete towards i i i and a vertex sparse towards i i i . If A A A has no edges, then each W j W_j W j is complete or β \beta β -sparse to each earlier W i W_i W i , and so ( W 1 , … , W m ) (W_1,\ldots,W_m) ( W 1 , … , W m ) is already β \beta β -semisparse. An increasing path of A A A is a sequence i 1 < ⋯ < i p i_1 < \cdots< i_p i 1 < ⋯ < i p with i a i a + 1 ∈ E ( A ) i_ai_{a+1} \in E(A) i a i a + 1 ∈ E ( A ) for all $a < p.
Lemma 5.13 (Monotone paths). Let m ≥ 4 m \ge4 m ≥ 4 , k ′ = ⌊ m ⌋ k' = \lfloor\sqrt{m}\rfloor k ′ = ⌊ m ⌋ , G G G be a graph with blockade W = ( W 1 , … , W m ) \mathcal{W} = (W_1,\ldots,W_m) W = ( W 1 , … , W m ) and β > 0 \beta> 0 β > 0 such that for every vertex w ∈ W j w \in W_j w ∈ W j and every i < j i < j i < j , w w w is either complete or sparse towards i i i . Let A \mathcal{A} A be the ambiguity graph of W \mathcal{W} W . Suppose that for every increasing path i 1 < ⋯ < i p i_1 < \cdots< i_p i 1 < ⋯ < i p of A \mathcal{A} A and all a < b − 1 a < b-1 a < b − 1 , no vertex of W i b W_{i_b} W i b is sparse towards i a i_a i a and complete towards i a + 1 i_{a+1} i a + 1 . Then there is a k ′ β k'\beta k ′ β -semisparse blockade of length k ′ k' k ′ and width at least min i ∈ [ m ] { ∣ W i ∣ / k ′ } \min_{i\in[m]}\{|W_i|/k'\} min i ∈ [ m ] { ∣ W i ∣/ k ′ } , each of whose blocks is a subset of some W i W_i W i .
Proof. By hypothesis, along an increasing path i 1 < ⋯ < i p i_1 < \cdots< i_p i 1 < ⋯ < i p , a vertex of W i b W_{i_b} W i b that is sparse towards some i a i_a i a is also sparse towards i a + 1 , … , i b − 1 i_{a+1},\ldots,i_{b-1} i a + 1 , … , i b − 1 . So its types towards i 1 , … , i b − 1 i_1,\ldots,i_{b-1} i 1 , … , i b − 1 are complete up to some point and sparse afterwards. Call the number of complete ones its complete prefix . For example, a vertex of W i 5 W_{i_5} W i 5 whose types towards i 1 , i 2 , i 3 , i 4 i_1,i_2,i_3,i_4 i 1 , i 2 , i 3 , i 4 are complete, complete, sparse, sparse has complete prefix 2.
Suppose first that A \mathcal{A} A has an increasing path i 1 < ⋯ < i k ′ i_1 < \cdots< i_{k'} i 1 < ⋯ < i k ′ . Partition each W i b W_{i_b} W i b according to the complete prefix (at most k ′ k' k ′ values) and keep a largest part W b ′ W'_b W b ′ , so ∣ W b ′ ∣ ≥ ∣ W i b ∣ / k ′ |W'_b| \ge|W_{i_b}|/k' ∣ W b ′ ∣ ≥ ∣ W i b ∣/ k ′ . For every a < b a < b a < b , all vertices of W b ′ W'_b W b ′ have the same type towards i a i_a i a . If it is complete, W b ′ W'_b W b ′ is complete to W a ′ ⊆ W i a W'_a \subseteq W_{i_a} W a ′ ⊆ W i a and if it is sparse, every vertex of W b ′ W'_b W b ′ has fewer than β ∣ W i a ∣ ≤ k ′ β ∣ W a ′ ∣ \beta|W_{i_a}| \le k'\beta|W'_a| β ∣ W i a ∣ ≤ k ′ β ∣ W a ′ ∣ neighbors in W a ′ W'_a W a ′ . Then ( W 1 ′ , … , W k ′ ′ ) (W'_1,\ldots,W'_{k'}) ( W 1 ′ , … , W k ′ ′ ) is the required blockade.
So we may assume that A \mathcal{A} A has no increasing path with at least k ′ k' k ′ vertices. Label each i ∈ [ m ] i \in[m] i ∈ [ m ] by the number of vertices of a longest increasing path of A \mathcal{A} A ending at i i i . So there are at most k ′ − 1 k'-1 k ′ − 1 labels. Then some label class has at least m / ( k ′ − 1 ) > k ′ m/(k'-1) > k' m / ( k ′ − 1 ) > k ′ indices. If two indices i < j i < j i < j in this label class are adjacent in A \mathcal{A} A , then the longest increasing path ending at j j j is longer than the path ending at i i i , a contradiction. So for every i < j i < j i < j in this class, all vertices of W j W_j W j have the same type towards i i i , so W j W_j W j is complete or β \beta β -sparse to W i W_i W i . Hence the corresponding sets W i W_i W i form a β \beta β -semisparse blockade of length at least k ′ k' k ′ .
Lemma 5.14. Every hereditary class has the frontier property of order 5 with constant 20.
Proof. Let ( Z 1 , … , Z m ) (Z_1,\ldots,Z_m) ( Z 1 , … , Z m ) with R j R_j R j , J J J be a rooted frontier of order 5 with c = 20 c=20 c = 20 as in Definitions 5.10 and 5.12 . Put
ξ 0 = ρ 64 m 5 , θ = ξ 0 4 , η = 1 16 m 3 , β = 2 m 2 θ = ρ 128 m 3 . \xi_0 = \frac{\rho}{64m^5}, \qquad\theta= \frac{\xi_0}{4}, \qquad\eta= \frac{1}{16m^3}, \qquad\beta= 2m^2\theta= \frac{\rho}{128m^3}. ξ 0 = 64 m 5 ρ , θ = 4 ξ 0 , η = 16 m 3 1 , β = 2 m 2 θ = 128 m 3 ρ .
Since m ≥ 2 20 m \ge2^{20} m ≥ 2 20 and 0 < ρ ≤ 1 0 < \rho\le1 0 < ρ ≤ 1 , we have 0 < ξ 0 < 2 − 30 0 < \xi_0 < 2^{-30} 0 < ξ 0 < 2 − 30 and 2 16 ≤ m ≤ 2 ξ 0 − 1 / 2 2^{16} \le m \le2\xi_0^{-1/2} 2 16 ≤ m ≤ 2 ξ 0 − 1/2 . Moreover, ∣ Z i ∣ ≥ ( m / ρ ) 20 ≥ 16 ξ 0 − 3 |Z_i| \ge(m/\rho)^{20} \ge16\xi_0^{-3} ∣ Z i ∣ ≥ ( m / ρ ) 20 ≥ 16 ξ 0 − 3 for every i ∈ [ m ] i \in[m] i ∈ [ m ] . By Definition 5.10 (F2), every vertex of ⋃ j > i Z j \bigcup_{j>i} Z_j ⋃ j > i Z j sends no rooted P 4 P_4 P 4 into Z i Z_i Z i , and this root set is disjoint from Z i Z_i Z i . Thus the conditions of Lemma 5.8 hold for each Z i Z_i Z i with parameters ( ξ 0 , m ) (\xi_0,m) ( ξ 0 , m ) and root set ⋃ j > i Z j \bigcup_{j>i} Z_j ⋃ j > i Z j .
In the rest of the proof, whenever an application of Lemma 5.8 or Lemma 2.3 gives a blockade instead, we stop at once (an early outcome ). Such a blockade is pure (Lemma 5.8 (M1)–(M3)) or complete (5.8 (M4) and Lemma 2.3), hence ρ \rho ρ -semisparse. We show that its length and width satisfy the second alternative of Definition 5.12 in Table 1 . So each early outcome is already the conclusion of the lemma, and nothing is carried to the end.
Table 1. Blockades produced in the proof of Lemma 5.14 . Rounds 1 and 2 apply Lemma 5.8 with parameters ( ξ 0 , m ) (\xi_0,m) ( ξ 0 , m ) and ( m − 2 , m ) (m^{-2},m) ( m − 2 , m ) to sets of at least n / m b n/m^b n / m b and n / m b + 1 n/m^{b+1} n / m b + 1 vertices. All blockades except the final one are pure or complete, hence ρ \rho ρ -semisparse.
We proceed as follows.
Round 1. By Lemma 5.8 applied to Z i Z_i Z i , there is Z i ( 1 ) ⊆ Z i Z_i^{(1)} \subseteq Z_i Z i ( 1 ) ⊆ Z i with ∣ Z i ( 1 ) ∣ ≥ ∣ Z i ∣ / m |Z_i^{(1)}| \ge|Z_i|/m ∣ Z i ( 1 ) ∣ ≥ ∣ Z i ∣/ m such that every vertex of ⋃ j > i Z j \bigcup_{j>i} Z_j ⋃ j > i Z j is complete to Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) or has fewer than θ ∣ Z i ( 1 ) ∣ \theta|Z_i^{(1)}| θ ∣ Z i ( 1 ) ∣ neighbors in Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) . Accordingly every vertex p ∈ Z j ( 1 ) p \in Z_j^{(1)} p ∈ Z j ( 1 ) has a type towards each i < j i < j i < j : complete or sparse. All sets
::: below are subsets of the Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) , and a vertex complete towards i i i remains complete to every subset of Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) .
Round 2. Call a pair i < j i<j i < j good if some root u ∈ R j u\in R_j u ∈ R j has at least η ∣ Z i ( 1 ) ∣ \eta|Z_i^{(1)}| η ∣ Z i ( 1 ) ∣ nonneighbors in Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) , and bad otherwise. For a good pair fix such a root u u u , and let S i j S_{ij} S ij be the set of vertices of Z j ( 1 ) Z_j^{(1)} Z j ( 1 ) that are sparse towards i i i . There are at most θ ∣ Z i ( 1 ) ∣ ∣ S i j ∣ \theta|Z_i^{(1)}||S_{ij}| θ ∣ Z i ( 1 ) ∣∣ S ij ∣ edges between Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) and S i j S_{ij} S ij . So some nonneighbor p i j p_{ij} p ij of u u u in Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) has at most ( θ ∣ Z i ( 1 ) ∣ ∣ S i j ∣ ) / ( η ∣ Z i ( 1 ) ∣ ) ≤ θ ∣ Z j ( 1 ) ∣ / η (\theta|Z_i^{(1)}||S_{ij}|)/(\eta|Z_i^{(1)}|)\leq\theta|Z_j^{(1)}|/\eta ( θ ∣ Z i ( 1 ) ∣∣ S ij ∣ ) / ( η ∣ Z i ( 1 ) ∣ ) ≤ θ ∣ Z j ( 1 ) ∣/ η neighbors in S i j S_{ij} S ij . By Definition 5.10 (F1) and Lemma 5.1 (with Z = Z j ( 1 ) Z=Z_j^{(1)} Z = Z j ( 1 ) ), p i j p_{ij} p ij sends no rooted P 4 P_4 P 4 into Z j ( 1 ) Z_j^{(1)} Z j ( 1 ) . Apply Lemma 5.8 to Z j ( 1 ) Z_j^{(1)} Z j ( 1 ) (which has at least 16 m 6 16m^6 16 m 6 vertices) with parameters ( m − 2 , m ) (m^{-2},m) ( m − 2 , m ) and the representatives p i j p_{ij} p ij (i < j i<j i < j good) as roots. Outside early outcomes we get D j ⊆ Z j ( 1 ) D_j\subseteq Z_j^{(1)} D j ⊆ Z j ( 1 ) with ∣ D j ∣ ≥ ∣ Z j ( 1 ) ∣ / m |D_j|\geq|Z_j^{(1)}|/m ∣ D j ∣ ≥ ∣ Z j ( 1 ) ∣/ m on which each p i j p_{ij} p ij is complete or has fewer than ∣ D j ∣ / ( 4 m 2 ) |D_j|/(4m^2) ∣ D j ∣/ ( 4 m 2 ) neighbors.
After choosing all the sets D j D_j D j , we make the following deletions from each D j D_j D j , simultaneously for all pairs.
For each good pair i < j i<j i < j , if p i j p_{ij} p ij is complete to D j D_j D j , delete D j ∩ S i j D_j\cap S_{ij} D j ∩ S ij , which has at most θ ∣ Z j ( 1 ) ∣ / η ≤ θ m ∣ D j ∣ / η \theta|Z_j^{(1)}|/\eta\leq\theta m|D_j|/\eta θ ∣ Z j ( 1 ) ∣/ η ≤ θ m ∣ D j ∣/ η vertices. Otherwise, delete the vertices of D j D_j D j that are complete towards i i i . All these vertices are adjacent to p i j p_{ij} p ij , so there are fewer than ∣ D j ∣ / ( 4 m 2 ) |D_j|/(4m^2) ∣ D j ∣/ ( 4 m 2 ) of them.
For fixed j j j , the deletions in the second item remove fewer than m 2 η ∣ Z j ( 1 ) ∣ ≤ ∣ D j ∣ / 16 m^2\eta|Z_j^{(1)}|\leq|D_j|/16 m 2 η ∣ Z j ( 1 ) ∣ ≤ ∣ D j ∣/16 vertices in total. Since θ m 2 / η = ρ / 16 \theta m^2/\eta=\rho/16 θ m 2 / η = ρ /16 , the deletions of the first kind remove at most m ( 1 / ( 4 m 2 ) + θ m / η ) = 1 / ( 4 m ) + ρ / 16 ≤ 1 / 8 m(1/(4m^2)+\theta m/\eta)=1/(4m)+\rho/16\leq1/8 m ( 1/ ( 4 m 2 ) + θ m / η ) = 1/ ( 4 m ) + ρ /16 ≤ 1/8 of D j D_j D j . Let Z j ( 2 ) Z_j^{(2)} Z j ( 2 ) be what remains of D j D_j D j . So ∣ Z j ( 2 ) ∣ ≥ ∣ Z j ( 1 ) ∣ / ( 2 m ) |Z_j^{(2)}|\geq|Z_j^{(1)}|/(2m) ∣ Z j ( 2 ) ∣ ≥ ∣ Z j ( 1 ) ∣/ ( 2 m ) . Now for a good pair i < j i<j i < j , all vertices of Z j ( 2 ) Z_j^{(2)} Z j ( 2 ) have the same type towards i i i and for a bad pair i < j i<j i < j every root in R j R_j R j is complete to Z i ( 2 ) Z_i^{(2)} Z i ( 2 ) .
Round 3. If for some i i i , every anticonnected component of G [ Z i ( 2 ) ] G[Z_i^{(2)}] G [ Z i ( 2 ) ] has fewer than ∣ Z i ( 2 ) ∣ / m |Z_i^{(2)}|/m ∣ Z i ( 2 ) ∣/ m vertices, Lemma 2.3 gives a complete ( m , ∣ Z i ( 2 ) ∣ / m 2 ) (m,|Z_i^{(2)}|/m^2) ( m , ∣ Z i ( 2 ) ∣/ m 2 ) -blockade (an early outcome). So there is an anticonnected component of G [ Z i ( 2 ) ] G[Z_i^{(2)}] G [ Z i ( 2 ) ] , denoted by Z i ( 3 ) Z_i^{(3)} Z i ( 3 ) , with at least ∣ Z i ( 2 ) ∣ / m ≥ ∣ Z i ∣ / ( 2 m 3 ) |Z_i^{(2)}|/m\geq|Z_i|/(2m^3) ∣ Z i ( 2 ) ∣/ m ≥ ∣ Z i ∣/ ( 2 m 3 ) vertices. A vertex sparse towards i i i has fewer than θ ∣ Z i ( 1 ) ∣ ≤ β ∣ Z i ( 3 ) ∣ \theta|Z_i^{(1)}|\leq\beta|Z_i^{(3)}| θ ∣ Z i ( 1 ) ∣ ≤ β ∣ Z i ( 3 ) ∣ neighbors in Z i ( 3 ) Z_i^{(3)} Z i ( 3 ) . So the types of round 1 satisfy the setting of Lemma 5.13 for the sets W i = Z i ( 3 ) W_i=Z_i^{(3)} W i = Z i ( 3 ) with this β \beta β . Let A A A be the ambiguity graph, and call its edges ambiguous pairs . Since for a good pair i < j i<j i < j , all vertices of Z j ( 2 ) Z_j^{(2)} Z j ( 2 ) have the same type towards i i i , ambiguous pairs are bad and they are edges of J J J (if i j ∉ E ( J ) ij\notin E(J) ij ∈ / E ( J ) the blocks are complete, so all vertices are complete towards i i i ). In particular an increasing path of A A A is an increasing path of J J J .
Claim 5.14.1. Let i 1 < ⋯ < i p i_1<\cdots<i_p i 1 < ⋯ < i p be an increasing path of A A A and i = i a i=i_a i = i a , j = i a + 1 j=i_{a+1} j = i a + 1 be consecutive on it. Let ℓ \ell ℓ be a later vertex of the path. Then no vertex of Z ℓ ( 3 ) Z_\ell^{(3)} Z ℓ ( 3 ) is complete towards j j j and sparse towards i i i .
Proof of Claim 5.14.1. Suppose w ∈ Z ℓ ( 3 ) w\in Z_\ell^{(3)} w ∈ Z ℓ ( 3 ) is complete towards j j j and sparse towards i i i . By Definition 5.10 (F4), some root u ∈ R j u\in R_j u ∈ R j is anticomplete to Z ℓ Z_\ell Z ℓ . By Definition 5.10 (F1), u u u is complete to Z j ( 3 ) Z_j^{(3)} Z j ( 3 ) . Since i j ij ij is bad, u u u is complete to Z i ( 3 ) Z_i^{(3)} Z i ( 3 ) . As Z i ( 3 ) Z_i^{(3)} Z i ( 3 ) contains both a vertex complete towards i i i and a vertex sparse towards i i i and G ‾ [ Z j ( 3 ) ] \overline{G}[Z_j^{(3)}] G [ Z j ( 3 ) ] is connected, there is a G ‾ \overline{G} G -edge v v ′ vv' v v ′ inside Z j ( 3 ) Z_j^{(3)} Z j ( 3 ) with v v v sparse and v ′ v' v ′ complete towards i i i . Since w w w and v v v each have fewer than β ∣ Z i ( 3 ) ∣ \beta|Z_i^{(3)}| β ∣ Z i ( 3 ) ∣ neighbors in Z ( 3 ) Z^{(3)} Z ( 3 ) and 2 β < 1 2\beta< 1 2 β < 1 , there is p ∈ Z i ( 3 ) p \in Z_i^{(3)} p ∈ Z i ( 3 ) nonadjacent to both w w w and v v v . Then u − w − p − v − v ′ u-w-p-v-v' u − w − p − v − v ′ is an induced path of G G G as u w uw u w , w p wp w p , p v pv p v , v v ′ vv' v v ′ are G G G -edges, while in G G G the vertex u u u is complete to { p , v , v ′ } \{p,v,v'\} { p , v , v ′ } , the vertex w w w is complete to { v , v ′ } ⊆ Z j ( 3 ) \{v,v'\} \subseteq Z_j^{(3)} { v , v ′ } ⊆ Z j ( 3 ) , and v ′ v' v ′ is adjacent to p p p . This is a rooted P 5 P_5 P 5 from u u u into Y Y Y , contrary to Definition 5.10 (F1). ■
By Claim 5.14.1, the hypothesis of Lemma 5.13 holds, which gives, with k ′ = ⌊ m ⌋ k'=\lfloor\sqrt{m}\rfloor k ′ = ⌊ m ⌋ , a k ′ β k'\beta k ′ β -semisparse, hence ρ \rho ρ -semisparse, blockade of length k ′ k' k ′ and width at least min i ∣ Z i ( 3 ) ∣ / k ′ \min_i |Z_i^{(3)}|/k' min i ∣ Z i ( 3 ) ∣/ k ′ .
Now we are ready to check the lengths and widths of all early outcome blockades. Recall that ∣ Z i ∣ ≥ n / m b |Z_i| \ge n/m^b ∣ Z i ∣ ≥ n / m b for every i i i . The inputs to the first and second applications of Lemma 5.8 have at least n / m b n/m^b n / m b and n / m b + 1 n/m^{b+1} n / m b + 1 vertices, respectively. Moreover, ∣ Z i ( 2 ) ∣ ≥ n / ( 2 m b + 2 ) |Z_i^{(2)}| \ge n/(2m^{b+2}) ∣ Z i ( 2 ) ∣ ≥ n / ( 2 m b + 2 ) . Table 1 lists every blockade the proof can produce with its length K K K , its width as given by the lemma used and an exponent e e e with width at least n / K e n/K^e n / K e . Every length satisfies m 1 / 4 ≤ K ≤ 1 / ξ 0 = 64 m 5 / ρ ≤ ( m / ρ ) 6 m^{1/4} \le K \le1/\xi_0 = 64m^5/\rho\le(m/\rho)^6 m 1/4 ≤ K ≤ 1/ ξ 0 = 64 m 5 / ρ ≤ ( m / ρ ) 6 , all exponents are at most 4 b + 8 ≤ 4 b + 12 ≤ 20 + 4 b 4b+8 \le4b+12 \le20+4b 4 b + 8 ≤ 4 b + 12 ≤ 20 + 4 b and K ≤ ( m / ρ ) 20 K \le(m/\rho)^{20} K ≤ ( m / ρ ) 20 . This proves Lemma 5.14 . □
Frontiers of order at least six
Lemma 5.15. Let r ≥ 6 r \ge6 r ≥ 6 and C C C be a hereditary class satisfying R r − 1 R_{r-1} R r − 1 and R max ( r − 2 , 5 ) R_{\max(r-2,5)} R m a x ( r − 2 , 5 ) , both with constant d 0 ≥ 2 d_0 \ge2 d 0 ≥ 2 . Then C C C has the frontier property of order r r r with constant c = d 0 ( 4 d 0 + 11 ) c=d_0(4d_0+11) c = d 0 ( 4 d 0 + 11 ) .
Proof. Let ( Z 1 , … , Z m ) (Z_1,\ldots,Z_m) ( Z 1 , … , Z m ) , R j R_j R j , J J J be a rooted frontier of order r r r in Y Y Y , with G ∈ C G \in C G ∈ C and m m m , ρ \rho ρ , b b b , n n n as in Definition 5.12. All applications of R r − 1 R_{r-1} R r − 1 and R max ( r − 2 , 5 ) R_{\max(r-2,5)} R m a x ( r − 2 , 5 ) below are made in G G G , with coarse parameter 1 / m ≤ 2 − d 0 1/m \le2^{-d_0} 1/ m ≤ 2 − d 0 . Whenever such an application gives Definition 5.2 (R2) or (R3), we stop (an early outcome ). Put
a 0 = ρ 2 12 m 4 d 0 + 10 , θ = a 0 4 , a 1 = ρ 64 m 2 , η = 1 16 m d 0 + 2 , β = 2 m d 0 θ , β ′ = 2 m d 0 β . a_0=\frac{\rho}{2^{12}m^4d_0+10},\quad\theta=\frac{a_0}{4},\quad a_1=\frac{\rho}{64m^2},\quad\eta=\frac{1}{16md_0+2},\quad\beta=2m^{d_0}\theta,\quad\beta'=2m^{d_0}\beta. a 0 = 2 12 m 4 d 0 + 10 ρ , θ = 4 a 0 , a 1 = 64 m 2 ρ , η = 16 m d 0 + 2 1 , β = 2 m d 0 θ , β ′ = 2 m d 0 β .
We have 0 < a 0 ≤ a 1 ≤ min { ρ , 1 / m } 0<a_0\le a_1\le\min\{\rho,1/m\} 0 < a 0 ≤ a 1 ≤ min { ρ , 1/ m } . We proceed as follows.
Round 1. By Definition 5.10 (F2), the vertices in ⋃ j > i Z j \bigcup_{j>i}Z_j ⋃ j > i Z j send no rooted P r − 1 P_{r-1} P r − 1 into Z i Z_i Z i . Since ∣ Z i ∣ ≥ ( m / ρ ) c ≥ a 0 − d 0 |Z_i|\ge(m/\rho)^c\ge a_0^{-d_0} ∣ Z i ∣ ≥ ( m / ρ ) c ≥ a 0 − d 0 , by applying R r − 1 R_{r-1} R r − 1 to Z i Z_i Z i with x x x replaced by a 0 a_0 a 0 , outside early outcomes, Definition 5.2 (R1) gives Z i ( 1 ) ⊆ Z i Z_i^{(1)}\subseteq Z_i Z i ( 1 ) ⊆ Z i with ∣ Z i ( 1 ) ∣ ≥ ∣ Z i ∣ / m d 0 |Z_i^{(1)}|\ge|Z_i|/m^{d_0} ∣ Z i ( 1 ) ∣ ≥ ∣ Z i ∣/ m d 0 such that every vertex in ⋃ j > i Z j \bigcup_{j>i}Z_j ⋃ j > i Z j is complete to Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) or has fewer than θ ∣ Z i ( 1 ) ∣ \theta|Z_i^{(1)}| θ ∣ Z i ( 1 ) ∣ neighbors in Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) . So, as in round 1 of Lemma 5.14 , every vertex p ∈ Z j ( 1 ) p\in Z_j^{(1)} p ∈ Z j ( 1 ) has a type towards each i < j i<j i < j : complete if p p p is complete to Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) and sparse if p p p has fewer than θ ∣ Z i ( 1 ) ∣ \theta|Z_i^{(1)}| θ ∣ Z i ( 1 ) ∣ neighbors in Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) . A vertex complete towards i i i remains complete to every subset of Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) .
Round 2. Call a pair i < j i<j i < j good if some root u ∈ R j u\in R_j u ∈ R j has at least η ∣ Z i ( 1 ) ∣ \eta|Z_i^{(1)}| η ∣ Z i ( 1 ) ∣ nonneighbors in Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) and bad otherwise. For a good pair i < j i<j i < j , fix such a root u u u and let S i j S_{ij} S ij be the set of vertices of Z j ( 1 ) Z_j^{(1)} Z j ( 1 ) sparse towards i i i . There are at most θ ∣ Z i ( 1 ) ∣ ∣ S i j ∣ \theta|Z_i^{(1)}||S_{ij}| θ ∣ Z i ( 1 ) ∣∣ S ij ∣ edges between Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) and S i j S_{ij} S ij . Since u u u has at least η ∣ Z i ( 1 ) ∣ \eta|Z_i^{(1)}| η ∣ Z i ( 1 ) ∣ nonneighbors in Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) , we can fix a nonneighbor p i j p_{ij} p ij of u u u in Z i ( 1 ) Z_i^{(1)} Z i ( 1 ) with at most θ ∣ S i j ∣ / η ≤ θ ∣ Z i ( 1 ) ∣ / η \theta|S_{ij}|/\eta\le\theta|Z_i^{(1)}|/\eta θ ∣ S ij ∣/ η ≤ θ ∣ Z i ( 1 ) ∣/ η neighbors in S i j S_{ij} S ij . We call p i j p_{ij} p ij the representative of the good pair ( i , j ) (i,j) ( i , j ) . By Definition 5.10 (F1) and Lemma 5.1 , p i j p_{ij} p ij sends no rooted P r − 1 P_{r-1} P r − 1 into Z j ( 1 ) Z_j^{(1)} Z j ( 1 ) . Since c ≥ 4 d 0 c\ge4d_0 c ≥ 4 d 0 , m ≥ 64 m\ge64 m ≥ 64 and 0 < ρ ≤ 1 0<\rho\le1 0 < ρ ≤ 1 , we have ∣ Z j ( 1 ) ∣ ≥ ∣ Z j ∣ / m d 0 ≥ ( m / ρ ) c / m d 0 ≥ ( 64 m 2 / ρ ) d 0 = a 1 − d 0 |Z_j^{(1)}|\ge|Z_j|/m^{d_0}\ge(m/\rho)^c/m^{d_0}\ge(64m^2/\rho)^{d_0}=a_1^{-d_0} ∣ Z j ( 1 ) ∣ ≥ ∣ Z j ∣/ m d 0 ≥ ( m / ρ ) c / m d 0 ≥ ( 64 m 2 / ρ ) d 0 = a 1 − d 0 . We may therefore apply R r − 1 R_{r-1} R r − 1 to Z j ( 1 ) Z_j^{(1)} Z j ( 1 ) with parameters x = a 1 x=a_1 x = a 1 and y = 1 / m y=1/m y = 1/ m , using the vertices p i j p_{ij} p ij as roots. Outside early outcomes, we obtain D j ⊆ Z j ( 1 ) D_j\subseteq Z_j^{(1)} D j ⊆ Z j ( 1 ) with ∣ D j ∣ ≥ ∣ Z j ( 1 ) ∣ / m d 0 |D_j|\ge|Z_j^{(1)}|/m^{d_0} ∣ D j ∣ ≥ ∣ Z j ( 1 ) ∣/ m d 0 such that, for every good pair i < j i<j i < j , the representative p i j p_{ij} p ij is complete to D j D_j D j or has fewer than a 1 ∣ D j ∣ / 4 a_1|D_j|/4 a 1 ∣ D j ∣/4 neighbors in D j D_j D j . As in Lemma 5.14 , the sets D j D_j D j are chosen first and then we delete the following vertices. For each good pair i < j i<j i < j , delete the set S i j ∩ D j S_{ij}\cap D_j S ij ∩ D j if p i j p_{ij} p ij is complete to D j D_j D j and delete the vertices of D j D_j D j complete towards i i i otherwise (they are neighbors of p i j p_{ij} p ij ). For each bad pair j < ℓ j<\ell j < ℓ , delete every vertex of D j D_j D j that is nonadjacent to at least one root in R ℓ R_\ell R ℓ . For fixed j j j , the deletions of the first kind remove at most a fraction m ( a 1 / 4 + θ m d 0 / η ) = ρ / ( 256 m ) + ρ / ( 2 10 m 2 d 0 + 7 ) < 1 / 16 m(a_1/4+\theta m^{d_0}/\eta)=\rho/(256m)+\rho/(2^{10}m^{2d_0+7})<1/16 m ( a 1 /4 + θ m d 0 / η ) = ρ / ( 256 m ) + ρ / ( 2 10 m 2 d 0 + 7 ) < 1/16 of D j D_j D j , and those of the second kind remove at most m 2 η ∣ Z j ( 1 ) ∣ ≤ ∣ D j ∣ / 16 m^2\eta|Z_j^{(1)}|\le|D_j|/16 m 2 η ∣ Z j ( 1 ) ∣ ≤ ∣ D j ∣/16 vertices. Let Z j ( 2 ) Z_j^{(2)} Z j ( 2 ) be the remaining set, so ∣ Z j ( 2 ) ∣ ≥ ∣ Z j ∣ / ( 2 m 2 d 0 ) |Z_j^{(2)}|\ge|Z_j|/(2m^{2d_0}) ∣ Z j ( 2 ) ∣ ≥ ∣ Z j ∣/ ( 2 m 2 d 0 ) . A vertex sparse towards i i i has fewer than β ∣ Z i ( 2 ) ∣ \beta|Z_i^{(2)}| β ∣ Z i ( 2 ) ∣ neighbors in Z i ( 2 ) Z_i^{(2)} Z i ( 2 ) . For a good pair i < j i<j i < j , all vertices of Z j ( 2 ) Z_j^{(2)} Z j ( 2 ) have the same type towards i i i and for a bad pair i < j i<j i < j every root in R j R_j R j is complete to Z i ( 2 ) Z_i^{(2)} Z i ( 2 ) . Call i < j i<j i < j ambiguous if Z j ( 2 ) Z_j^{(2)} Z j ( 2 ) contains both a vertex complete towards i i i and a vertex sparse towards i i i . So ambiguous pairs are bad and are edges of J J J .
Round 3. Call an ambiguous pair i < j i<j i < j offending , if there are ℓ > j \ell>j ℓ > j , w ∈ Z ℓ ( 2 ) w\in Z_\ell^{(2)} w ∈ Z ℓ ( 2 ) and u ∈ R j u\in R_j u ∈ R j such that u u u is nonadjacent to w w w and w w w is complete towards j j j and sparse towards i i i . For each offending pair fix such ( ℓ , w , u ) (\ell,w,u) ( ℓ , w , u ) . Since the pair is bad, u u u is complete to Z i ( 2 ) Z_i^{(2)} Z i ( 2 ) . By Definition 5.10 (F1), u u u is also complete to Z j ( 2 ) Z_j^{(2)} Z j ( 2 ) . Since the vertex w w w has fewer than β ∣ Z j ( 2 ) ∣ \beta|Z_j^{(2)}| β ∣ Z j ( 2 ) ∣ neighbors in Z j ( 2 ) Z_j^{(2)} Z j ( 2 ) and the vertices S i j ′ ⊆ Z j ( 2 ) S'_{ij}\subseteq Z_j^{(2)} S ij ′ ⊆ Z j ( 2 ) that are sparse towards i i i send fewer than β ∣ Z i ( 2 ) ∣ ∣ S i j ′ ∣ \beta|Z_i^{(2)}||S'_{ij}| β ∣ Z i ( 2 ) ∣∣ S ij ′ ∣ edges to Z i ( 2 ) Z_i^{(2)} Z i ( 2 ) , some p ∈ Z i ( 2 ) ∖ N ( w ) p\in Z_i^{(2)}\setminus N(w) p ∈ Z i ( 2 ) ∖ N ( w ) has at most 2 β ∣ Z j ( 2 ) ∣ 2\beta|Z_j^{(2)}| 2 β ∣ Z j ( 2 ) ∣ neighbors in S i j ′ S'_{ij} S ij ′ . Fix such a representative p i j ′ = p p'_{ij}=p p ij ′ = p .
If p i j ′ p'_{ij} p ij ′ sends a rooted P r − 2 = p i j ′ − q 2 − ⋯ − q r − 2 P_{r-2}=p'_{ij}-q_2-\cdots-q_{r-2} P r − 2 = p ij ′ − q 2 − ⋯ − q r − 2 into Z j ( 2 ) Z_j^{(2)} Z j ( 2 ) , then u − w − p i j ′ − q 2 − ⋯ − q r − 2 u-w-p'_{ij}-q_2-\cdots-q_{r-2} u − w − p ij ′ − q 2 − ⋯ − q r − 2 would be a rooted P r P_r P r from u u u into Y Y Y , a contradiction. So we may assume that the representative p i j ′ p'_{ij} p ij ′ sends no rooted P r − 2 P_{r-2} P r − 2 into Z j ( 2 ) Z_j^{(2)} Z j ( 2 ) . In particular, p i j ′ p'_{ij} p ij ′ sends no rooted P max ( r − 2 , 5 ) P_{\max(r-2,5)} P m a x ( r − 2 , 5 ) into Z j ( 2 ) Z_j^{(2)} Z j ( 2 ) .
Since c ≥ 6 d 0 c \ge6d_0 c ≥ 6 d 0 , m ≥ 64 m \ge64 m ≥ 64 , and 0 < ρ ≤ 1 0 < \rho\le1 0 < ρ ≤ 1 , we have ∣ Z j ( 2 ) ∣ ≥ ∣ Z j ∣ / ( 2 m 2 d 0 ) ≥ ( m / ρ ) c / ( 2 m 2 d 0 ) ≥ ( 64 m 2 / ρ ) d 0 = a 1 − d 0 |Z_j^{(2)}| \ge|Z_j|/(2m^{2d_0}) \ge(m/\rho)^c/(2m^{2d_0}) \ge(64m^2/\rho)^{d_0} = a_1^{-d_0} ∣ Z j ( 2 ) ∣ ≥ ∣ Z j ∣/ ( 2 m 2 d 0 ) ≥ ( m / ρ ) c / ( 2 m 2 d 0 ) ≥ ( 64 m 2 / ρ ) d 0 = a 1 − d 0 . We may therefore apply R max ( r − 2 , 5 ) R_{\max}(r-2,5) R m a x ( r − 2 , 5 ) to Z j ( 2 ) Z_j^{(2)} Z j ( 2 ) with parameters x = a 1 x = a_1 x = a 1 and y = 1 / m y = 1/m y = 1/ m , using these (fewer than m m m ) representatives as roots. Outside early outcomes, we get D j ′ ⊆ Z j ( 2 ) D'_j \subseteq Z_j^{(2)} D j ′ ⊆ Z j ( 2 ) with ∣ D j ′ ∣ ≥ ∣ Z j ( 2 ) ∣ / m d 0 |D'_j| \ge|Z_j^{(2)}|/m^{d_0} ∣ D j ′ ∣ ≥ ∣ Z j ( 2 ) ∣/ m d 0 on which each representative is complete or has fewer than a 1 ∣ D j ′ ∣ / 4 a_1|D'_j|/4 a 1 ∣ D j ′ ∣/4 neighbors. For each offending pair i < j i < j i < j , we delete vertices of D j ′ D'_j D j ′ as follows. If p i j ′ p'_{ij} p ij ′ is complete to D j ′ D'_j D j ′ , then delete the vertices of D j ′ D'_j D j ′ that are sparse towards i i i , thus, at most 2 β m d 0 ∣ D j ′ ∣ 2\beta m^{d_0}|D'_j| 2 β m d 0 ∣ D j ′ ∣ vertices. If p i j ′ p'_{ij} p ij ′ has fewer than a 1 ∣ D j ′ ∣ / 4 a_1|D'_j|/4 a 1 ∣ D j ′ ∣/4 neighbors in D j ′ D'_j D j ′ , then delete the vertices complete towards i i i , thus, fewer than a 1 ∣ D j ′ ∣ / 4 a_1|D'_j|/4 a 1 ∣ D j ′ ∣/4 , since they are adjacent to p i j ′ p'_{ij} p ij ′ . For fixed j j j , there are fewer than m m m offending pairs i < j i < j i < j , so the total number of vertices deleted from D j ′ D'_j D j ′ is at most m ( a 1 / 4 + 2 m d 0 β ) ∣ D j ′ ∣ m(a_1/4+2m^{d_0}\beta)|D'_j| m ( a 1 /4 + 2 m d 0 β ) ∣ D j ′ ∣ . Since m ( a 1 / 4 + 2 m d 0 β ) = ρ / ( 256 m ) + ρ / ( 2 12 m 2 d 0 + 9 ) ≤ 1 / 256 + 1 / 4096 < 1 / 2 m(a_1/4+2m^{d_0}\beta) = \rho/(256m)+\rho/(2^{12}m^{2d_0+9}) \le1/256+1/4096 < 1/2 m ( a 1 /4 + 2 m d 0 β ) = ρ / ( 256 m ) + ρ / ( 2 12 m 2 d 0 + 9 ) ≤ 1/256 + 1/4096 < 1/2 , fewer than half the vertices of D j ′ D'_j D j ′ are deleted. The remaining set Z j ( 3 ) Z_j^{(3)} Z j ( 3 ) therefore satisfies ∣ Z j ( 3 ) ∣ ≥ ∣ D j ′ ∣ / 2 ≥ ∣ Z j ( 2 ) ∣ / ( 2 m d 0 ) ≥ ∣ Z j ∣ / ( 4 m 3 d 0 ) |Z_j^{(3)}| \ge|D'_j|/2 \ge|Z_j^{(2)}|/(2m^{d_0}) \ge|Z_j|/(4m^{3d_0}) ∣ Z j ( 3 ) ∣ ≥ ∣ D j ′ ∣/2 ≥ ∣ Z j ( 2 ) ∣/ ( 2 m d 0 ) ≥ ∣ Z j ∣/ ( 4 m 3 d 0 ) . A vertex sparse towards i i i has fewer than β ′ ∣ Z i ( 3 ) ∣ < ∣ Z i ( 3 ) ∣ \beta'|Z_i^{(3)}| < |Z_i^{(3)}| β ′ ∣ Z i ( 3 ) ∣ < ∣ Z i ( 3 ) ∣ neighbors in Z i ( 3 ) Z_i^{(3)} Z i ( 3 ) . In particular, a vertex complete to Z i ( 3 ) Z_i^{(3)} Z i ( 3 ) has type complete towards i i i .
So the types satisfy the setting of Lemma 5.13 for W i = Z i ( 3 ) W_i = Z_i^{(3)} W i = Z i ( 3 ) and β ′ \beta' β ′ . Let A ′ A' A ′ be the ambiguity graph. Every edge of A ′ A' A ′ is ambiguous and hence an edge of J J J and not offending.
Claim 5.15.1. Let i 1 < ⋯ < i p i_1 < \cdots< i_p i 1 < ⋯ < i p be an increasing path of A ′ A' A ′ and i = i a i = i_a i = i a , j = i a + 1 j = i_{a+1} j = i a + 1 be consecutive on it. Let ℓ \ell ℓ be a later vertex of the path. Then no vertex of Z ℓ ( 3 ) Z_\ell^{(3)} Z ℓ ( 3 ) is complete towards j j j and sparse towards i i i .
Proof of Claim 5.15.1. The path is also an increasing path of J J J , so by Definition 5.10 (F4), some u ∈ R j u \in R_j u ∈ R j is anticomplete to Z ℓ ⊇ Z ℓ ( 3 ) Z_\ell\supseteq Z_\ell^{(3)} Z ℓ ⊇ Z ℓ ( 3 ) . If some w ∈ Z ℓ ( 3 ) w \in Z_\ell^{(3)} w ∈ Z ℓ ( 3 ) were complete towards j j j and sparse towards i i i , then ( ℓ , w , u ) (\ell,w,u) ( ℓ , w , u ) would witness that i j ij ij is offending, since ℓ > j \ell> j ℓ > j , w ∈ Z ℓ ( 3 ) ⊆ Z ℓ ( 2 ) w \in Z_\ell^{(3)} \subseteq Z_\ell^{(2)} w ∈ Z ℓ ( 3 ) ⊆ Z ℓ ( 2 ) , and u ∈ R j u \in R_j u ∈ R j is nonadjacent to w w w . This is impossible since i j ∈ E ( A ′ ) ij \in E(A') ij ∈ E ( A ′ ) and no edge of A ′ A' A ′ is offending. ▪
By Claim 5.15.1 and Lemma 5.13 with k ′ = ⌊ m ⌋ k' = \lfloor\sqrt{m}\rfloor k ′ = ⌊ m ⌋ , we obtain a k ′ k' k ′ -semisparse blockade of length k ′ k' k ′ and width at least min i ∣ Z i ( 3 ) ∣ / k ′ ≥ n / ( 4 m b + 3 d 0 k ′ ) \min_i |Z_i^{(3)}|/k' \ge n/(4m^{b+3d_0}k') min i ∣ Z i ( 3 ) ∣/ k ′ ≥ n / ( 4 m b + 3 d 0 k ′ ) . Since k ′ ≤ m k' \le m k ′ ≤ m and β ′ = ρ / ( 2 12 m 2 d 0 + 10 ) \beta' = \rho/(2^{12}m^{2d_0+10}) β ′ = ρ / ( 2 12 m 2 d 0 + 10 ) , we have k ′ β ′ ≤ ρ k'\beta' \le\rho k ′ β ′ ≤ ρ , so this blockade is ρ \rho ρ -semisparse.
It remains to verify that each possible outcome satisfies Definition 5.12 . The bounds above imply that the input set of each application has at least n / ( 2 m b + 2 d 0 ) n/(2m^{b+2d_0}) n / ( 2 m b + 2 d 0 ) vertices. An early (R2) outcome gives a z 4 z^4 z 4 -restricted set T T T with z ∈ [ a 0 4 , 1 / m ] ⊆ [ ( ρ / m ) c , 1 / m ] z \in[a_0^4,1/m] \subseteq[(\rho/m)^c,1/m] z ∈ [ a 0 4 , 1/ m ] ⊆ [( ρ / m ) c , 1/ m ] . Its size satisfies ∣ T ∣ ≥ z d 0 n / ( 2 m b + 2 d 0 ) ≥ z b + 3 d 0 + 1 n ≥ z c + b n |T| \ge z^{d_0}n/(2m^{b+2d_0}) \ge z^{b+3d_0+1}n \ge z^{c+b}n ∣ T ∣ ≥ z d 0 n / ( 2 m b + 2 d 0 ) ≥ z b + 3 d 0 + 1 n ≥ z c + b n . An early (R3) outcome gives a ρ \rho ρ -semisparse blockade whose length satisfies K ∈ [ m , a 0 − d 0 ] ⊆ [ m 1 / 4 , ( m / ρ ) c ] K \in[m,a_0^{-d_0}] \subseteq[m^{1/4},(m/\rho)^c] K ∈ [ m , a 0 − d 0 ] ⊆ [ m 1/4 , ( m / ρ ) c ] . Its width is at least n / ( 2 m b + 2 d 0 K d 0 ) ≥ n / K b + 3 d 0 + 1 ≥ n / K 4 b n/(2m^{b+2d_0}K^{d_0}) \ge n/K^{b+3d_0+1} \ge n/K^{4b} n / ( 2 m b + 2 d 0 K d 0 ) ≥ n / K b + 3 d 0 + 1 ≥ n / K 4 b . The final blockade has length K = k ′ = ⌊ m ⌋ K=k'=\lfloor\sqrt{m}\rfloor K = k ′ = ⌊ m ⌋ , with m 1 / 4 ≤ K ≤ ( m / ρ ) c m^{1/4} \le K \le(m/\rho)^c m 1/4 ≤ K ≤ ( m / ρ ) c . Since m ≤ K 3 m \le K^3 m ≤ K 3 and K ≥ 4 K \ge4 K ≥ 4 , its width is at least n / ( 4 m b + 3 d 0 K ) ≥ n / ( 4 K 3 b + 9 d 0 + 1 ) ≥ n / K 3 b + 9 d 0 + 2 ≥ n / K 4 b n/(4m^{b+3d_0}K) \ge n/(4K^{3b+9d_0+1}) \ge n/K^{3b+9d_0+2} \ge n/K^{4b} n / ( 4 m b + 3 d 0 K ) ≥ n / ( 4 K 3 b + 9 d 0 + 1 ) ≥ n / K 3 b + 9 d 0 + 2 ≥ n / K 4 b . This proves Lemma 5.15. □
Proof of Theorems 5.4 and 5.5
Theorem 5.16. Let r ≥ 5 r \ge5 r ≥ 5 and let C \mathcal{C} C be a hereditary class with the frontier property of order r r r with constant c c c , such that O r − 1 ( C ) \mathcal{O}_{r-1}(\mathcal{C}) O r − 1 ( C ) has Erdős–Hajnal exponent κ ∈ ( 0 , 1 ] \kappa\in(0,1] κ ∈ ( 0 , 1 ] . Let g = max ( 2 , 1 / κ ) g = \max(2,1/\kappa) g = max ( 2 , 1/ κ ) . Then C \mathcal{C} C satisfies R r R_r R r with constant d = ( c + 6 ) ( [ 4 g + 5 ] + 3 ) + c + 1 d = (c+6)([4g+5]+3)+c+1 d = ( c + 6 ) ([ 4 g + 5 ] + 3 ) + c + 1 .
Proof. The proof combines the cut-tree lemma, the frontier property, and the sampling lemma. We choose the parameters so that each outcome of the cut-tree lemma yields one of Definition 5.2 (R1)–(R3) with the bounds required by R r R_r R r .
Put d t = ⌈ 4 g + 5 ⌉ d_t=\lceil4g+5\rceil d t = ⌈ 4 g + 5 ⌉ and d 1 = 6 d t + 3 d_1=6d_t+3 d 1 = 6 d t + 3 . So d = ( c + 6 ) d 1 + c + 1 d=(c+6)d_1+c+1 d = ( c + 6 ) d 1 + c + 1 . Let x , y , G , U , Y , n x,y,G,U,Y,n x , y , G , U , Y , n be as in Definition 5.2 , and put t = ⌈ y − d t ⌉ t=\lceil y^{-d_t}\rceil t = ⌈ y − d t ⌉ . Then t ≥ 2 d t ≥ max ( 2 16 , 2 c ) t\ge2^{d_t}\ge\max(2^{16},2^c) t ≥ 2 d t ≥ max ( 2 16 , 2 c ) and t ≤ 2 y − d t ≤ x − d 1 t\le2y^{-d_t}\le x^{-d_1} t ≤ 2 y − d t ≤ x − d 1 .
We then apply Lemma 5.11 with μ = n / t 6 \mu=n/t^6 μ = n / t 6 and show that each of its outcomes yields one of (R1)–(R3) in Definition 5.2 .
(T1) gives (R1): the set S S S is x x x -clean for U U U , and since t ≤ 2 y − d t t\le2y^{-d_t} t ≤ 2 y − d t , 2 − 6 ≥ y 2^{-6}\ge y 2 − 6 ≥ y and d ≥ 6 d t + 1 d\ge6d_t+1 d ≥ 6 d t + 1 , we have ∣ S ∣ ≥ n / t 6 ≥ 2 − 6 y 6 d t n ≥ y 6 d t + 1 n ≥ y d n |S|\ge n/t^6\ge2^{-6}y^{6d_t}n\ge y^{6d_t+1}n\ge y^d n ∣ S ∣ ≥ n / t 6 ≥ 2 − 6 y 6 d t n ≥ y 6 d t + 1 n ≥ y d n .
(T2) gives (R3) with K = t ∈ [ 1 / y , x − d ] K=t\in[1/y,x^{-d}] K = t ∈ [ 1/ y , x − d ] : a complete blockade is x x x -semisparse, and n / t 7 ≥ n / K d n/t^7\ge n/K^d n / t 7 ≥ n / K d .
(T3) and (T4) give a rooted frontier with m m m blocks, where b = 6 b=6 b = 6 or b = 3 b=3 b = 3 respectively, and t ≤ m ≤ max ( t , 4 t 6 / x ) t\le m\le\max(t,4t^6/x) t ≤ m ≤ max ( t , 4 t 6 / x ) . Since y ≥ x y\ge x y ≥ x and 2 8 ≤ x − 2 2^8\le x^{-2} 2 8 ≤ x − 2 , 4 t 6 / x ≤ 2 8 y − 6 d t x − 1 ≤ x − 6 d t − 3 4t^6/x\le2^8y^{-6d_t}x^{-1}\le x^{-6d_t-3} 4 t 6 / x ≤ 2 8 y − 6 d t x − 1 ≤ x − 6 d t − 3 , and so m ≤ x − 6 d t − 3 = x − d 1 m\le x^{-6d_t-3}=x^{-d_1} m ≤ x − 6 d t − 3 = x − d 1 . We have m ≥ t ≥ 2 c m\ge t\ge2^c m ≥ t ≥ 2 c , and every block has at least n / m b n/m^b n / m b vertices. Since b ≤ 6 b\le6 b ≤ 6 , n ≥ x − d n\ge x^{-d} n ≥ x − d , m ≤ x − d 1 m\le x^{-d_1} m ≤ x − d 1 , and d − 6 d 1 = c ( d 1 + 1 ) + 1 d-6d_1=c(d_1+1)+1 d − 6 d 1 = c ( d 1 + 1 ) + 1 , we have
n m b ≥ n m 6 ≥ x − d + 6 d 1 = x − c ( d 1 + 1 ) − 1 ≥ x − c ( d 1 + 1 ) ≥ ( m / x ) c . \frac{n}{m^b}\ge\frac{n}{m^6}\ge x^{-d+6d_1}=x^{-c(d_1+1)-1}\ge x^{-c(d_1+1)}\ge(m/x)^c. m b n ≥ m 6 n ≥ x − d + 6 d 1 = x − c ( d 1 + 1 ) − 1 ≥ x − c ( d 1 + 1 ) ≥ ( m / x ) c .
Thus the frontier property applies with ρ = x \rho=x ρ = x . If the first alternative holds, there are z ∈ [ ( x / m ) c , 1 / m ] z\in[(x/m)^c,1/m] z ∈ [( x / m ) c , 1/ m ] and a z 4 z^4 z 4 -restricted set T ⊆ Y T\subseteq Y T ⊆ Y with ∣ T ∣ ≥ z c + b n |T|\ge z^{c+b}n ∣ T ∣ ≥ z c + b n . Since d ≥ c ( d 1 + 1 ) d\ge c(d_1+1) d ≥ c ( d 1 + 1 ) , the bounds on m m m give z ≥ ( x / m ) c ≥ x c ( d 1 + 1 ) ≥ x d z\ge(x/m)^c\ge x^{c(d_1+1)}\ge x^d z ≥ ( x / m ) c ≥ x c ( d 1 + 1 ) ≥ x d and z ≤ 1 / m ≤ 1 / t ≤ y z\le1/m\le1/t\le y z ≤ 1/ m ≤ 1/ t ≤ y . Moreover, b ≤ 6 b\le6 b ≤ 6 and d ≥ c + 6 d\ge c+6 d ≥ c + 6 imply ∣ T ∣ ≥ z c + b n ≥ z c + 6 n ≥ z d n |T|\ge z^{c+b}n\ge z^{c+6}n\ge z^d n ∣ T ∣ ≥ z c + b n ≥ z c + 6 n ≥ z d n , since z ≤ 1 z\le1 z ≤ 1 . Hence (R2) holds. If the second alternative holds, there is an x x x -semisparse blockade of length K ∈ [ m 1 / 4 , ( m / x ) c ] K\in[m^{1/4},(m/x)^c] K ∈ [ m 1/4 , ( m / x ) c ] and width at least n / K c + 4 b n/K^{c+4b} n / K c + 4 b . Since d t ≥ 4 d_t\ge4 d t ≥ 4 and d ≥ c ( d 1 + 1 ) d\ge c(d_1+1) d ≥ c ( d 1 + 1 ) , we have
1 y ≤ y − d t / 4 ≤ t 1 / 4 ≤ m 1 / 4 ≤ K ≤ ( m / x ) c ≤ x − c ( d 1 + 1 ) ≤ x − d . \frac{1}{y}\le y^{-d_t/4}\le t^{1/4}\le m^{1/4}\le K\le(m/x)^c\le x^{-c(d_1+1)}\le x^{-d}. y 1 ≤ y − d t /4 ≤ t 1/4 ≤ m 1/4 ≤ K ≤ ( m / x ) c ≤ x − c ( d 1 + 1 ) ≤ x − d .
Its width is at least n / K c + 4 b ≥ n / K c + 24 ≥ n / K d n/K^{c+4b}\ge n/K^{c+24}\ge n/K^d n / K c + 4 b ≥ n / K c + 24 ≥ n / K d , since b ≤ 6 b\le6 b ≤ 6 and d ≥ c + 24 d\ge c+24 d ≥ c + 24 . Hence (R3) holds.
(T5): let M ≥ 3 n / ( 8 t ) M\ge3n/(8t) M ≥ 3 n / ( 8 t ) be the total size of the negative layers. Each layer has fewer than n / t 6 n/t^6 n / t 6 vertices, so φ ≤ 8 / ( 3 t 5 ) ≤ 8 3 y 5 d t ≤ y 16 g + 16 \varphi\le8/(3t^5)\le\frac{8}{3}y^{5d_t}\le y^{16g+16} φ ≤ 8/ ( 3 t 5 ) ≤ 3 8 y 5 d t ≤ y 16 g + 16 . By (T5), every set X X X meeting each layer at most once induces a member of O r − 1 ( C ) O_{r-1}(\mathcal{C}) O r − 1 ( C ) , so hom ( G [ X ] ) ≥ ∣ X ∣ κ \operatorname{hom}(G[X])\ge|X|^\kappa hom ( G [ X ]) ≥ ∣ X ∣ κ . By Lemma 5.9 with ε = y 4 ≤ 2 − 4 ( g + 10 ) \varepsilon=y^4\le2^{-4(g+10)} ε = y 4 ≤ 2 − 4 ( g + 10 ) , there is a y 4 y^4 y 4 -restricted set of size at least y 8 g + 8 M ≥ y 8 g + d t + 10 n ≥ y d n y^{8g+8}M\ge y^{8g+d_t+10}n\ge y^d n y 8 g + 8 M ≥ y 8 g + d t + 10 n ≥ y d n , which is (R2) with z = y z=y z = y .
Finally d ≥ max ( 6 d t + 2 , c ( d 1 + 1 ) , c + 24 , 8 g + d t + 10 , g + 10 ) d\ge\max(6d_t+2,c(d_1+1),c+24,8g+d_t+10,g+10) d ≥ max ( 6 d t + 2 , c ( d 1 + 1 ) , c + 24 , 8 g + d t + 10 , g + 10 ) , which covers all the exponents used. □
Now we are ready to prove Theorems 5.4 and 5.5 , which we restate here for convenience.
Theorem 5.17. (Theorem 5.4 ) Every hereditary class satisfies R 5 R_5 R 5 with constant 2127 2127 2127 .
Proof. Let C \mathcal{C} C be any hereditary class. We claim that O 4 ( C ) O_4(\mathcal{C}) O 4 ( C ) has Erdős–Hajnal exponent 1 2 \frac{1}{2} 2 1 . Let G ∈ O 4 ( C ) G\in O_4(\mathcal{C}) G ∈ O 4 ( C ) with ordering v 1 , … , v n v_1,\ldots,v_n v 1 , … , v n . Suppose that a − b − c − d a-b-c-d a − b − c − d is an induced path of G ‾ \overline{G} G . If the earliest vertex of this P 4 P_4 P 4 is a a a or d d d , then this vertex would start a rooted P 4 P_4 P 4 into the later vertices. So the earliest vertex is b b b or c c c . Hence b < a b<a b < a or c < d c<d c < d , which satisfies the hypothesis of Theorem 2.6 for G ‾ \overline{G} G . Thus hom ( G ) = hom ( G ‾ ) ≥ ∣ G ∣ 1 / 2 \operatorname{hom}(G)=\operatorname{hom}(\overline{G})\ge|G|^{1/2} hom ( G ) = hom ( G ) ≥ ∣ G ∣ 1/2 . By Lemma 5.14 and Theorem 5.16 with c = 20 c=20 c = 20 and κ = 1 2 \kappa=\frac{1}{2} κ = 2 1 (so g = 2 g=2 g = 2 , d t = 13 d_t=13 d t = 13 , and d 1 = 81 d_1=81 d 1 = 81 ), C \mathcal{C} C satisfies R 5 R_5 R 5 with constant 26 ⋅ 81 + 21 = 2127 26\cdot81+21=2127 26 ⋅ 81 + 21 = 2127 . □
Theorem 5.18. (Theorem 5.5) Let r ≥ 6 r \ge6 r ≥ 6 and let C \mathcal{C} C be a hereditary class. Suppose that C \mathcal{C} C satisfies R r − 1 \mathrm{R}_{r-1} R r − 1 and R max ( r − 2 , 5 ) \mathrm{R}_{\max(r-2,5)} R m a x ( r − 2 , 5 ) , and that O r − 1 ( C ) \mathcal{O}_{r-1}(\mathcal{C}) O r − 1 ( C ) has the Erdős–Hajnal property. Then C \mathcal{C} C satisfies R r \mathrm{R}_r R r .
Proof. Let d 0 ≥ 2 d_0 \ge2 d 0 ≥ 2 be a common constant for R r − 1 \mathrm{R}_{r-1} R r − 1 and R max ( r − 2 , 5 ) \mathrm{R}_{\max(r-2,5)} R m a x ( r − 2 , 5 ) . By Lemma 5.15, C \mathcal{C} C has the frontier property of order r r r with constant d 0 ( 4 d 0 + 11 ) d_0(4d_0 + 11) d 0 ( 4 d 0 + 11 ) . By Theorem 5.16, C \mathcal{C} C satisfies R r \mathrm{R}_r R r . □ \square □
Proof of the main theorem
Throughout this section, fix s ≥ 6 s \ge6 s ≥ 6 and assume EH ( P s − 1 ) \operatorname{EH}(P_{s-1}) EH ( P s − 1 ) . Let G s \mathcal{G}_s G s be the class of P s ‾ \overline{P_s} P s -free graphs.
Lemma 6.1. Let r ≥ 5 r \ge5 r ≥ 5 . If G s \mathcal{G}_s G s satisfies R r \mathrm{R}_r R r , then O r ( G s ) \mathcal{O}_r(\mathcal{G}_s) O r ( G s ) has the local alternative.
Proof. Let d d d be the constant of R r \mathrm{R}_r R r . We show that O r ( G s ) \mathcal{O}_r(\mathcal{G}_s) O r ( G s ) has the local alternative with constant D = max ( d + 2 , 4 ) D = \max(d + 2, 4) D = max ( d + 2 , 4 ) . Let 0 < x ≤ y ≤ 2 − D 0 < x \le y \le2^{-D} 0 < x ≤ y ≤ 2 − D and F ∈ O r ( G s ) F \in\mathcal{O}_r(\mathcal{G}_s) F ∈ O r ( G s ) be y 3 y^3 y 3 -sparse with n = ∣ F ∣ ≥ x − D n = |F| \ge x^{-D} n = ∣ F ∣ ≥ x − D . Order V ( F ) V(F) V ( F ) as in Definition 5.3, let Y Y Y be the set of the last ⌈ y n ⌉ \lceil yn\rceil ⌈ y n ⌉ vertices and U U U the set of the others. Every vertex of U U U precedes all of Y Y Y , so it sends no rooted P r P_r P r into Y Y Y . Since n ≥ x − D ≥ 1 / y n \ge x^{-D} \ge1/y n ≥ x − D ≥ 1/ y we have y n ≥ 1 yn \ge1 y n ≥ 1 . So y n ≤ ∣ Y ∣ ≤ y n + 1 ≤ 2 y n yn \le|Y| \le yn + 1 \le2yn y n ≤ ∣ Y ∣ ≤ y n + 1 ≤ 2 y n . Since D − 1 ≥ d D - 1 \ge d D − 1 ≥ d , ∣ Y ∣ ≥ y n ≥ x n ≥ x 1 − D ≥ x − d |Y| \ge yn \ge xn \ge x^{1-D} \ge x^{-d} ∣ Y ∣ ≥ y n ≥ x n ≥ x 1 − D ≥ x − d . Also x ≤ y ≤ 2 − D ≤ 2 − d x \le y \le2^{-D} \le2^{-d} x ≤ y ≤ 2 − D ≤ 2 − d . So the conditions of Definition 5.2 hold for F F F with x , y x,y x , y .
If Definition 5.2 (R1) holds, then there is a set X ⊆ Y X \subseteq Y X ⊆ Y that is x x x -clean for U U U and has ∣ X ∣ ≥ y d ∣ Y ∣ ≥ y d + 1 n |X| \ge y^d|Y| \ge y^{d+1}n ∣ X ∣ ≥ y d ∣ Y ∣ ≥ y d + 1 n . Fix a vertex p ∈ X p \in X p ∈ X . Every vertex complete to X X X is a neighbor of p p p , and p p p has at most y 3 n y^3n y 3 n neighbors as F F F is y 3 y^3 y 3 -sparse. So at most y 3 n y^3n y 3 n vertices of U U U are complete to X X X . Since X X X is x x x -clean for U U U , the other vertices of U U U have fewer than x ∣ X ∣ / 4 x|X|/4 x ∣ X ∣/4 neighbors in X X X . Let Z = { u ∈ U : ∣ N F ( u ) ∩ X ∣ < x ∣ X ∣ / 4 } Z = \{u \in U : |N_F(u) \cap X| < x|X|/4\} Z = { u ∈ U : ∣ N F ( u ) ∩ X ∣ < x ∣ X ∣/4 } . Then X X X and Z Z Z are disjoint, Z Z Z is x x x -sparse to X X X , and ∣ Z ∣ ≥ ∣ U ∣ − y 3 n ≥ ( 1 − 4 y ) n |Z| \ge|U| - y^3n \ge(1 - 4y)n ∣ Z ∣ ≥ ∣ U ∣ − y 3 n ≥ ( 1 − 4 y ) n . Since ∣ X ∣ ≥ y d + 1 n ≥ y D n |X| \ge y^{d+1}n \ge y^Dn ∣ X ∣ ≥ y d + 1 n ≥ y D n , Definition 4.1 (O3) holds.
If Definition 5.2 (R2) holds, then there is a z d z^d z d -restricted set with z ∈ [ x d , y ] z \in[x^d,y] z ∈ [ x d , y ] and at least z d ∣ Y ∣ ≥ z d y n ≥ z d + 1 n z^d|Y| \ge z^dyn \ge z^{d+1}n z d ∣ Y ∣ ≥ z d y n ≥ z d + 1 n vertices (as z ≤ y z \le y z ≤ y ), which gives Definition 4.1 (O4).
If Definition 5.2 (R3) holds, then there is an x x x -semisparse (hence weakly x x x -semisparse) blockade of length K ∈ [ 1 / y , x − d ] K \in[1/y,x^{-d}] K ∈ [ 1/ y , x − d ] and width at least ∣ Y ∣ / K d ≥ y n / K d ≥ n / K d + 1 |Y|/K^d \ge yn/K^d \ge n/K^{d+1} ∣ Y ∣/ K d ≥ y n / K d ≥ n / K d + 1 (as y ≥ 1 / K y \ge1/K y ≥ 1/ K ), which gives Definition 4.1 (O2).
Thus O r ( G s ) \mathcal{O}_r(\mathcal{G}_s) O r ( G s ) has the local alternative. □ \square □
The next lemma takes the place of property ( ∗ ) (*) ( ∗ ) of [9 Section 4] and of the quantitative comb condition [15 Definition 7.1] .
Lemma 6.2. If G s \mathcal{G}_s G s satisfies R max ( s − 2 , 5 ) \mathrm{R}_{\max(s-2,5)} R m a x ( s − 2 , 5 ) , then G s \mathcal{G}_s G s has the local alternative.
Proof. Let r = max ( s − 2 , 5 ) r = \max(s-2, 5) r = max ( s − 2 , 5 ) and d d d be the constant of R r \mathrm{R}_r R r . We show G s \mathcal{G}_s G s has the local alternative with constant D = 3 d + 10 D = 3d + 10 D = 3 d + 10 . Let 0 < x ≤ y ≤ 2 − D 0 < x \le y \le2^{-D} 0 < x ≤ y ≤ 2 − D and G ∈ G s G \in\mathcal{G}_s G ∈ G s be y 3 y^3 y 3 -sparse with n = ∣ G ∣ ≥ x − D n = |G| \ge x^{-D} n = ∣ G ∣ ≥ x − D . By applying Lemma 2.4 with these x , y x,y x , y , there is an ( ℓ , y 4 n / ℓ 2 ) (\ell,y^4n/\ell^2) ( ℓ , y 4 n / ℓ 2 ) -comb ( a i , B i ) : i ∈ [ ℓ ] (a_i,B_i) : i \in[\ell] ( a i , B i ) : i ∈ [ ℓ ] with ℓ ∈ [ 1 / y , x − 2 ] \ell\in[1/y,x^{-2}] ℓ ∈ [ 1/ y , x − 2 ] and a special vertex v v v , since the first two outcomes of Lemma 2.4 give Definition 4.1 (O3) and (O1). As y > 1 / ℓ y > 1/\ell y > 1/ ℓ , each ∣ B i ∣ ≥ n / ℓ 6 |B_i| \ge n/\ell^6 ∣ B i ∣ ≥ n / ℓ 6 .
Let U i = ⋃ j ≠ i B j U_i = \bigcup_{j \ne i} B_j U i = ⋃ j = i B j . In G ‾ \overline{G} G , the vertex v v v is adjacent to a i a_i a i and to no vertex of B i ∪ U i B_i \cup U_i B i ∪ U i , while a i a_i a i is adjacent to every vertex of U i U_i U i and to no vertex of B i B_i B i . If some u ∈ U i u \in U_i u ∈ U i sent a rooted P s − 2 P_{s-2} P s − 2 into B i B_i B i , then prefixing this path with v , a i v,a_i v , a i would give an induced P s P_s P s in G ‾ \overline{G} G , contrary to the fact that G ‾ \overline{G} G is P s P_s P s -free. Therefore no vertex of U i U_i U i sends a rooted P s − 2 P_{s-2} P s − 2 into B i B_i B i . Since r ≥ s − 2 r \ge s-2 r ≥ s − 2 , no vertex of U i U_i U i sends a rooted P r P_r P r into B i B_i B i .
Since x 3 ≤ 1 / ℓ ≤ y ≤ 2 − d x^3 \le1/\ell\le y \le2^{-d} x 3 ≤ 1/ ℓ ≤ y ≤ 2 − d and ∣ B i ∣ ≥ y 4 n / ℓ 2 ≥ x 8 n ≥ x − 3 d |B_i| \ge y^4n/\ell^2 \ge x^8n \ge x^{-3d} ∣ B i ∣ ≥ y 4 n / ℓ 2 ≥ x 8 n ≥ x − 3 d , the conditions of R r R_r R r hold for Y = B i Y = B_i Y = B i and the roots U = U i U = U_i U = U i with x , y x,y x , y replaced by x 3 , 1 / ℓ x^3,1/\ell x 3 , 1/ ℓ . If Definition 5.2 (R2) holds, then there is a z 4 z^4 z 4 -restricted set with z ∈ [ x 3 d , 1 / ℓ ] z \in[x^3d,1/\ell] z ∈ [ x 3 d , 1/ ℓ ] and at least z d ∣ B i ∣ ≥ z d + 6 n z^d|B_i| \ge z^{d+6}n z d ∣ B i ∣ ≥ z d + 6 n vertices, which gives Definition 4.1 (O4). If Definition 5.2 (R3) holds, then there is an x 3 x^3 x 3 -semisparse blockade of length K ∈ [ ℓ , x − 3 d ] K \in[\ell,x^{-3d}] K ∈ [ ℓ , x − 3 d ] and width at least ∣ B i ∣ / K d ≥ n / K d + 6 |B_i|/K^d \ge n/K^{d+6} ∣ B i ∣/ K d ≥ n / K d + 6 , and hence Definition 4.1 (O2) holds, since K ≥ ℓ ≥ 1 / y K \ge\ell\ge1/y K ≥ ℓ ≥ 1/ y .
So we may assume that Definition 5.2 (R1) holds for every i i i , giving S i ⊆ B i S_i \subseteq B_i S i ⊆ B i with ∣ S i ∣ ≥ ∣ B i ∣ / ℓ d ≥ n / ℓ d + 6 |S_i| \ge|B_i|/\ell^d \ge n/\ell^{d+6} ∣ S i ∣ ≥ ∣ B i ∣/ ℓ d ≥ n / ℓ d + 6 that is x 3 x^3 x 3 -clean for U i U_i U i . We claim that ( S 1 , … , S ℓ ) (S_1,\ldots,S_\ell) ( S 1 , … , S ℓ ) is a weakly x x x -semisparse blockade. Let θ = x 3 / 4 \theta= x^3/4 θ = x 3 /4 and i ≠ j i \ne j i = j . Since S j ⊆ B j ⊆ U i S_j \subseteq B_j \subseteq U_i S j ⊆ B j ⊆ U i , every vertex of S j S_j S j is a root for S i S_i S i . So by the cleanliness of S i S_i S i , every vertex of S j S_j S j is complete to S i S_i S i or has fewer than θ ∣ S i ∣ \theta|S_i| θ ∣ S i ∣ neighbors in S i S_i S i . Symmetrically, since S i ⊆ U j S_i \subseteq U_j S i ⊆ U j , every vertex of S i S_i S i is complete to S j S_j S j or has fewer than θ ∣ S j ∣ \theta|S_j| θ ∣ S j ∣ neighbors in S j S_j S j . Suppose ( S i , S j ) (S_i,S_j) ( S i , S j ) is not complete. Take nonadjacent p ∈ S i p \in S_i p ∈ S i , q ∈ S j q \in S_j q ∈ S j . Then q q q is not complete to S i S_i S i , so it has fewer than θ ∣ S i ∣ \theta|S_i| θ ∣ S i ∣ neighbors in S i S_i S i . In particular, fewer than θ ∣ S i ∣ \theta|S_i| θ ∣ S i ∣ vertices of S i S_i S i are complete to S j S_j S j . Every other vertex of S i S_i S i is not complete to S j S_j S j , so it has fewer than θ ∣ S j ∣ \theta|S_j| θ ∣ S j ∣ neighbors in S j S_j S j . Hence there are fewer than 2 θ ∣ S i ∣ ∣ S j ∣ ≤ x ∣ S i ∣ ∣ S j ∣ 2\theta|S_i||S_j| \le x|S_i||S_j| 2 θ ∣ S i ∣∣ S j ∣ ≤ x ∣ S i ∣∣ S j ∣ edges between S i S_i S i and S j S_j S j . This gives Definition 4.1 (O2) with k = ℓ k=\ell k = ℓ .
All exponents above are at most 3 d + 10 3d+10 3 d + 10 , which proves the lemma. □
Now we are ready to prove Theorem 1.1 .
Proof of Theorem 1.1. We prove by induction on s s s . For s ≤ 4 s \le4 s ≤ 4 the result is classical and EH ( P 5 ) \operatorname{EH}(P_5) EH ( P 5 ) follows from [12 ] . So we may assume that EH ( P s − 1 ) \operatorname{EH}(P_{s-1}) EH ( P s − 1 ) .
We claim that G s \mathcal{G}_s G s satisfies R r R_r R r for 5 ≤ r ≤ max { s − 2 , 5 } 5 \le r \le\max\{s-2,5\} 5 ≤ r ≤ max { s − 2 , 5 } . We prove this by induction on r r r . For r = 5 r=5 r = 5 , this is Theorem 5.4 . Let 6 ≤ r ≤ s − 2 6 \le r \le s-2 6 ≤ r ≤ s − 2 and suppose G s \mathcal{G}_s G s satisfies R r − 1 R_{r-1} R r − 1 and R max ( r − 2 , 5 ) R_{\max(r-2,5)} R m a x ( r − 2 , 5 ) . By Lemma 6.1, O r − 1 ( G s ) \mathcal{O}_{r-1}(\mathcal{G}_s) O r − 1 ( G s ) has the local alternative. Since O r − 1 ( G s ) \mathcal{O}_{r-1}(\mathcal{G}_s) O r − 1 ( G s ) is a hereditary class of P s ‾ \overline{P_s} P s -free graphs, O r − 1 ( G s ) \mathcal{O}_{r-1}(\mathcal{G}_s) O r − 1 ( G s ) has the Erdős–Hajnal property by Theorem 4.2 . So Theorem 5.5 shows that G s \mathcal{G}_s G s satisfies R r R_r R r . Thus, G s \mathcal{G}_s G s satisfies R max { s − 2 , 5 } R_{\max\{s-2,5\}} R m a x { s − 2 , 5 } . By Lemma 6.2 and Theorem 4.2 , G s \mathcal{G}_s G s has the Erdős–Hajnal property. Hence EH ( P s ‾ ) \operatorname{EH}(\overline{P_s}) EH ( P s ) holds, which is equivalent to EH ( P s ) \operatorname{EH}(P_s) EH ( P s ) . □
Acknowledgements
The proof presented in this paper was developed through an interactive dialogue with Claude Opus 5.5 (Anthropic) and ChatGPT-6 (OpenAI). The authors used them to explore multiple possible proof strategies and directions, and the AI generated the initial draft under the authors’ guidance. The authors then critically examined the generated proof, verified each step for correctness and rigor, and revised it where necessary. The authors take full responsibility for the final content.