Joel Spencer
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
Research Subjects
Research Interests
Joel Spencer has a total of 27 co-authors. Here are the top co-authors by number of shared publications:
- Noga Alon
Department of Mathematics, Princeton University, Princeton, USA
4 shared publications - Svante Janson
Department of Mathematics, Uppsala University, Uppsala, Sweden
3 shared publications - Christian Borgs
Bakar Institute of Digital Materials for the Planet, College of Computing, Data Science, and Society, University of California, Berkeley, California 94720, USA
2 shared publications G. Tóth
Hungarian Academy of Sciences
2 shared publications- Gordon Slade
University of British Columbia
2 shared publications - Jennifer T. Chayes
Bakar Institute of Digital Materials for the Planet, College of Computing, Data Science, and Society, University of California, Berkeley, California 94720, USA
2 shared publications
Latest Publications
- Open Access
Phase transitions for modified Erdös-Rényi processes
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.
Open AccessPhase transitions for modified Erdös-Rényi processes
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.
- 20 February 2008
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 152 (1-3) , 174-179
The complexity of random ordered structures
- 20 February 2008
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 152 (1-3) , 174-179
The complexity of random ordered structures
- 1 January 2007
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 16 (4) , 631-658
A Point Process Describing the Component Sizes in the Critical Window of the Random Graph Evolution
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.
- 1 January 2007
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 16 (4) , 631-658
A Point Process Describing the Component Sizes in the Critical Window of the Random Graph Evolution
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
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.
Open AccessA point process describing the component sizes in the critical window of the random graph evolution
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.
- 13 January 2005
- Published by Wiley in Random Structures & Algorithms
- Vol. 27 (2) , 137-184
Random subgraphs of finite graphs: I. The scaling window under the triangle condition
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
- 13 January 2005
- Published by Wiley in Random Structures & Algorithms
- Vol. 27 (2) , 137-184
Random subgraphs of finite graphs: I. The scaling window under the triangle condition
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
- 23 November 2004
- Published by Wiley in Random Structures & Algorithms
- Vol. 26 (1-2) , 119-145
How complex are random graphs in first order logic?
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
- 23 November 2004
- Published by Wiley in Random Structures & Algorithms
- Vol. 26 (1-2) , 119-145
How complex are random graphs in first order logic?
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?
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 AccessHow Complex are Random Graphs in First Order Logic?
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
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.Open AccessRandom subgraphs of finite graphs: III. The phase transition for the $n$-cube
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. - 19 September 2002
- Published by Wiley in Random Structures & Algorithms
- Vol. 21 (3-4) , 225-251
Random dyadic tilings of the unit square
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
- 19 September 2002
- Published by Wiley in Random Structures & Algorithms
- Vol. 21 (3-4) , 225-251
Random dyadic tilings of the unit square
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
- 1 January 2001
- Published by Springer Nature
- p. 103-118
Near Rational Powers of n