\section{Low shrubdepth colorings and the strong Erd\H{o}s-Hajnal property}\label{app:shrubs}

We start by considering the setting when the graph in question admits a connection model of bounded depth and using a bounded number of labels. Here, by the {\em{depth}} of a rooted tree we mean the maximum number of vertices on a root-to-leaf path.

\begin{lemma}\label{lem:low-shrubdepth}
 Let $G$ be a graph on $n\geq 2$ vertices that admits a connection model of depth $d$ and using a label set of size $s$.
 Then there exist disjoint subsets of vertices $A$, $B$ of $G$ such that $$\min(|A|,|B|)\geq \frac{n}{3s\cdot 2^{d-2}}$$ and $A$ is either complete or anticomplete to $B$.
\end{lemma}
\begin{proof}
 Let \((\lambda, T, \set{Z_x \colon x \in V(T) \setminus V(G)})\) be the assumed connection model of $G$. 
 Recall $T$ has depth $d$ and $Z_x\subseteq \Lambda^2$ for some label set $\Lambda$ of size $s$, for each $x \in V(T) \setminus V(G)$.
 Note that since $n\geq 2$, $T$~cannot consist of only one leaf, hence $d\geq 2$.
 We proceed by induction on $d$, where the base case $d=2$ will be argued directly within the reasoning.
 
 Let $r$ be the root of $T$ and let $C$ be the set of children of $r$ in $T$. 
 For every $c\in C$, let $L_c$ comprise the leaves of $T$ that are descendants of $c$ (possibly $L_c=\{c\}$ if $c$ itself is a leaf).
 Then $\{L_c\colon c\in C\}$ is a partition of the vertex set of $G$. We consider two cases.
 
 First, suppose that there exists $c_0\in C$ such that $|L_{c_0}|>n/2$.
 Note here that this case cannot happen for $d=2$, because then $T$ is a star with all the children of $r$ being leaves, hence $|L_c|=1\leq n/2$ for all $c\in C$.
 Therefore, we may apply the induction hypothesis to the graph $G[L_{c_0}]$, which has $|L_{c_0}|>n/2\geq 1$ vertices and admits a connection model of depth $d-1$ and using a label set of size $s$, obtained by restricting the connection model \((\lambda, T, \set{Z_x \colon x \in V(T) \setminus V(G)})\) in a natural way.
Thus, we obtain $A,B\subseteq L_{c_0}$ such that $A$ is either complete or anticomplete to~$B$, and
 $$\min(|A|,|B|)\geq \frac{|L_{c_0}|}{3s\cdot 2^{d-3}}>\frac{n}{3s\cdot 2^{d-2}},$$
 as required.
 
 Second, suppose that for all $c\in C$, we have $|L_c|\leq n/2$.
 It is well-known that then there is a partition of $C$ into $X$ and $Y$ such that for each $Z\in \{X,Y\}$, we have
 $$n/3\leq \sum_{c\in Z} |L_c|\leq 2n/3.$$
 Since the connection model uses a label set $\Lambda$ of size $s$, we can find a set $A$ such that
  $A\subseteq \bigcup_{c\in X} L_c$, $|A|\geq \frac{n}{3s}$, and all vertices of $A$ receive the same label under $\lambda$.
 We also find $B\subseteq \bigcup_{c\in Y} L_c$ such that
  $B\subseteq \bigcup_{c\in Y} L_c$, $|B|\geq \frac{n}{3s}$, and all vertices of $B$ receive the same label under $\lambda$.
 Thus, $A$ and $B$ are disjoint and $$\min(|A|,|B|)\geq \frac{n}{3s}\geq \frac{n}{3s\cdot 2^{d-2}}.$$
 Finally, let $\lambda_A$ be the value of $\lambda(a)$ for all $a\in A$ 
 and $\lambda_B$ be the value of $\lambda(b)$ for all $b\in B$.
 If $(\lambda_A,\lambda_B) \not \in Z_r$ then $A$ is anticomplete to $B$.
 Otherwise, $(\lambda_A,\lambda_B)  \in Z_r$ and then $A$ is complete to~$B$.
 Note that since in this case we have found suitable sets $A$ and $B$ directly, the base case $d=2$ is covered.
\end{proof}

Now, from Lemma~\ref{lem:low-shrubdepth} it is easy to conclude the claimed connection.

\begin{theorem}\label{thm:lsc-EH}
 Let $\Cc$ be a class of graphs that admits low shrubdepth colorings. Then $\Cc$ has the strong Erd\H{o}s-Hajnal property.
\end{theorem}
\begin{proof}
 Consider any graph $G\in \Cc$, say on $n$ vertices. 
 Since we want to verify the strong Erd\H{o}s-Hajnal property of $G$, we assume that $n\geq2$.
 By assumption, there exist numbers $s=s(1)$ and $f=f(1)$ such that $G$ admits a coloring using $f$ colors where each color induces a subgraph of shrubdepth at most $s$.
 By considering the color class of the largest cardinality, we infer that $G$ contains an induced subgraph $H$ such that $H$ has at least $n/f$ vertices and shrubdepth at most~$s$.
 Assuming that $n/f\geq 2$, we may apply Lemma~\ref{lem:low-shrubdepth} to $H$. This yields a pair of disjoint vertex subsets $A$ and $B$ such that $A$ is either complete or anticomplete to $B$, and
 $$\min(|A|,|B|)\geq \frac{|V(H)|}{3s\cdot 2^{s-2}}\geq \frac{n}{3sf\cdot 2^{s-2}}.$$
 Finally, if $n/f<2$, then $n<2f$ and we may choose $A$ and $B$ to be any disjoint singleton sets ($n\geq2$); then $\min(|A|,|B|)>\frac{n}{2f}$.
 We conclude that $\Cc$ has the strong Erd\H{o}s-Hajnal property for $\delta=\frac{1}{3sf\cdot 2^{s-2}}$.
\end{proof}

By combining Theorem~\ref{thm:lsc-EH} with the results of Kwon et al.~\cite{KPS20}, we conclude that for every class of bounded expansion $\Cc$ and positive integer $d$, 
the class $\Cc^d$ has the strong Erd\H{o}s-Hajnal property
Similarly, Conjecture~\ref{conj:lsc}, if true, would imply a weaker variant of Theorem~\ref{thm:main}, where $A=B=V(G)$ and we only require that $\min(|A'|,|B'|)\geq n^{1-\epsi}$.
However, note that in the proof of Theorem~\ref{thm:lsc-EH} we only relied on the existence of a suitable coloring for $p=1$, instead of all positive integers $p$, as postulated by
Conjecture~\ref{conj:lsc}.
While Conjecture~\ref{conj:lsc} remains open in general, its restriction to the case of $p=1$ was very recently proved by Ne\v{s}et\v{r}il et al.~\cite{NOdMPZ19}. 
Therefore, the aforementioned weaker form of Theorem~\ref{thm:main} indeed follows from the results of~\cite{NOdMPZ19} through the reasoning explained above.
{"config": "arxiv", "file": "2006.01500/shrubs.tex"}