Oleg Verbitsky

most citedHow Complex are Random Graphs in First Order Logic?

1 citations · 1 across the 7 of their papers we have counts for

collaborators

7 papers

math.CO2005

First Order Definability of Trees and Sparse Random Graphs

Tom Bohman, Alan Frieze, Tomasz Luczak +4

Let D(G) be the smallest quantifier depth of a first order formula which is true for a graph G but false for any other non-isomorphic graph. This can be viewed as a measure for the…

cs.CC2004

On the Computational Complexity of the Forcing Chromatic Number

Frank Harary, Wolfgang Slany, Oleg Verbitsky

We consider vertex colorings of graphs in which adjacent vertices have distinct colors. A graph is $s$ -chromatic if it is colorable in $s$ colors and any coloring of it uses at lea…

math.LO2004

Definitions with no quantifier alternation

Oleg Pikhurko, Joel Spencer, Oleg Verbitsky

Let $D (G)$ be the minimum quantifier depth of a first order sentence $Φ$ that defines a graph $G$ up to isomorphism. Let $D_{0} (G)$ be the version of $D (G)$ where we do not allow qua…

math.CO2004

On the Lengths of Symmetry Breaking-Preserving Games on Graphs

Frank Harary, Wolfgang Slany, Oleg Verbitsky

Given a graph $G$ , we consider a game where two players, $A$ and $B$ , alternatingly color edges of $G$ in red and in blue respectively. Let $l (G)$ be the maximum number of moves in…

math.CO2004

The First Order Definability of Graphs with Separators via the Ehrenfeucht Game

Oleg Verbitsky

We say that a first order formula $Φ$ defines a graph $G$ if $Φ$ is true on $G$ and false on every graph $G^{'}$ non-isomorphic with $G$ . Let $D (G)$ be the minimal quantifier rank of…

math.CO2004★ 1 cited

How Complex are Random Graphs in First Order Logic?

Jeong Han Kim, Oleg Pikhurko, Joel Spencer +1

It is not hard to write a first order formula which is true for a given graph G but is false for any graph not isomorphic to G. The smallest number $(G) of nested quantifiers in a…