2019/02/10 by E. D. Kudryavtsev, Mikhail Makarov, Kudryavtsev, E. D. +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1902.03648
openalex publication_date 2019/02/10 · openalex created_date 2019/02/21 · openalex updated_date 2026/07/28
We prove that, for every ℓ≥ 4, there exists an ℓ-vertex graph and a first order sentence having a quantifier depth at most ℓ-1 defining the property of having an induced subgraph isomorphic to the given one. We prove that a first order sentence defining the property of containing an induced subgraph on ℓ vertices isomorphic to a given disjoint union of isomorphic complete multipartite graphs has a quantifier depth at least ℓ. Finally, we prove that, for every graph on ℓ≤ 5 vertices a sentence defining the property of containing an induced subgraph isomorphic to the given one has a quantifier depth at least ℓ-1.