First-order definitions of subgraph isomorphism through the adjacency and order relations (Q2211263)

Given a graph \(F\), let \(\mathcal S(F)\) be the graphical property of having \(F\) as a (not necessarily induced) subgraph. If \(\sim\) is the vertex adjacency relation symbol, let \(\Sigma = \{ \sim, < \}\) be the signature for linearly ordered finite graphs. A first-order sentence \(\varphi\) of signature \(\Sigma\) defines \(\mathcal S(F)\) if, for any graph \(G\), and any linear ordering of \(G\)'s vertices, if \(G'\) is \(G\) expanded by that linear ordering, then \(G' \models \varphi\) iff \(G\) has \(F\) as a (not necessarily induced) subgraph. Let \(D_< (F)\) be the minimum quantifier depth of any \(\Sigma\)-sentence defining \(\mathcal S(F)\) and let \(W_< (F)\) be the minimum number of variables of any \(\Sigma\)-sentence defining \(\mathcal S(F)\). The primary result of this paper is that if \(F\) is a tree of \(\ell\) vertices, then \(D_< (F) \leq \ell/2 + \lceil \log_2 (\ell + 2) \rceil - 1\); they also observe that \(W_< (F) \leq \ell/2 + 2\). In addition, using Fraïsse-Ehrenfeucht games, \(D_<(F)\) is computed for each graph \(F\) of order less than \(5\). There are some typos, so readers should take care.