3 citations · 5 across the 6 of their papers we have counts for
Showing 2004Show all
3 papers · 1 filter
math.LO2004
Definitions with no quantifier alternation
Oleg Pikhurko, Joel Spencer, Oleg Verbitsky
Let be the minimum quantifier depth of a first order sentence that defines a graph up to isomorphism. Let be the version of where we do not allow qua…
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…
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…