3 citations · 5 across the 6 of their papers we have counts for
13 papers
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…
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…
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…
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…
Dense Edge-Magic Graphs and Thin Additive Bases
Oleg Pikhurko
We study s(k,n), the maximum size of A+A where A is a k-subset of [n]. A few known functions from additive number theory can be expressed via s(k,n). For example, our estimates of…
Descriptive Complexity of Finite Structures: Saving the Quantifier Rank
Oleg Pikhurko, Oleg Verbitsky
Given a relational structure M on n elements, let D(M) be the minimum quantifier rank of a first order formula identifying M up to isomorphism in the class of n-element structures.…