O. Verbitsky

activity

20012005

most citedDescriptive Complexity of Finite Structures: Saving the Quantifier Rank

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

collaborators

Showing 2004 · math.LOShow all

2 papers · 2 filters

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.LO2004

Succinct Definitions in the First Order Theory of Graphs

Oleg Pikhurko, Joel Spencer, Oleg Verbitsky

We say that a first order sentence A defines a graph G if A is true on G but false on any graph non-isomorphic to G. Let L(G) (resp. D(G)) denote the minimum length (resp. quantifi…