Blockades, Combs and Pattern Graphs

We prove the stronger inequality. [given] $\alpha (J)\omega (J)\ge q$ by induction on $q$. The cases $q=0$ and $q=1$ are immediate.

Assume $q\ge 2$. By [L1], write $V(J)=A\bigsqcup B$ with $A,B\mathrm{\ne }\mathrm{\varnothing }$ and $(A,B)$ pure. Put. [step 1.1, L1] $a=\alpha (J[A]),b=\alpha (J[B]),c=\omega (J[A]),d=\omega (J[B])\mathrm{.}$ The induction hypothesis gives $ac\ge \mathrm{\mid }A\mathrm{\mid }$ and $bd\ge \mathrm{\mid }B\mathrm{\mid }$.

If $(A,B)$ is complete, then. [step 2.1, algebra] $\omega (J)=c+d$ and $\alpha (J)=\max \{a,b\}$, whence $\alpha (J)\omega (J)=\max \{a,b\}(c+d)\ge ac+bd\ge \mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }=q\mathrm{.}$ If $(A,B)$ is anticomplete, then $\alpha (J)=a+b$ and $\omega (J)=\max \{c,d\}$, and the same calculation gives $\alpha (J)\omega (J)\ge ac+bd\ge q$.

The induction closes. Since. [step 1.1, step 3.1, algebra] $\max \{\alpha (J),\omega (J)\}\ge \sqrt{\alpha (J)\omega (J)}$, one obtains $\mathrm{hom}(J)\ge \sqrt{q}$.

By A $P_4$-free graph on $q$ vertices has a homogeneous set of size at least $\sqrt{q}$, the pattern graph $P(\mathcal{B})$ has a clique or stable set $I\subseteq [t]$ with $\mathrm{\mid }I\mathrm{\mid }\ge \sqrt{t}$.

If $I$ is a clique, then by the definition of the pattern graph every pair of blocks indexed by $I$ is complete, so $(B_i:i\in I)$ is a complete subblockade. If $I$ is a stable set, the same definition makes $(B_i:i\in I)$ anticomplete. In either case the width does not decrease when blocks are discarded.

Therefore $\mathcal{B}$ contains a complete or anticomplete subblockade of length at least $\sqrt{t}$ and of at least the original width.

Suppose for contradiction that $q<{ϵ}^{-2}$. Reorder the blocks so that $\mathrm{\mid }{A}_1\mathrm{\mid }={\max }_i\mathrm{\mid }{A}_i\mathrm{\mid }$. Then $q\mathrm{\mid }{A}_1{\mathrm{\mid }}^{1\mathrm{/}a}\ge {\sum }_{i=1}^q\mathrm{\mid }{A}_i{\mathrm{\mid }}^{1\mathrm{/}a}\ge \mathrm{\mid }G{\mathrm{\mid }}^{1\mathrm{/}a},$ so $\mathrm{\mid }{A}_1\mathrm{\mid }\ge \mathrm{\mid }G\mathrm{\mid }\mathrm{/}{q}^a\ge {ϵ}^{2a}\mathrm{\mid }G\mathrm{\mid }$. By the hypothesis on $G$, the induced subgraph $G[A_1]$ contains a complete or anticomplete $(k,\mathrm{\mid }{A}_1\mathrm{\mid }\mathrm{/}{k}^a)$-blockade $(B_1,\dots ,B_k)$ for some $k\in [2,{ϵ}^{-1}]$.

Replace the block $A_1$ by $B_1,\dots ,B_k$, and keep the other blocks $A_2,\dots ,A_q$. Because $(A_1,\dots ,A_q)$ was pure, every outside block is either complete or anticomplete to $A_1$, hence to each $B_j\subseteq A_1$. The new blockade is still pure, its pattern graph is obtained by substituting a complete or edgeless graph for the vertex corresponding to $A_1$, and so it is still $P_4$-free.

Every new block satisfies $\mathrm{\mid }{B}_j\mathrm{\mid }\ge \mathrm{\mid }{A}_1\mathrm{\mid }\mathrm{/}{k}^a\ge {ϵ}^a\mathrm{\mid }{A}_1\mathrm{\mid }\ge {ϵ}^{3a}\mathrm{\mid }G\mathrm{\mid }$, while ${\sum }_{j=1}^k\mathrm{\mid }{B}_j{\mathrm{\mid }}^{1\mathrm{/}a}\ge k{\left(\frac{\mathrm{\mid }{A}_1\mathrm{\mid }}{k^a}\right)}^{1\mathrm{/}a}=\mathrm{\mid }{A}_1{\mathrm{\mid }}^{1\mathrm{/}a}\mathrm{.}$ So the new blockade still satisfies the lower bound on every block and on the total $a$-mass, but it has $q-1+k>q$ blocks. This contradicts the maximality of $q$.

Therefore $q\ge {ϵ}^{-2}$.

Let $q$ be maximal subject to the existence of a pure blockade $(A_1,\dots ,A_q)$ whose pattern graph is $P_4$-free, every block has size at least ${ϵ}^{3a}\mathrm{\mid }G\mathrm{\mid }$, and ${\sum }_{i=1}^q\mathrm{\mid }{A}_i{\mathrm{\mid }}^{1\mathrm{/}a}\ge \mathrm{\mid }G{\mathrm{\mid }}^{1\mathrm{/}a}$. By A maximal pure blockade with large total $a$-mass must already have at least ${ϵ}^{-2}$ blocks, one has $q\ge {ϵ}^{-2}$.

By Pure blockades with $P_4$-free patterns contain complete or anticomplete subblockades of square-root length, this blockade has a complete or anticomplete subblockade indexed by a set $I\subseteq [q]$ with $\mathrm{\mid }I\mathrm{\mid }\ge \sqrt{q}\ge {ϵ}^{-1}$. For each $i\in I$, choose $S_i\subseteq A_i$ with $\mathrm{\mid }{S}_i\mathrm{\mid }=\lceil {ϵ}^{3a}\mathrm{\mid }G\mathrm{\mid }\rceil$, and put $S:={\bigcup }_{i\in I}{S}_i$. Then $\mathrm{\mid }S\mathrm{\mid }=\mathrm{\mid }I\mathrm{\mid }\lceil {ϵ}^{3a}\mathrm{\mid }G\mathrm{\mid }\rceil \ge {ϵ}^{3a}\mathrm{\mid }G\mathrm{\mid }$.

If the chosen subblockade is anticomplete, then every vertex of $S_i$ has neighbors in $S$ only inside $S_i$, so its degree in $G[S]$ is at most $\mathrm{\mid }{S}_i\mathrm{\mid }-1\le \mathrm{\mid }S\mathrm{\mid }\mathrm{/}\mathrm{\mid }I\mathrm{\mid }\le ϵ\mathrm{\mid }S\mathrm{\mid }$. Hence $S$ is $ϵ$-sparse, and therefore $ϵ$-restricted.

If the chosen subblockade is complete, then in the complement $\bar{G}[S]$ every vertex of $S_i$ has neighbors only inside $S_i$, so the same estimate shows that $\bar{G}[S]$ is $ϵ$-sparse. Therefore $G[S]$ is $ϵ$-dense, and again $ϵ$-restricted.

In either case $G$ has an $ϵ$-restricted induced subgraph on at least ${ϵ}^{3a}\mathrm{\mid }G\mathrm{\mid }$ vertices, namely $G[S]$.

Let $n$ be maximal such that $G$ has a blockade $(B_1,\dots ,B_n)$ with $\mathrm{\mid }{B}_i\mathrm{\mid }\ge y^{a+2}\mathrm{\mid }G\mathrm{\mid }$ for all $i$, with $\mathrm{\mid }{B}_n\mathrm{\mid }\ge (1-by{)}^n\mathrm{\mid }G\mathrm{\mid }$, and such that for every $i\in [n]$, either every later block is $x$-sparse to $B_i$ or every later block is complete to $B_i$. This is possible because $n=1$ and $B_1=V(G)$ already satisfy the conditions.

Suppose that $n<2y^{-1}$. Since $y\le c=2^{-4b}$, one has $by\le b{2}^{-4b}<1\mathrm{/}2$. For $t\in [0,1\mathrm{/}2]$ the elementary inequality $1-t\ge 2^{-2t}$ holds, so with $t=by$ we get $(1-by{)}^{2y^{-1}}\ge (2^{-2by}{)}^{2y^{-1}}=2^{-4b}=c$. Therefore $\mathrm{\mid }{B}_n\mathrm{\mid }\ge (1-by{)}^n\mathrm{\mid }G\mathrm{\mid }\ge c\mathrm{\mid }G\mathrm{\mid }$. Applying the hypothesis to the induced subgraph $G[B_n]$, choose disjoint $X,Y\subseteq B_n$ with $\mathrm{\mid }X\mathrm{\mid }\ge y^a\mathrm{\mid }{B}_n\mathrm{\mid }\ge y^{a+2}\mathrm{\mid }G\mathrm{\mid }$ and $\mathrm{\mid }Y\mathrm{\mid }\ge (1-by)\mathrm{\mid }{B}_n\mathrm{\mid }\ge (1-by{)}^{n+1}\mathrm{\mid }G\mathrm{\mid }$, and with $Y$ $x$-sparse or complete to $X$. Because $X\cup Y\subseteq B_n$, the relation of every earlier block $B_i$ to $B_n$ restricts to the same relation to both $X$ and $Y$. Hence $(B_1,\dots ,B_{n-1},X,Y)$ is a larger blockade of the same type, contradicting the maximality of $n$. So $n\ge 2y^{-1}$.

Let $Q$ be the set of indices $i$ such that every later block is $x$-sparse to $B_i$, and let $R$ be the set of indices $i$ such that every later block is complete to $B_i$. By construction every index lies in $Q\cup R$, so one of $Q$ or $R$ has cardinality at least $n\mathrm{/}2\ge y^{-1}$.

Since one of $\mathrm{\mid }Q\mathrm{\mid },\mathrm{\mid }R\mathrm{\mid }$ is an integer at least $y^{-1}$, step 3.1 makes that cardinality at least $\lceil y^{-1}\rceil$. [step 3.1, given] If it is $\mathrm{\mid }Q\mathrm{\mid }$, choose $\lceil y^{-1}\rceil$ indices from $Q$ in their inherited order; the corresponding blocks form an $x$-sparse blockade. If it is $\mathrm{\mid }R\mathrm{\mid }$, the same choice from $R$ gives a complete blockade. Every selected block has size at least $y^{a+2}\mathrm{\mid }G\mathrm{\mid }$ by step 1.1. Thus one of the two required blockades exists.

Therefore $G$ contains an $x$-sparse or complete $(\lceil y^{-1}\rceil ,y^{a+2}\mathrm{\mid }G\mathrm{\mid })$-blockade.