Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism

Abstract

Let $v(F)$ denote the number of vertices in a fixed connected pattern graph $F$. We show an infinite family of patterns $F$ such that the existence of a subgraph isomorphic to $F$ is expressible by a first-order sentence of quantifier depth $\frac{2}{3}v(F)+1$, assuming that the host graph is sufficiently large and connected. On the other hand, this is impossible for any $F$ with using less than $\frac{2}{3}v(F)-2$ first-order variables.

arXiv comment22 pages, 3 figures