Research Summary
Goals
Applications of Probabilistic Methods in Discrete Mathematics and
Theoretical Computer Science
Vita
List of papers, positions, committees, etc.
postscript
pdf
Short (5 page) form
postscript
pdf
Selected Papers
A Few I REALLY Like

Joel Spencer , Asymptotic Packing via A Branching Process
postscript
pdf
Description
Paul Erdos and Haim Hanani conjectured that
there exists (for fixed l < k) an asymptotically good packing of kelement
subsets of an nset (n approaching infinity) with no lset covered
more than once. This was first shown by Vojtech Rodl using what is
now called the Rodl Nibble. In this paper we show that a random
greedy algorithm (order the ksets randomly and consider sequentially,
accepting if possible) is shown to work. Analyzing
it leads to an interesting branching process. Selfreview: Wonderful
Stuff!
Random Structures and Algorithms, vol 7, 1995, 167172
 Remco v.d. Hofstad, Joel Spencer,
Counting Connected Graphs Asymptotically
postscript
pdf
tex
Description
The asymptotics for the number $C(k,l)$ of connected labelled
graphs with $k$ vertices and $k1+l$ edges are found when
$k,l\rightarrow\infty$. Erd\H{o}s Magic is used, as the
random graph $G(k,p)$ is analyzed for a suitable $p$. Breadth
first search on $G(k,p)$ is analyzed, which in turn leads to
a tilted balls into bins question. (European J Comb.  2006, vol
27, 12941320)
 Ioana Dumitriu and Joel Spencer, A HalfLiar's Game
postscript
pdf
Description
Paul is trying to find x from n possibilities with q Yes/No queries
but responder Carole can lie (at most) k times. That is the standard
Liar Game  but now we insist that if the correct answer is Yes then
Carole must say Yes. (I.e., no false negatives.) We show asymptotically
(k fixed) that the largest n for which Paul wins goes up by a factor
of 2^k from the usual Liar Game. Theoretical Computer
Science, vol. 313 (2004), 353369
 Joel Spencer and Nick Wormald,
Birth Control for Giants
postscript
pdf
Description
We look at random graph processes of which the following is
typical. Begin with the empty graph. Each round four vertices
v,w,x,y are uniformly chosen. If v,w are isolated add the edge
v,w otherwise add the edge x,y. Parametrize time with time t
being tn/2 rounds so in normal ErdosRenyi the critical point
is t=1. We find a differential equation for the susceptibility
which explodes at some t_c. We show that the process hugs the
differential equation. In the subcritical t < t_c all components
are O(\ln n) while in the supercritical t > t_c a giant component
of size \Omega(n) has emerged. We make important use of a
result of Cramer on branching processes from 1920.
Combinatorica, vol 27 (2007), 587628
 Joel Spencer, Ulam's Searching Game with a Fixed Number of Lies
postscript
pdf
Abstract
Consider the Liar Game where Carole "picks" a number from 1 to n and
Paul has to guess it in q questions but Carole is allowed to lie, though
at most k times. (Try it with a friend with n=100, q=10, k=1.) For k
fixed we give precise necessary and sufficient conditions on n,q (q
sufficiently large) so theat Paul wins. Appeared in Theoretical
Computer Science vol 95 (1992), 307322
Expository Pieces
 Joel Spencer, For the Class of '68
postscript
pdf
Description
A tribute to Paul Erdos. Foreward to Combinatorics: Paul Erdos is 80,
conference volume in honor of Paul Erdos's eightieth birthday.
 Joel Spencer, The Giant Component  The Golden Anniversary
postscript
pdf
tex
Description
An expository discussion of the work of Paul Erdos and Alfred Renyi
on the Giant Component and much of the subsequent work in the last
fifty years. Notices of the AMS, vol. 57 (2010), 720724
 Joel Spencer, Potpourri
postscript
pdf
tex
Description
A highly subjective compendium of various notes that I have written and
sent to friends over the years. Written for a special issue for my
birthday. Try it! Journal of Combinatorics, vol 1 (2010), 237264
Other Good Stuff
 Svante Janson, Joel Spencer,
Phase Transitions for Modified ErdosRenyi processes
pdf
Description
Detailed exploration of the BohmanFrieze process near criticality.
Also, detailed exploration of the ErdosRenyi process beginning with
a fixed (fairly, but not totally general) graph H. In both cases
it is indicated that these processes and standard ErdosRenyi belong
to the same universality class. In particular, the growth of the
giant component in the barely supercritical regime is linear in all
three cases. A basic tool is analysis of the susceptibility near
criticality. Appeared: Arkiv fo"r Matemaik, vol 50 (2012), 305329.
 Remco van der Hofstad, Malwina Luczak, Joel Spencer
The Second Largest Component in the Supercritical 2D Hamming Graph
tex
pdf
Description
The evolution of the random subgraph of the 2D Hamming Graph
(n^2 vertices, adjacent if they share a common coordinate)
is considered. The critical point is, easily, when the average
degree is one. We suppose the average degree is 1+\epsilon with
\epsilon >> n^{2/3}\ln^{1/3}n. From analogy to Erdos Renyi
percolation this should be barely outside the critical window.
Previous work had shown that the largest component is roughly
2\eps V (V=n^2) and we now show that the second largest component
is roughly \eps^{2}\ln(V\eps^3) which again matches the ErdosRenyi
behavior. Random Structures and Algorithms, vol 36 (2010), 8089
 Svante Janson, Joel Spencer,
A Point Process Describing the Component Sizes in the Critical
Window of the Random Graph Evolution
tex
ps
pdf
Description
For fixed $\lambda$ in the critical window at $p=n^{1}+\lambda n^{4/3}$
we scale components by $n^{2/3}$. The limiting values are given by a
point process on the positive reals. The point process has a surprising
rigidity in that the sum of the values larger than a small $\epsilon$
is almost constant. (Combinatorics, Probability & Combinatorics, vol. 16,
2006, pp 631658)
 Christian Borgs, Jennifer Chayes, Remco van der Hofstad,
Gordon Slade, Joel Spencer: A Series of Three papers
Random Subgraphs of Finite Graphs: I. The Scaling Window under the
Triangle Condition, Random Structures & Algorithms, vol 27
2005, 137184.
pdf
Random subgraphs of finite graphs: II. The lace expansion and
the triangle condition, Annals of Probability, vol 33, 2005, 18861944
pdf
Random subgraphs of finite graphs: III. The phase transition for
the ncube, Combinatorica, vol 26, (2006), 395410.
pdf
Description
A Series of papers giving the phase transition for the random
subgraph of the ncube, including finite analogues to the
triangle condition and mean field behavior.
 Christian Borgs, Jennifer Chayes, Henry Kesten, Joel Spencer,
Birth of the Infinite Cluster: FiniteSize Scaling in Percolation
pdf
Description
Percolation for an asymptotically large cube, of size n, in dimension
d has critical window p_c + \lambda n^{a} for an appropriate a.
Communications in Mathematical Physics
vol. 224 (1) 2001, pp 153204
 Mihyun Kang, Will Perkins, Joel Spencer
The BohmanFrieze Process Near Criticality
pdf
Description
Detailed exploration of the BohmanFrieze process near criticality.
At t_c\epsilon the size and nature of the largest component and
at t_c+\epsilon the size and nature of both the largest and
second largest component. Random Structures & Algorithms, to
appear 2013
 Abraham Neyman, Joel Spencer,
Complexity and Effective Prediction
pdf
Description
Two players pick Finite State Automata that then play a
finite, zerosum game and infinite number of times. The
other FSA's move is input. Suppose one player gets to
pick an FSA with m states and the other with n states
 how much bigger need m be than n to give the first
player a real advantage? Games and Economic Behavior
(2010), 165168
 Joshua Cooper and Joel Spencer,
Simulating a Random Walk with Constant Error
postscript
pdf
Description
This investigates a machine devised by Jim Propp to have
quasirandom behavior. In Z^d we start with a pile of chips
on the origin (though it could be more general). Each time
the chips at each position are spread evenly to their
neighbors. Critically the "odd" ones are also spread and
in such a way that next time there are an "odd" number at
that position it evens out. It is shown that the discrepency
between this deterministic machine and the expectation of
a random walk machine is bounded by a constant (dependent on
d) independent of the time of the run and the initial position.
(To appear, CPC)
 Benjamin Doerr, Joshua Cooper, Gabor Tardos and Joel Spencer,
Deterministic Random Walks on the Integers
postscript
pdf
Description
This investigates a machine devised by Jim Propp to have
quasirandom behavior. We restrict to the machine on the
integers Z. We start with various piles of chips at
various even positions. Each time
until the chips at each position are split, half going left
and half going right one position. Critically, the choice
when there are an odd number of chips of where to put the
odd chip alternates between left and right.
We bound the discrepency
between this deterministic machine and the expectation of
a random walk machine, when averaged over a time interval,
a space interval, or both.
European Journal of Combinatorics, vol 28,
(2007), 20722090
 Boris Pittel, Nick Wormald and Joel Spencer
Sudden emergence of a giant $k$core in a random graph
pdf
Description
The $k$core of a graph $G$ is given by iterating the deletion of
all vertices with degree less than $k$. This might be empty. We
condider the value of the $k$core in the ErdosRenyi model, adding
one edge at a time. We find the $c$ so that the $k$core becomes
nonempty at $cn/2$ edges. We show that at the moment the $k$core
becomes nonempty there is, effectively, a first order phase transition
in that the $k$core then has $Kn$ vertices, where $K$ is a positive
constant.
(J. Combinatorial Theory, Ser B. \underline{67} (1996), 111151)
 Joel Spencer, Logic and Random Structures
pdf
tex
ps
Description
An expository account of ZeroOne Laws, geared more to the
logician than to the combinatorialist. A chapter in
Finite Model Theory and Its Applications, Springer, 2007
 Joel Spencer and Katherine StJohn,
The Complexity of Random Ordered Structures
pdf
Description
For a finite structure G the value D(G) is the smallest
quantifier depth of a first order sentence that uniquely
defines G. We consider D(G) for various random structures.
For the random graph it is O(ln n), for the random
bin string it is O(ln ln n), but for the random ordered string
it is O(ln*n). These are all with p=1/2 and matching lower
bounds are found.
(Submitted for publication)
 Michael Mitzenmacher, Roberto Oliveira and Joel Spencer,
A Scaling Result for Explosive Processes
postscript
pdf
tex
Description
We consider the asymptotic behavior of the following model: balls are
sequentially thrown into bins so that the probability that a bin with
$n$ balls obtains the next ball is proportional to $f(n)$ for some
function $f$. A commonly studied case where there are two bins and
$f(n) = n^p$ for $p > 1$. In this case, one of the two bins
eventually obtains a monopoly, in the sense that it obtains all balls
thrown past some point. This model is motivated by the phenomenon of
positive feedback, where the ``rich get richer.'' We derive a
asymptotic expression for the probability that bin 1 obtains a
monopoly when bin 1 starts with $x$ balls and bin 2 starts with $y$
balls for the case $f(n) = n^p$. We found the appropriate scaling
when $x>y$ are large to determine if the first bin has a substantial
advantage over the second. (Electronic Journal of Combinatorics,
R31, vol. 11 (1) 2004)
 Roberto Oliveira and Joel Spencer,
Connectivity Transitions in Networks with SuperLinear
Preferential Attachment
pdf
Description
This is a graph process where each new vertex joins to one old vertex
with the choice in proportion to the degree to the power p. For every
positive integer k there is a phase transition at p = 1 + 1/k. For
all 2>p>1 other than at the phase transitions
there will be one critical vertex and the
infinite graph of its descendents is described (dependent on p) plus
a "finite" part of the graph that is, in some sense, arbitrary.
Internet Mathematics vol 2 (2005), 121163 (with Roberto Oliveira)
 Bela Bollobas, Oliver Riordan, G. Tusnary and Joel Spencer,
The degree sequence of a scalefree random graph process
postscript
pdf
Description
In modelling the web graph new vertices are joined to old vertices
in proportion (maybe!) to the current degrees of the old vertices
so that the rich get richer. Analyzing this process leads to some
intriguing power laws. Random Structures and Algorithms, vol 18, 2001,
279290
 Dana Randall, Svante Janson and Joel Spencer, Random Dyadic Tilings of the
Unit Square
postscript
pdf
Description
Dyadic Tilings are splittings of
the unit square into 2^n rectangles, each of size 2^{n}, each
axis parallel with intervals in both axes of the form
[a2^{c},(a+1)2^{c}]. They have a remarkably rich structure.
(Random Structures
& Algorithms, vol. 21 (2002), 225251)
 Joel Spencer and Catherine Yan, The HalfLie Problem
postscript
pdf
Description
In a followup to the Dumitriu/Spencer paper described above the
second order term on the largest n for which Paul wins is found.
Journal of Combinatorial Theory, Ser A, vol. 103,
(2003), 6989
 Ioana Dumitriu and Joel Spencer, The Liar Game over an Arbitray Channel
postscript
pdf
Description
Here Paul asks questions with t (fixed) possible answers and Carole
can lie only according to predetermined patterns. For example, with
answers A,B,C, Carole could only lie B for A or C for B. Fixing the
number of lies and fixing the channel we find asymptotically the
maximum n for which Paul wins. Surprisingly, it depends only on t and
the number E of lie patterns, not on the actual configuration.
Combinatorica, vol 25 (2005) 537559.
 Ioana Dumitriu and Joel Spencer, The TwoBatch Liar Game over an Arbitray Channel
postscript
pdf
Description
Same as above paper except now Paul must ask his questions in only two
batches. We show that Paul does asymptotically just as well as when
he does not have this restriction.
(SIAM Discrete Math, to appear)
 Joel Spencer and Geza Toth, Crossing Numbers for Random Graphs
postscript
pdf
Description
What is the usual crossing number of the random graph G(n,p). There
are three answers given, depending on the notion of crossing number.
(The usual; straight lines; pairs of edges crossing). We find for
fairly small p that the crossing number becomes a positive proportion
of the number of pairs of edges. Random Structures and
Algorithms, vol. 21 (2002), 347358
 Joel Spencer, Logic and Random Structures
postscript
pdf
Description
A series of expository talks given
given at the University of Pennsylvania Workshop on Logic and
Cognitive Science, sponsored by DIMACS and IRCS in April 1999.
They explore the world of ZeroOne Laws and Random Structures
in briefer style than the monograph "The Strange Logic of Random
Graphs." Designed for an audience of logicians.
 Joel Spencer, Ultrahigh Moments for a Brownian Excursion
postscript
pdf
Description
The number c(n,k) of connected labelled graphs with n vertices and
n1+k edges is given in terms of the kth factorial moment of a random
variable M associated with a finite excursion  a walk with fixed endpoint
that never goes negative. As n and k go to infinity this is related
(but without full rigor) to the title. The hope (still speculative) is
to give an alternative argument for the asymptotics of c(n,k) due to
Bender, Canfield and McKay and to understand better the random connected
graph. Appeared in Mathematics and Computer Science (Gard, Mokkadem,
eds.), Birkhauser 200
 Jiri Matousek and Joel Spencer, Discrepancy in Arithmetic Progressions
postscript
pdf
Description
There exists a coloring of the first n integers so that all arithmetic
progressions have discrepancy at most cn^{1/4}, realizing a bound
of K.F. Roth. Journal of the American Mathematical
Society, vol. 9 (1996), 195204
 Tomasz Luczak and Joel Spencer, Can you feel the double jump
postscript
pdf
photo of authors
Description
In what languages is the jump in G(n,p) from p= 0.99/n to 1.01/n
visible? Roughly, not in First Order but yes in Second Order Monadic.
 Joel Spencer, The Erdos Existence Argument
postscript
pdf
Description
A trip down memory lane with many of Erdos's main results in the
probabilistic method, looked at from a modern viewpoint.
 Joel Spencer, From Erdos to Algorithms
postscript
pdf
Description
Appeared in Discrete Math vol. 136 (1994), 295304
 Joel Spencer, Nine Lectures on the Probabilistic Method
postscript
pdf
Description
Lectures gives at the Summer School of Probability io St. Flour, France.
Covers all aspects of the Probabilistic Method, aimed toward probabilists.
Appeared in Ecole d' Ete' de Probabilite's
de SaintFlour XXI1991 (P.L. Hennequin, ed.) Lecture Notes in Mathematics
1541, SpringerVerlag. pp 293347
 Joel Spencer, On the Edge of Convergence
postscript
pdf
Description
An unpublished expository note that uses Unbounded Search to give
convergent and divergent sums that are very close together, without
calculus.
 Tomasz Luczak and Joel Spencer, When does the Zero One Law hold?
postscript
pdf
Description
Appeared in Journal of the American Mathematical Society, vol. 4, 1991,
451468
 Noga Alon, JeongHan Kim and Joel Spencer, Nearly perfect matchings
in regular simple hypergraphs
postscript
pdf
Description
Take a kuniform hypergraph on N vertices, each vertex in D hyperedges.
Think of k fixed (e.g., k=3) and N,D going to infinity. Suppose further
that any two hyperedges overlap in at most one vertex. Then we show
the existence of a packing with all but ND^{1/(k1)} vertices, with
an extra polylog factor when k=3. This uses a nibble plus some
martingales to show that we stay on the heuristically derived differential
equation. There are good reasons to believe that the 1/(k1) is the
right power of D.
Appeared in Israel J. Math, vol. 100, 1997,
171187
 Talk given at ICM, Zurich 1994
postscript
pdf
Description
Probabilistic Methods
 Noga Alon, Prasad Tetali and Joel Spencer, Covering with Latin Transversals
postscript
pdf
Description
Features an intriguing extension of the Lovasz Local Lemma in which
one doesn't require full independence but rather only that the
correlations are going in the correct way. Appeared in Disc Appl Math,
vol 57 (1995), 110
 Joel Spencer, Maximal Triangle Free Graphs and Ramsey R(3,k)
postscript
pdf
Description
Improves Erdos's 1961 bound by a showing that the random
triangle free process produces a graph with no appropriately
large independent set.
Bounds superceeded by Kim's results but still
an interesting approach. [In 2008, Tom Bohman gave a much more
sophisticated analysis showing that the random triangle free
process gives a graph on n vertices with no independent set
of size \sqrt{n\ln n}, matching Kim's result, which gives the
right value (up to constants) for R(3,k).]
 Joel Spencer, Modern Probabilistic Methods in Combinatorics
postscript
pdf
Description
Talk given at the British Combinatorial Conference, Stirling, summer
1995.
 Saharon Shelah and Joel Spencer, Random Sparse Unary Predicates
postscript
pdf
Description
Appeared in Random Structures and Algorithms, vol. 5 (1994), 375394.
 Joel Spencer, Applications of Talagrand's Inequality
postscript
pdf
Description
An expository description of a new probabilistic inequality of M. Talagrand
and how it can be considered a useful new tool for probabilistic methods.
 Joel Spencer, Randomization, Derandomization, Antirandomization: Three
Games
postscript
pdf
Description
Appeared in Theoretical Computer Science vol. 131 (1994), 415430
 Joel Spencer, ZeroOne Laws with Variable Probability
postscript
pdf
Abstract
An overview of work on ZeroOne laws and allied concepts like Convergence
in various random settings of interest to Discrete Mathematicians.
Appeared in Journal of Symbolic Logic, vol 58 (1993), 114