Quantitatively divisive finite families are viral

We first prove the local-blockade assertion. Fix a finite graph $Q$ on $N$ vertices, $0<ϵ<1\mathrm{/}2$, and $D\ge 1$. Put $x={ϵ}^{12D}$. Assume that every induced subgraph $F$ of $Q$ with $\mathrm{\mid }F\mathrm{\mid }\ge {ϵ}^{4D}N$ has an $x$-sparse blockade in $F$ or in its complement, of length at least some real $k\in [2,x^{-1}]$ and width at least $\mathrm{\mid }F\mathrm{\mid }\mathrm{/}{k}^D$. We claim that some $S\subseteq V(Q)$ has |S|\ge x^{D+1}N,\qquad \min\{e(Q[S]),e(\overline Q[S])\}\le\epsilon\binom{|S|}{2}.\tag{1} If $N\le x^{-D-1}$, any singleton works, so assume $N>x^{-D-1}$. In particular all block-width thresholds used below exceed one when required.

A layout is a cograph $J$ with pairwise disjoint nonempty blocks $(A_j:j\in V(J))$ of $Q$; vertices outside all blocks are permitted. A pair is undecided when both ends are in one block. All other pairs are decided. A decided pair is wrong if its ends lie in distinct blocks and their adjacency differs from that of the corresponding pair in $J$. Choose a layout satisfying |A_j|\ge\epsilon^{6D}N\quad(j\in J),\qquad \sum_{j\in J}|A_j|^{1/D}\ge N^{1/D},\qquad |\mathrm{wrong}|\le x|\mathrm{decided}|,\tag{2} with $\mathrm{\mid }J\mathrm{\mid }$ maximal. The one-block layout $A_1=V(Q)$ qualifies, and finiteness gives a maximum.

If $\mathrm{\mid }J\mathrm{\mid }\ge 4{ϵ}^{-2}$, [L1] supplies a clique or stable set $I\subseteq V(J)$ of size at least $2{ϵ}^{-1}$. Complement $Q,J$ together if needed, so $I$ is stable. From each $A_i$, $i\in I$, choose the same number $r=\lceil {ϵ}^{6D}N\rceil$ of vertices, and let $S$ be their union. Edges within these equal blocks account for at most $\mathrm{\mid }I{\mathrm{\mid }}^{-1}\left(\genfrac{}{}{0px}{}{\mathrm{\mid }S\mathrm{\mid }}{2}\right)$. Edges between them are wrong pairs and hence at most $x\left(\genfrac{}{}{0px}{}{N}{2}\right)$. Since $\mathrm{\mid }S\mathrm{\mid }=\mathrm{\mid }I\mathrm{\mid }r\ge 2{ϵ}^{6D-1}N$, their share of $\left(\genfrac{}{}{0px}{}{\mathrm{\mid }S\mathrm{\mid }}{2}\right)$ is at most $x{ϵ}^{2-12D}\mathrm{/}2={ϵ}^2\mathrm{/}2\le ϵ\mathrm{/}2$; the within-block share is at most $ϵ\mathrm{/}2$. Also $\mathrm{\mid }S\mathrm{\mid }\ge {ϵ}^{6D}N\ge x^{D+1}N$. This gives (1). We may therefore assume $\mathrm{\mid }J\mathrm{\mid }<4{ϵ}^{-2}$.

Let $A_1$ be a largest block. The power-sum condition in (2) and the bound on $\mathrm{\mid }J\mathrm{\mid }$ imply $\mathrm{\mid }{A}_1\mathrm{\mid }\ge ({ϵ}^2\mathrm{/}4{)}^{D}N\ge {ϵ}^{4D}N$. Apply the hypothesis in step 1.1 to $Q[A_1]$, complementing $Q,J$ if needed, to get an $x$-sparse blockade $(B_1,\dots ,B_t)$ of actual integer length $t\ge k$ for some real $k\in [2,x^{-1}]$, with $\mathrm{\mid }{B}_i\mathrm{\mid }\ge \mathrm{\mid }{A}_1\mathrm{\mid }\mathrm{/}{k}^D$. Suppose $t<\lceil 2\mathrm{/}ϵ\rceil$. Then $t<2\mathrm{/}ϵ$, and $k\le t$ gives $\mathrm{\mid }{B}_i\mathrm{\mid }\ge \mathrm{\mid }{A}_1\mathrm{\mid }\mathrm{/}{t}^D\ge (ϵ\mathrm{/}2{)}^D\mathrm{\mid }{A}_1\mathrm{\mid }\ge {ϵ}^{2D}\mathrm{\mid }{A}_1\mathrm{\mid }\ge {ϵ}^{6D}N$. Replace vertex $1$ of $J$ by $t$ pairwise nonadjacent vertices whose blocks are the $B_i$. By [F1] the new pattern remains a cograph; also ${\sum }_i\mathrm{\mid }{B}_i{\mathrm{\mid }}^{1\mathrm{/}D}\ge t(\mathrm{\mid }{A}_1\mathrm{\mid }\mathrm{/}{t}^D{)}^{1\mathrm{/}D}=\mathrm{\mid }{A}_1{\mathrm{\mid }}^{1\mathrm{/}D}$. Old decided pairs stay decided. New wrong pairs can occur only between the $B_i$, and $x$-sparsity makes at most an $x$ fraction of those new decided pairs wrong. Thus (2) persists while $\mathrm{\mid }J\mathrm{\mid }$ increases, a contradiction. Hence $t\ge \lceil 2\mathrm{/}ϵ\rceil$.

Put $m=\lceil 2\mathrm{/}ϵ\rceil \le t$ and $w=\lceil \mathrm{\mid }{A}_1\mathrm{\mid }\mathrm{/}{k}^D\rceil$. Independently choose uniformly a $w$-element subset $C_i\subseteq B_i$ for each $i\le m$. For each pair $i<j$, its expected number of edges is at most $x{w}^2$, because the blockade is $x$-sparse. Markov's inequality says that the probability of more than $x{m}^2{w}^2\mathrm{/}2$ edges in that pair is at most $2\mathrm{/}{m}^2$. There are fewer than $m^2\mathrm{/}2$ pairs, so a simultaneous choice exists with every pair below this bound. Let $S={\bigcup }_{i\le m}{C}_i$. The within-block edge fraction is at most $1\mathrm{/}m\le ϵ\mathrm{/}2$; the cross-block edge fraction is at most $x{m}^2\le 16{ϵ}^{12D-2}\le ϵ\mathrm{/}2$. Thus $e(Q[S])\le ϵ\left(\genfrac{}{}{0px}{}{\mathrm{\mid }S\mathrm{\mid }}{2}\right)$. Finally, $\mathrm{\mid }S\mathrm{\mid }\ge w\ge \mathrm{\mid }{A}_1\mathrm{\mid }\mathrm{/}{k}^D\ge {ϵ}^{4D}{x}^{D}N\ge x^{D+1}N,$ where the last inequality follows from $4D+12D^2\le 12D(D+1)$. This proves (1), including the case where we complemented $Q$.

Now use the divisiveness constants $b,c$. Enlarge the exponent to $d\ge \max \{b,1\mathrm{/}c,4\}$ and decrease the parameter bound to $1\mathrm{/}d$; the defining implication persists because a smaller copy threshold and a smaller required width make it weaker. Put $D=d+1$ and $C=12D(D+1)$. We claim that $C$ is a weak viral exponent: for $0<ϵ<1\mathrm{/}2$, every graph $G$ with ${\mathrm{ind}}_H(G)<({ϵ}^C\mathrm{\mid }G\mathrm{\mid }{)}^{\mathrm{\mid }H\mathrm{\mid }}$ for all $H\in \mathcal{F}$ has $S$ of size at least ${ϵ}^C\mathrm{\mid }G\mathrm{\mid }$ satisfying the edge bound in (1). If $\mathrm{\mid }G\mathrm{\mid }\le {ϵ}^{-C}$, take a singleton. Otherwise put $x={ϵ}^{12D}$ and let $F$ be any induced subgraph of $G$ of size at least ${ϵ}^{4D}\mathrm{\mid }G\mathrm{\mid }$. Since $12dD+4D<C$, $x^d\mathrm{\mid }F\mathrm{\mid }\ge {ϵ}^{12dD+4D}\mathrm{\mid }G\mathrm{\mid }>{ϵ}^C\mathrm{\mid }G\mathrm{\mid }\mathrm{.}$ The copy bounds transfer to $F$. Moreover $\mathrm{\mid }F\mathrm{\mid }>{ϵ}^{4D-C}\ge x^{-d\mathrm{/}2}$, and $x<1\mathrm{/}d\le c$. Divisiveness gives an $x$-sparse blockade in $F$ or its complement of width at least $\mathrm{\mid }F\mathrm{\mid }\mathrm{/}{k}^d\ge \mathrm{\mid }F\mathrm{\mid }\mathrm{/}{k}^D$ for some $k\in [2,x^{-1}]$. Thus every such $F$ satisfies the hypothesis of step 1.1 with $Q=G$ and exponent $D$. Its conclusion has size $x^{D+1}\mathrm{\mid }G\mathrm{\mid }={ϵ}^C\mathrm{\mid }G\mathrm{\mid }$, proving the weak claim.

Set $E=4C$. If $G$ satisfies the viral copy bounds at ${ϵ}^E$, then it satisfies the weak copy bounds at $(ϵ\mathrm{/}4{)}^C$, because ${ϵ}^{4C}\le (ϵ\mathrm{/}4{)}^C$ for $ϵ<1\mathrm{/}2$. Step 5.1, with parameter $ϵ\mathrm{/}4$, gives $T$ with $\mathrm{\mid }T\mathrm{\mid }\ge (ϵ\mathrm{/}4{)}^C\mathrm{\mid }G\mathrm{\mid }$ and, in $G[T]$ or its complement, at most $(ϵ\mathrm{/}4)\left(\genfrac{}{}{0px}{}{\mathrm{\mid }T\mathrm{\mid }}{2}\right)$ edges. The mean degree there is less than $ϵ\mathrm{\mid }T\mathrm{\mid }\mathrm{/}4$, so fewer than half the vertices have degree greater than $ϵ\mathrm{\mid }T\mathrm{\mid }\mathrm{/}2$. Keep the other vertices as $S$. Then $\mathrm{\mid }S\mathrm{\mid }\ge \mathrm{\mid }T\mathrm{\mid }\mathrm{/}2$, and every vertex of $S$ has at most $ϵ\mathrm{\mid }T\mathrm{\mid }\mathrm{/}2\le ϵ\mathrm{\mid }S\mathrm{\mid }$ neighbors in the chosen graph on $S$. Also $\mathrm{\mid }S\mathrm{\mid }\ge (ϵ\mathrm{/}4{)}^C\mathrm{\mid }G\mathrm{\mid }\mathrm{/}2\ge {ϵ}^{4C}\mathrm{\mid }G\mathrm{\mid }$ because $C\ge 1$ and $ϵ\le 1\mathrm{/}2$. Thus $S$ is $ϵ$-restricted and has the required viral size.