Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism

02/06/2018
by   Oleg Verbitsky, et al.
0

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 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 2/3 v(F)-2 first-order variables.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset