3 citations · 8 across the 8 of their papers we have counts for
9 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…
A point process describing the component sizes in the critical window of the random graph evolution
Svante Janson, Joel Spencer
We study a point process describing the asymptotic behavior of sizes of the largest components of the random graph G(n,p) in the critical window p=n^{-1}+lambda n^{-4/3}. In partic…
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…
Random subgraphs of finite graphs: III. The phase transition for the -cube
Christian Borgs, Jennifer T. Chayes, Remco van der Hofstad +2
We study random subgraphs of the -cube , where nearest-neighbor edges are occupied with probability . Let be the value of for which the expected clust…