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

Showing math.COShow all

4 papers · 1 filter

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…

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…