3 citations · 5 across the 6 of their papers we have counts for
8 papers · 1 filter
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…
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…
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…
Borsuk's Conjecture Fails in Dimensions 321 and 322
Oleg Pikhurko
Borsuk's conjecture states that any bounded set in R^n can be partitioned into n+1 sets of smaller diameter. It is known to be false for all n bigger or equal to 323. Here we show…
Remarks on a Paper by Y.Caro and R.Yuster on Turan Problem
Oleg Pikhurko
Caro and Yuster (Electronic J.Comb 7 (2000)) studied a generalization of the Turan problem, where a certain function (instead of the size) of an F-free graph of order n has to be m…
Asymptotic Size Ramsey Results for Bipartite Graphs
Oleg Pikhurko
We investigate size Ramsey numbers involving bipartite graphs. It is proved that, if each forbidden graph is fixed or grows with n (in a certain uniform manner), then the extremal…