Iterative Sparsification and the Five-Vertex Path

Partition the anticonnected components into a minimum number of unions $S_0,\dots ,S_r$, each of size less than $n\mathrm{/}k$, and order them so that $\mathrm{\mid }{S}_0\mathrm{\mid }\le \cdots \le \mathrm{\mid }{S}_r\mathrm{\mid }$. Since their union has size $n$, one has $r+1>k$.

For every $i\ge 1$, minimality gives $\mathrm{\mid }{S}_{i-1}\mathrm{\mid }+\mathrm{\mid }{S}_i\mathrm{\mid }\ge n\mathrm{/}k$; otherwise these two parts could be merged. The ordering then yields $\mathrm{\mid }{S}_i\mathrm{\mid }\ge n\mathrm{/}(2k)$. Thus $S_1,\dots ,S_r$ contain at least $k$ nonempty blocks of width at least $n\mathrm{/}(2k)$, and [L1] makes every cross-pair complete. Selecting any $\lceil k\mathrm{/}2\rceil$ of them proves the statement.

If $\lceil 1\mathrm{/}x\rceil \ge \mathrm{\mid }A\mathrm{\mid }$, take $S:=A$ and every neighbourhood in $A$ is hit. Otherwise let $m:=\lceil 1\mathrm{/}x\rceil <\mathrm{\mid }A\mathrm{\mid }$ and choose a subset $S\subseteq A$ uniformly among all subsets of size $m$. For a fixed vertex $b\in B$, the probability that $S\cap N(b)=\mathrm{\varnothing }$ is at most $(1-x{)}^m\le e^{-xm}\le e^{-1}<1\mathrm{/}2$.

In the first case every vertex of $B$ is hit. In the second case the expected number of vertices of $B$ whose neighbourhood misses $S$ is less than $\mathrm{\mid }B\mathrm{\mid }\mathrm{/}2$, so some choice of $S$ misses fewer than half of $B$. Thus in either case there is a set $S\subseteq A$ with $\mathrm{\mid }S\mathrm{\mid }\le \lceil 1\mathrm{/}x\rceil$ that meets the neighbourhood of at least half of the vertices of $B$.

The cited source lemma assumes the negation of the desired blockade, first obtains a connected component of size at least $\mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}2$, and then obtains two further large connected pieces outside successive neighbourhoods.

The source shows that the absence of the blockade then forces five selected vertices to induce $P_5$, contradicting the hypothesis. Therefore the stated anticomplete two-blockade exists.

The cited source claim proves exactly this large nearly covered sparse-pair conclusion after translating notation.

Therefore the present statement follows.

Fix $i\in [k]$ and put $n_i:=\mathrm{\mid }{B}_i\mathrm{\mid }$. Suppose first that every anticonnected component of $G[B_i]$ has size less than $n_i\mathrm{/}k$. Partition the anticonnected components into a minimum number of unions $S_0,\dots ,S_r$, each of size less than $n_i\mathrm{/}k$, and order them by nondecreasing size. Since the parts cover $B_i$, one has $r+1>k$. Minimality gives $\mathrm{\mid }{S}_{j-1}\mathrm{\mid }+\mathrm{\mid }{S}_j\mathrm{\mid }\ge n_i\mathrm{/}k$ for $j\ge 1$, and hence $\mathrm{\mid }{S}_j\mathrm{\mid }\ge n_i\mathrm{/}(2k)\ge n_i\mathrm{/}{k}^2$ because $k\ge 4$. By [L1], the sets $S_1,\dots ,S_k$ are pairwise complete. They therefore form a complete, hence pure, $(k,n_i\mathrm{/}{k}^2)$-blockade in $G[B]$. By [F1], $n_i\mathrm{/}{k}^2\ge \mathrm{\mid }B\mathrm{\mid }\mathrm{/}{k}^{10}$, which proves the result in this case.

We may consequently assume that, for every $i\in [k]$, the graph $G[B_i]$ has an anticonnected component $D_i$ with $\mathrm{\mid }{D}_i\mathrm{\mid }\ge \mathrm{\mid }{B}_i\mathrm{\mid }\mathrm{/}k$. Choose one such $D_i$. Then $\mathrm{\mid }{D}_i\mathrm{\mid }\ge \mathrm{\mid }{B}_i\mathrm{\mid }\mathrm{/}k\ge \mathrm{\mid }B\mathrm{\mid }\mathrm{/}{k}^9\ge \mathrm{\mid }B\mathrm{\mid }\mathrm{/}{k}^{10}$, giving the required width bound for every chosen component.

Let $i\mathrm{\ne }j$, and suppose that some $u\in D_j$ is mixed on $D_i$. The sets of neighbours and nonneighbours of $u$ in $D_i$ are both nonempty. Since $\overline{G[D_i]}$ is connected, some edge of that complement crosses these two sets. Thus there are $w,z\in D_i$ such that $uw\in E(G)$, $uz\mathrm{\notin }E(G)$, and $wz\mathrm{\notin }E(G)$.

Among the five vertices $v,a_i,u,z,w$, the nonedges are exactly $v{a}_i,a_{i}u,uz,zw$. Indeed, the hypotheses on $v$ determine its four incidences; [F1] determines the incidences from $a_i$ to $D_i\subseteq B_i$ and to $u\in D_j\subseteq B_j$; and step 3.1 determines the three remaining incidences. Hence those four nonedges form the path $v-a_i-u-z-w$, so these vertices induce $\overline{P_5}$ by [F4] and [F5], contrary to the hypothesis on $G$. Therefore no vertex of $D_j$ is mixed on $D_i$.

Applying step 4.1 with both orders of $i,j$ shows that no vertex of either set is mixed on the other. If the pair $(D_i,D_j)$ had both an edge and a nonedge, then the vertices of $D_j$ would include one complete to $D_i$ and one anticomplete to $D_i$; every endpoint in $D_i$ of the cross-edge would then be mixed on $D_j$, a contradiction. Thus $(D_i,D_j)$ is pure.

The sets $D_1,\dots ,D_k$ are pairwise disjoint subsets of $B$, have size at least $\mathrm{\mid }B\mathrm{\mid }\mathrm{/}{k}^{10}$ by step 2.1, and every cross-pair is pure by step 5.1. Hence they form the required pure $(k,\mathrm{\mid }B\mathrm{\mid }\mathrm{/}{k}^{10})$-blockade in $G[B]$.

The cited source lemma proves exactly the three displayed alternatives under these hypotheses.

Therefore the present trichotomy holds.

The cited source lemma applies the preceding sparse-pair trichotomy to the final block and uses the correctly oriented sparse relations to extend the blockade whenever the sparse-pair outcome occurs.

Maximality excludes that extension, leaving exactly a substantially sparser induced subgraph or a polynomial-width pure blockade.

Apply the corrected, well-formed reading of the cited source lemma recorded in [F1]. Its two alternatives are exactly outcomes 1 and 2, and [F2] records the minimal-threshold argument establishing them.

Therefore the present statement follows.

Let $D\ge 40$ be supplied by [L1], and set $d:=2D$. Fix $x$ and $G$ as in the Statement. Since $d\ge D$, one has $x<2^{-D}$ and $\mathrm{\mid }V(G)\mathrm{\mid }\ge x^{-D}$. Thus [L1] gives a real $r\in [2,x^{-1}]$ and a pure or $x$-sparse blockade whose actual length is at least $r$ and whose width is at least $\mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}{r}^D$.

Put $k:=\lfloor r\rfloor$. Then $k$ is an integer and $2\le k\le r\le x^{-1}$. The blockade's integral actual length, being at least $r$, is in particular at least $k$, as required by [F2].

Since $k\ge 2$ and $k\le r<k+1$, one has $r^D<(k+1{)}^D\le (3k\mathrm{/}2{)}^D\le k^{2D}=k^d$. Consequently $\mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}{r}^D\ge \mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}{k}^d$. The blockade from step 1.1 is therefore a pure or $x$-sparse $(k,\mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}{k}^d)$-blockade in the library's sense.

The chosen $d=2D$ satisfies $d\ge 40$, and steps 1.1--3.1 prove the stated conclusion for every admissible $x$ and $G$.

If the chosen layout had at least ${ϵ}^{-1}$ blocks, [L1] would make its blocks a blockade satisfying the conclusion of the surrounding theorem.

The enclosing counterexample excludes that conclusion, so the layout has fewer than ${ϵ}^{-1}$ blocks.

Suppose the local blockade inside $A$ had length $k<{ϵ}^{-1}$. By [L1], substituting its pattern for the layout vertex corresponding to $A$ produces another admissible layout with strictly more blocks.

This contradicts the maximal choice of the original layout. Hence the local blockade has length at least ${ϵ}^{-1}$.

The cited source theorem applies to the hypotheses above and produces a blockade of length at least ${ϵ}^{-1}$, width at least $x^{2d}\mathrm{\mid }V(G)\mathrm{\mid }$, and complete-or-weakly-${ϵ}^d$-sparse cross-pairs.

Since blockade length is integral, length at least ${ϵ}^{-1}$ is equivalent to length at least $\lceil {ϵ}^{-1}\rceil$. This is exactly the stated conclusion.

Let $d$ be a common exponent large enough to dominate the polynomial width bound in [L1] and the layout theorem [L2]. Fix $ϵ\in (0,\frac{1}{2})$ and a $\overline{P_5}$-free graph $G$ with $\mathrm{\mid }V(G)\mathrm{\mid }\ge {ϵ}^{-10d^2}$, and set $x:={ϵ}^{5d}$. Then $x<2^{-d}$. If $F$ is an induced subgraph of $G$ with $\mathrm{\mid }V(F)\mathrm{\mid }\ge {ϵ}^d\mathrm{\mid }V(G)\mathrm{\mid }$, then $\mathrm{\mid }V(F)\mathrm{\mid }\ge {ϵ}^d{ϵ}^{-10d^2}={ϵ}^{-10d^2+d}\ge {ϵ}^{-5d^2}=x^{-d}\mathrm{.}$ Therefore [L1] applies to $F$ and gives a pure or $x$-sparse $(k,\mathrm{\mid }V(F)\mathrm{\mid }\mathrm{/}{k}^d)$-blockade for some $k\in [2,{ϵ}^{-5d^2}]$.

Applying [L2] to $G$ yields an $({ϵ}^{-1},{ϵ}^{10d^2}\mathrm{\mid }V(G)\mathrm{\mid })$-blockade whose distinct block pairs are either complete or weakly ${ϵ}^d$-sparse. By [L3], this is exactly the niceness condition for $H=P_5$.

Therefore $P_5$ is nice.

The cited source claim yields exactly this semisparse-blockade or complete-blockade alternative after translating exponents into constants.

Therefore one of the two displayed outcomes holds.

The cited source claim proves exactly this mixed-block dichotomy after translating exponents into constants.

Therefore one of the two displayed outcomes holds.

Apply [F1] to the graph in the Given. Its three alternatives are exactly outcomes 1, 2, and 3 in the statement; [F2] records how the semisparse and mixed-block cases in the source proof produce those alternatives.

Therefore the present trichotomy holds.

The cited source lemma builds a maximal anticomplete blockade and verifies the size normalization needed before applying the preceding sparse trichotomy inside its last block.

Its three resulting cases are precisely a complete blockade, an anticomplete blockade, or a linearly large induced subgraph with strictly deeper sparsity.

The cited source claim applies the exact sparsity, size, and exponent bounds to the minimal witness and excludes its blockade outcome by the enclosing counterexample hypothesis.

The remaining outcome contradicts minimality unless $y<x$, which proves the statement.

The cited source lemma runs the minimal-threshold argument with all size and exponent bounds and proves the first alternative whenever the blockade alternative is absent.

Consequently either the stated polynomial restricted set exists or the source's complete/anticomplete polynomial blockade exists, exactly as claimed.

Let $a$ be as in [L1]. Fix $x\in (0,\frac{1}{2})$ and a $P_5$-free graph $G$. Then $\bar{G}$ is $\overline{P_5}$-free. Apply [L1] to every induced subgraph $F$ of $\bar{G}$ with $\mathrm{\mid }V(F)\mathrm{\mid }\ge x^{2a}\mathrm{\mid }V(G)\mathrm{\mid }$. If any such $F$ has an $x$-restricted set of size at least $x^a\mathrm{\mid }V(F)\mathrm{\mid }$, that set has size at least $x^{3a}\mathrm{\mid }V(G)\mathrm{\mid }$ and is also $x$-restricted in $G$.

Otherwise every such $F$ has the complete-or-anticomplete blockade supplied by [L1], so the hypothesis of [L2] holds for $\bar{G}$. Applying [L2] yields an $x$-restricted induced subgraph on at least $x^{3a}\mathrm{\mid }V(G)\mathrm{\mid }$ vertices; the same vertex set is $x$-restricted in $G$.

Therefore $P_5$ has the polynomial Rödl property.

Applying [L2] to the singleton family $\{P_5\}$ and using [L1], we conclude that $P_5$ has the Erdős-Hajnal property.

By [F1], the same holds for $\overline{P_5}$.

Therefore both $P_5$ and $\overline{P_5}$ have the Erdős-Hajnal property.