JSJoel Spencer

Joel Spencer

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Joel Spencer has a total of 27 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Phase transitions for modified Erdös-Rényi processes

    by Svante Janson, Joel Spencer

    A fundamental and very well studied region of the Erd\"os-R\'enyi process is the phase transition at n/2 edges in which a giant component suddenly appears. We examine the process beginning with an initial graph. We further examine the Bohman-Frieze process in which edges between isolated vertices are more likely. While the positions of the phase transitions vary, the three processes belong, roughly speaking, to the same universality class. In particular, the growth of the giant component in the barely supercritical region is linear in all cases.

  • The complexity of random ordered structures

    by Joel H. Spencer, Katherine St. John

  • A Point Process Describing the Component Sizes in the Critical Window of the Random Graph Evolution

    by Svante Janson, Joel Spencer

    We study a point process describing the asymptotic behaviour of sizes of the largest components of the random graph G(n, p) in the critical window, that is, for p = n−1 + λn−4/3, where λ is a fixed real number. In particular, we show that this point process has a surprising rigidity. Fluctuations in the large values will be balanced by opposite fluctuations in the small values such that the sum of the values larger than a small ϵ (a scaled version of the number of vertices in components of size greater than εn2/3) is almost constant.


  • Open Access

    A point process describing the component sizes in the critical window of the random graph evolution

    by 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 particular, we show that this point process has a surprising rigidity. Fluctuations in the large values will be balanced by opposite fluctuations in the small values such that the sum of the values larger than a small epsilon is almost constant.

  • Random subgraphs of finite graphs: I. The scaling window under the triangle condition

    by Christian Borgs, Jennifer T. Chayes, Remco van der Hofstad, Gordon Slade, Joel Spencer

    We study random subgraphs of an arbitrary finite connected transitive graph 𝔾 obtained by independently deleting edges with probability 1 − p. Let V be the number of vertices in 𝔾, and let Ω be their degree. We define the critical threshold pc = pc (𝔾, λ) to be the value of p for which the expected cluster size of a fixed vertex attains the value λV1/3, where λ is fixed and positive. We show that, for any such model, there is a phase transition at pc analogous to the phase transition for the random graph, provided that a quantity called the triangle diagram is sufficiently small at the threshold pc. In particular, we show that the largest cluster inside a scaling window of size |p − pc| = Θ(Ω−1V−1/3) is of size Θ(V2/3), while, below this scaling window, it is much smaller, of order O(ϵ−2 log(Vϵ3)), with ϵ = Ω(pc − p). We also obtain an upper bound O(Ω(p − pc)V) for the expected size of the largest cluster above the window. In addition, we define and analyze the percolation probability above the window and show that it is of order Θ(Ω(p − pc)). Among the models for which the triangle diagram is small enough to allow us to draw these conclusions are the random graph, the n‐cube and certain Hamming cubes, as well as the spread‐out n‐dimensional torus for n > 6. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005


  • How complex are random graphs in first order logic?

    by Jeong Han Kim, Oleg Pikhurko, Joel H. Spencer, Oleg Verbitsky

    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 D(G) of nested quantifiers in such a formula can serve as a measure for the “first order complexity” of G. Here, this parameter is studied for random graphs. We determine it asymptotically when the edge probability p is constant; in fact, D(G) is of order log n then. For very sparse graphs its magnitude is Θ(n). On the other hand, for certain (carefully chosen) values of p the parameter D(G) can drop down to the very slow growing function log* n, the inverse of the TOWER‐function. The general picture, however, is still a mystery. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005


  • Open Access

    How Complex are Random Graphs in First Order Logic?

    by Jeong Han Kim, Oleg Pikhurko, Joel Spencer, Oleg Verbitsky

    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 such formula can serve as a measure for the ``first order complexity'' of G. Here, this parameter is studied for random graphs. We determine it asymptotically when the edge probability p is constant; in fact, D(G) is of order log n then. For very sparse graphs its magnitude is \Theta(n). On the other hand, for certain (carefully chosen) values of p the parameter D(G) can drop down to the very slow growing function log^* n, the inverse of the tower-function. The general picture, however, is still a mystery.

  • Open Access

    Random subgraphs of finite graphs: III. The phase transition for the $n$-cube

    by Christian Borgs, Jennifer T. Chayes, Remco van der Hofstad, Gordon Slade, Joel Spencer

    We study random subgraphs of the $n$-cube $\{0,1\}^n$, where nearest-neighbor edges are occupied with probability $p$. Let $p_c(n)$ be the value of $p$ for which the expected cluster size of a fixed vertex attains the value $\lambda 2^{n/3}$, where $\lambda$ is a small positive constant. Let $\epsilon=n(p-p_c(n))$. In two previous papers, we showed that the largest cluster inside a scaling window given by $|\epsilon|=\Theta(2^{-n/3})$ is of size $\Theta(2^{2n/3})$, below this scaling window it is at most $2(\log2) n\epsilon^{-2}$, and above this scaling window it is at most $O(\epsilon 2^n)$. In this paper, we prove that for $p - p_c(n) \geq e^{-cn^{1/3}}$ the size of the largest cluster is at least $\Theta(\epsilon 2^n)$, which is of the same order as the upper bound. This provides an understanding of the phase transition that goes far beyond that obtained by previous authors. The proof is based on a method that has come to be known as ``sprinkling,'' and relies heavily on the specific geometry of the $n$-cube.

  • Random dyadic tilings of the unit square

    by Svante Janson, Dana Randall, Joel Spencer

    A “dyadic rectangle” is a set of the formR= [a2−s, (a+ 1)2−s] × [b2−t, (b+ 1)2−t], wheresandtare nonnegative integers. A dyadic tiling is a tiling of the unit square with dyadic rectangles. In this paper we studyn‐tilings, which consist of 2nnonoverlapping dyadic rectangles, each of area 2−n, whose union is the unit square. We discuss some of the underlying combinatorial structures, provide some efficient methods for uniformly sampling from the set ofn‐tilings, and study some limiting properties of random tilings. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 225–251, 2002