3 citations · 8 across the 8 of their papers we have counts for
5 papers · 1 filter
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…
Random subgraphs of finite graphs: II. The lace expansion and the triangle condition
Christian Borgs, Jennifer T. Chayes, Remco van der Hofstad +2
In a previous paper, we defined a version of the percolation triangle condition that is suitable for the analysis of bond percolation on a finite connected transitive graph, and sh…
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…