The Structural Criterion for Property (*)

Since $\mathrm{\mid }{Y}_i\mathrm{\mid }\ge w\mathrm{/}2>0$, [F1] and [F2] give a clique or stable set in $G[Y_i]$, hence in $G$, with at least $(w\mathrm{/}2{)}^c$ vertices.

As $w\ge 4$, we have $w\mathrm{/}2\ge \sqrt{w}>0$; raising this inequality to the positive exponent $c$ and using [F3] gives $(w\mathrm{/}2{)}^c\ge (\sqrt{w}{)}^c=w^{c\mathrm{/}2}$.

The set from step 1.1 therefore has at least $w^{c\mathrm{/}2}$ vertices, which is the claimed clique-or-stable-set outcome.

The selected sets lie in distinct, hence disjoint, comb blocks. Fix $i\mathrm{\ne }k$. By [F1], every vertex of $A_{j_k}^k\subseteq B_k$ is individually complete or anticomplete to $A_{j_i}^i$. If two such vertices had opposite relations, then any vertex of the nonempty set $A_{j_i}^i$ would be mixed on $A_{j_k}^k$, contradicting [F1] applied with $i$ and $k$ reversed. Hence the relation is uniform and the pair of selected blocks is pure.

Thus the selected sequence is a pure blockade of length $\mathrm{\ell }$ and width at least $w\mathrm{/}(2\mathrm{\ell })$ by [F2].

Since $\mathrm{\ell }\ge 4$, $2\mathrm{\ell }\le {\mathrm{\ell }}^2$, so $w\mathrm{/}(2\mathrm{\ell })\ge w\mathrm{/}{\mathrm{\ell }}^2$. Step 2.1 and [F2] give the asserted pure $(\mathrm{\ell },w\mathrm{/}{\mathrm{\ell }}^2)$-blockade.

By the contrapositive of [F1], every $Y_i$ has size less than $w\mathrm{/}2$. Since $\mathrm{\mid }{B}_i\mathrm{\mid }\ge w$ and by [F3], every $X_i$ has size at least $w\mathrm{/}2$.

Suppose every partition had a block of size at least $w\mathrm{/}(2\mathrm{\ell })$. Then [F2] would give the excluded pure blockade. Hence some index $i$ has every $A_j^i$ of size less than $w\mathrm{/}(2\mathrm{\ell })$, and thus at most that bound.

For this $i$, [F3] and step 1.1 give $w\mathrm{/}2\le \mathrm{\mid }{X}_i\mathrm{\mid }={\sum }_{j=1}^{t_i}\mathrm{\mid }{A}_j^i\mathrm{\mid }\le t_{i}w\mathrm{/}(2\mathrm{\ell })$, hence $t_i\ge \mathrm{\ell }$.

Choose an integer $N>t$; then ${\mathrm{\ell }}^{N\mathrm{/}2}\ge 2^{N\mathrm{/}2}>t$, so $m_N=t$ by [F1]. Thus the set of indices attaining $t$ is nonempty, and [F3] supplies the least one $q$.

The upper bound $m_r\le {\mathrm{\ell }}^{r\mathrm{/}2}$ is part of [F1]. First let $r<q$ and write $x:={\mathrm{\ell }}^{r\mathrm{/}2}\ge 2$. Then $m_r<t$, so maximality in [F1] gives $x<m_r+1$. If $m_r<\sqrt{x}$, then $m_r^2<x<m_r+1$; but $m_r\ge 2$ and $m_r^2\ge m_r+1$, a contradiction. Thus $m_r\ge \sqrt{x}={\mathrm{\ell }}^{r\mathrm{/}4}$ by [F2]. For the terminal cutoff, $m_1\le \sqrt{\mathrm{\ell }}<\mathrm{\ell }\le t$, so $q\ge 2$. Put $y:={\mathrm{\ell }}^{(q-1)\mathrm{/}2}$. Since $m_{q-1}<t$ and $m_{q-1}$ is the largest integer at most $y$, integrality gives $t\ge m_{q-1}+1>y\ge {\mathrm{\ell }}^{q\mathrm{/}4}$. Hence $m_q=t\ge {\mathrm{\ell }}^{q\mathrm{/}4}$ as well.

Fix $2\le r\le q$. Minimality of $q$ gives $m_{r-1}<t$. Put $x={\mathrm{\ell }}^{(r-1)\mathrm{/}2}\ge 1$. Since $m_{r-1}\le x$ and ${\mathrm{\ell }}^{r\mathrm{/}2}=\sqrt{\mathrm{\ell }}x\ge 2x\ge x+1$, the integer $m_{r-1}+1$ is at most both $t$ and ${\mathrm{\ell }}^{r\mathrm{/}2}$. It is therefore admissible in the maximum defining $m_r$, so $m_r\ge m_{r-1}+1$. Also $m_1\ge 1$; hence every layer is nonempty and the successive index intervals cover exactly $[t]$.

Steps 1.1--2.1 prove existence, coverage, nonemptiness, and both cutoff bounds.

The selected sequence has $\mathrm{\mid }S\mathrm{\mid }$ pairwise disjoint nonempty blocks of size at least $s$ by [F3].

If $S$ is a clique, each pair of its pattern vertices is adjacent, so [F1] makes every selected pair complete. Thus [F2] makes the sequence a complete $(\mathrm{\mid }S\mathrm{\mid },s)$-blockade.

If $S$ is a stable set, no selected pattern pair is adjacent. Since the original blockade is pure, [F1] makes every selected pair anticomplete; [F2] therefore gives an anticomplete $(\mathrm{\mid }S\mathrm{\mid },s)$-blockade.

The clique and stable-set cases exhaust the stated alternatives.

The induced pattern on the first $m_r$ blocks is ${\mathcal{F}}_2$-free: an induced forbidden copy there would also be one in the full pattern. By [F1] and [F3], it has a clique or stable set $S$ of cardinality $k\ge m_r^c$.

From [F2] and step 1.1, $k\ge ({\mathrm{\ell }}^{r\mathrm{/}4}{)}^c={\mathrm{\ell }}^{cr\mathrm{/}4}$ by [F5].

The blocks indexed by $S$ lie among the first $m_r$ blocks and therefore in layers through $C_r$; decreasing block sizes and the width assumption on $C_r$ give them size at least $w\mathrm{/}{\mathrm{\ell }}^{5r\mathrm{/}2}$. By [F4] they form a complete or anticomplete blockade of length $k$ and at least that width.

Step 2.1 and [F5] give $k^{10\mathrm{/}c}\ge {\mathrm{\ell }}^{5r\mathrm{/}2}$, so $w\mathrm{/}{\mathrm{\ell }}^{5r\mathrm{/}2}\ge w\mathrm{/}{k}^{10\mathrm{/}c}$. Together with step 2.2 this proves the claim.

The first-layer contribution is at most ${\mathrm{\ell }}^{1\mathrm{/}2}w\mathrm{/}(2\mathrm{\ell })=w\mathrm{/}(2\sqrt{\mathrm{\ell }})\le w\mathrm{/}4$.

A small block in $C_r$ has size less than $w\mathrm{/}{\mathrm{\ell }}^{5r\mathrm{/}2}$; by the nonincreasing order and [F2], every block in $C_{r+1}$ is no larger. Hence the contribution of $C_{r+1}$ is less than $w{\mathrm{\ell }}^{(r+1)\mathrm{/}2-5r\mathrm{/}2}=w{\mathrm{\ell }}^{1\mathrm{/}2-2r}$.

Since $\mathrm{\ell }\ge 4$, the sum of these latter bounds is at most $w{\sum }_{r\ge 1}{4}^{1\mathrm{/}2-2r}=\frac{w}{8}{\sum }_{s\ge 0}{16}^{-s}=\frac{2w}{15}$ by [F3].

Adding steps 1.1 and 2.1 gives $\mathrm{\mid }X\mathrm{\mid }<w(1\mathrm{/}4+2\mathrm{/}15)=23w\mathrm{/}60<w\mathrm{/}2$, as required.

Set $c_1=c_3=c\mathrm{/}4$ and $c_2=10\mathrm{/}c$. We verify the three alternatives required by [F1] for an arbitrary given comb.

Suppose outcome one and outcome three both fail. By [F3], choose the resulting partition of some $X_i$ and relabel its finitely many blocks in nonincreasing order of size. Relabelling preserves the partition, its block bounds, purity, and the isomorphism type of its pattern graph, as well as the cross-block condition in the structural hypothesis. The relabelled partition is therefore decreasing and still structural; form its integral layers.

Otherwise every preterminal layer has a block below its threshold; [F5] then gives $\mathrm{\mid }{X}_i\mathrm{\mid }<w\mathrm{/}2$, contradicting [F3].

If some $Y_i$ has size at least $w\mathrm{/}2$, [F2] gives a clique or stable set of size at least $w^{c\mathrm{/}2}\ge w^{c\mathrm{/}4}=w^{c_1}$; this is outcome one.

If a preterminal layer $C_r$ is wide at the threshold $w\mathrm{/}{\mathrm{\ell }}^{5r\mathrm{/}2}$, [F4] gives a complete or anticomplete blockade of width at least $w\mathrm{/}{k}^{c_2}$. Since $r\ge 1$, its length parameter satisfies $k\ge {\mathrm{\ell }}^{cr\mathrm{/}4}\ge {\mathrm{\ell }}^{c\mathrm{/}4}={\mathrm{\ell }}^{c_3}$, so outcome two holds.

Thus failure of outcomes one and three forces outcome two, while step 2.1 handles the remaining case. The three outcomes in [F1] therefore always hold, proving property $(\ast )$.