2018/02/06 by Verbitsky, Oleg, Zhukovskii, Maksim
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.1802.02143
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 \frac23 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 \frac23 v(F)-2 first-order variables.