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 k-element subsets of an n-set (n approaching infinity) with no l-set 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 k-sets randomly and consider sequentially, accepting if possible) is shown to work. Analyzing it leads to an interesting branching process. Self-review: Wonderful Stuff! Random Structures and Algorithms, vol 7, 1995, 167-172

  ---

• 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 $k-1+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, 1294-1320)
  

  ---

• 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), 353-369

  ---

• 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 Erdos-Renyi 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), 587-628

  ---

• 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), 307-322

  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, Logic and Random Structures
  pdf tex ps
  Description
  An expository account of Zero-One Laws, geared more to the logician than to the combinatorialist. A chapter in Finite Model Theory and Its Applications, Springer, 2007

  ---

• 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), 720-724
  

  ---

• 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), 237-264
  

  Other Good Stuff

  ---

• Moumanti Podder, Joel Spencer, First Order Probabilities for Galton Watson Trees
  pdf
  Description
  G-W trees with Poisson mean lambda children are considered. We describe quite fully what the probabilities can be of first order properties (allowing quantification over vertices, but not sets), conditioning on the tree being infinite. Basically they can have finite towers of base e exponentiations.

  ---

• Nikhil Bansal, Joel Spencer, On-Line Balancing of Random Inputs.
  pdf
  Description
  Paul is sending n RANDOM +1,-1 vectors v_i of dimension n. Carole must ON-LINE select signs eps_i for each v_i so that the signed sum has ALL coordinates with absolute value less than K\sqrt{n}. Carole can do it! (Random Structures and Algorithms, to appear 2020)

  ---

• Svante Janson, Joel Spencer, Phase Transitions for Modified Erdos-Renyi processes
  pdf
  Description
  Detailed exploration of the Bohman-Frieze process near criticality. Also, detailed exploration of the Erdos-Renyi process beginning with a fixed (fairly, but not totally general) graph H. In both cases it is indicated that these processes and standard Erdos-Renyi 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), 305-329.

  ---

• 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 Erdos-Renyi behavior. Random Structures and Algorithms, vol 36 (2010), 80-89

  ---

• 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 631-658)

  ---

• 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, 137-184. pdf
  Random subgraphs of finite graphs: II. The lace expansion and the triangle condition, Annals of Probability, vol 33, 2005, 1886--1944 pdf
  Random subgraphs of finite graphs: III. The phase transition for the n-cube, Combinatorica, vol 26, (2006), 395-410. pdf
  Description
  A Series of papers giving the phase transition for the random subgraph of the n-cube, including finite analogues to the triangle condition and mean field behavior.

  ---

• Christian Borgs, Jennifer Chayes, Henry Kesten, Joel Spencer, Birth of the Infinite Cluster: Finite-Size 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 153-204

  ---

• Mihyun Kang, Will Perkins, Joel Spencer The Bohman-Frieze Process Near Criticality
  pdf
  Description
  Detailed exploration of the Bohman-Frieze 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, zero-sum 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), 165-168

  ---

• 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), 2072-2090

  ---

• 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 Erdos-Renyi 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), 111-151)

  ---

• 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 Super-Linear 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), 121-163 (with Roberto Oliveira)

  ---

• Bela Bollobas, Oliver Riordan, G. Tusnary and Joel Spencer, The degree sequence of a scale-free 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, 279-290

  ---

• 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), 225-251)

  ---

• 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), 69-89

  ---

• 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) 537-559.

  ---

• Ioana Dumitriu and Joel Spencer, The Two-Batch 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), 347-358

  ---

• 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 Zero-One 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 n-1+k edges is given in terms of the k-th 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), 195-204

  ---

• 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), 295-304

  ---

• 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 Saint-Flour XXI-1991 (P.L. Hennequin, ed.) Lecture Notes in Mathematics 1541, Springer-Verlag. pp 293-347

  ---

• 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, 451-468

  ---

• Noga Alon, Jeong-Han Kim and Joel Spencer, Nearly perfect matchings in regular simple hypergraphs
  postscript pdf
  Description
  Take a k-uniform 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/(k-1)} 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/(k-1) is the right power of D. Appeared in Israel J. Math, vol. 100, 1997, 171-187

  ---

• 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), 1-10

  ---

• 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), 375-394.

  ---

• 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), 415-430

  ---

• Joel Spencer, Zero-One Laws with Variable Probability
  postscript pdf
  Abstract
  An overview of work on Zero-One laws and allied concepts like Convergence in various random settings of interest to Discrete Mathematicians. Appeared in Journal of Symbolic Logic, vol 58 (1993), 1-14

  ---

  ---