First-order definitions of subgraph isomorphism through the adjacency and order relations (Q2211263)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | First-order definitions of subgraph isomorphism through the adjacency and order relations |
scientific article |
Statements
First-order definitions of subgraph isomorphism through the adjacency and order relations (English)
0 references
10 November 2020
0 references
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.
0 references
descriptive complexity
0 references
first-order logic
0 references
linearly ordered graphs
0 references
logical complexity
0 references
order
0 references
quantifier depth
0 references
subgraph isomorphism
0 references
subtree
0 references