Two Consequences of the Dichotomy Theorem

O. Verbitsky

Given two graphs $G$ and $H$, a vertex $u$ of $G$ and a vertex $v$ of $H$ such that there is no isomorphism from $G$ to $H$ taking $u$ to $v$, let $V(G,u,H,v)$ denote the minimum number of variables in a first order formula $\Phi(x)$ that is true on $(G,u)$ but false on $(H,v)$. Let $\mbox{\it Var\,}(G)$ be the maximum of $V(G,u,H,v)$ over all vertices $u$ of $G$ and all possible pairs $(H,v)$. Refining upon a result of Immerman and Lander, we prove that the class of graphs $G$ on $n$ vertices with $\mbox{\it Var\,}(G)\le(n+5)/2$ is efficiently recognizable and that, if $\mbox{\it Var\,}(G)>(n+5)/5$, then the exact value of $\mbox{\it Var\,}(G)$ is efficiently computable. We also solve a particular case of an open problem on the computational complexity of Ehrenfeucht games posed by Pezzoli.

1. Cai J.-Y., Fürer M., Immerman N. An optimal lower bound on the number of variables for graph identification, Combinatorica 12 (1992), no. 4, 389–410.

2. Dawar A., Lindell S., Weinstein S. Infinitary logic and inductive definability over finite structures, Information and Computation, 119 (1995), 160–175.

3. Immerman N. Descriptive complexity, Springer-Verlag, 1999.

4. Immerman N., Lander E. Describing graphs: a first-order approach to graph canonization, In: Complexity Theory Retrospective, A. Selman Ed., Springer-Verlag, (1990), 59–81.

5. Köbler J., Schöning U., Torán J. The graph isomorphism problem: its structural complexity, Birkhäuser, 1993.

6. Pezzoli E. Computational complexity of Ehrenfeucht-Fras̈sé games on finite structures, In: Proc. of the CSL'98 Conf., G. Gottlob, K. Seyr Eds. Lecture Notes in Computer Science 1584, Springer-Verlag, 1999, 159–170.

7. Pikhurko O., Veith H., Verbitsky O. First order definability of graphs: tight bounds on quantifier rank, Submitted manuscript, 2003, 50 pp. Available at http://arxiv.org/abs/math.CO/0311041

	Two consequences of the dichotomy theorem on first order definability of graphs
Author	O. Verbitsky Department of Mechanics and Mathematics, ,Kyiv National University
Abstract	Given two graphs $G$ and $H$, a vertex $u$ of $G$ and a vertex $v$ of $H$ such that there is no isomorphism from $G$ to $H$ taking $u$ to $v$, let $V(G,u,H,v)$ denote the minimum number of variables in a first order formula $\Phi(x)$ that is true on $(G,u)$ but false on $(H,v)$. Let $\mbox{\it Var\,}(G)$ be the maximum of $V(G,u,H,v)$ over all vertices $u$ of $G$ and all possible pairs $(H,v)$. Refining upon a result of Immerman and Lander, we prove that the class of graphs $G$ on $n$ vertices with $\mbox{\it Var\,}(G)\le(n+5)/2$ is efficiently recognizable and that, if $\mbox{\it Var\,}(G)>(n+5)/5$, then the exact value of $\mbox{\it Var\,}(G)$ is efficiently computable. We also solve a particular case of an open problem on the computational complexity of Ehrenfeucht games posed by Pezzoli.
Keywords	graph, vertex, efficiently recognizable class
DOI	doi:10.30970/ms.22.1.3-9
Reference	1. Cai J.-Y., Fürer M., Immerman N. An optimal lower bound on the number of variables for graph identification, Combinatorica 12 (1992), no. 4, 389–410. 2. Dawar A., Lindell S., Weinstein S. Infinitary logic and inductive definability over finite structures, Information and Computation, 119 (1995), 160–175. 3. Immerman N. Descriptive complexity, Springer-Verlag, 1999. 4. Immerman N., Lander E. Describing graphs: a first-order approach to graph canonization, In: Complexity Theory Retrospective, A. Selman Ed., Springer-Verlag, (1990), 59–81. 5. Köbler J., Schöning U., Torán J. The graph isomorphism problem: its structural complexity, Birkhäuser, 1993. 6. Pezzoli E. Computational complexity of Ehrenfeucht-Fras̈sé games on finite structures, In: Proc. of the CSL'98 Conf., G. Gottlob, K. Seyr Eds. Lecture Notes in Computer Science 1584, Springer-Verlag, 1999, 159–170. 7. Pikhurko O., Veith H., Verbitsky O. First order definability of graphs: tight bounds on quantifier rank, Submitted manuscript, 2003, 50 pp. Available at http://arxiv.org/abs/math.CO/0311041
Pages	3-9
Volume	22
Issue	1
Year	2004
Journal	Matematychni Studii
Full text of paper	pdf
Table of content of issue	html

Two consequences of the dichotomy theorem on first order definability of graphs