The Descriptive Complexity of Subgraph Isomorphism without Numerics

Let $F$ be a connected graph with $\mathrm{\ell }$ vertices. The existence of a subgraph isomorphic to $F$ can be defined in first-order logic with quantifier depth no better than $\mathrm{\ell }$, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs $K_{\mathrm{\ell }}$ and $K_{\mathrm{\ell }-1}$. We show that, for some $F$, the existence of an $F$ subgraph in \emph{sufficiently large} connected graphs is definable with quantifier depth $\mathrm{\ell }-3$. On the other hand, this is never possible with quantifier depth better than $\mathrm{\ell }\mathrm{/}2$. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some $F$ be arbitrarily small comparing to $\mathrm{\ell }$ but never smaller than the treewidth of $F$. Moreover, the definitions over highly connected graphs require quantifier depth strictly more than the density of $F$. Finally, we determine the exact values of these descriptive complexity parameters for all connected pattern graphs $F$ on 4 vertices.