3 citations · 8 across the 8 of their papers we have counts for
5 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…
Counting Connected Graphs Asymptotically
Remco van der Hofstad, Joel Spencer
We find the asymptotic number of connected graphs with vertices and edges when approach infinity, reproving a result of Bender, Canfield and McKay. We use the {\e…
Simulating a Random Walk with Constant Error
Joshua N. Cooper, Joel Spencer
We analyze Jim Propp's P-machine, a simple deterministic process that simulates a random walk on to within a constant. The proof of the error bound relies on several estimate…
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…
Packing Ferrers Shapes
Noga Alon, Miklós Bóna, Joel Spencer
Answering a question of Wilf, we show that if is sufficiently large, then one cannot cover an rectangle using each of the distinct Ferrers shapes of size…