Prof. Joel Spencer

Courant Institute (New York University)

 

 

Wednesday, June 25, 2008 at 16:30 

Lecture I: Paul Erdös and his Magic

 

 

We give several examples (chosen so as not to require previous knowledge) of teh Probabilistic Method, or Erdös Magic.  We find a "large" independent set in a graph using the random greedy algorithm.  We show the existence of graphs with high girth and high chromatic number by taking an appropriate random graph and adjusting it.  We give Turan's argument for the theorem of Hardy and Ramanujan that (roughly) most n have ln ln n prime factors.  We show that the existence of an asympotically perfect packing (as conjectured by Erdös adn Haim Hanani) under suitable conditions by analyzing the random greedy algorithm.

 

Paul Erdös was a giant of twentieth century mathematics.  He had a unique life style.  He had a multitude of devoted disciples, including this speaker: Paul loved to say: "I have no home, the world is my home", and whether Sydney or Haifa or London or New York, his visits were times of great mathematics and great stories.  We shall attempt to interweave the stories and the mathematics, as "Uncle Paul" did so successfully throughout his long life.

 

 

Thursday, June 26, 2008 at 16:30

 

Lecture II: 76 Years of Ramsey R(3,k)

 

The Ramsey Number  R(3,k) is that least number (dependent on k) so that any triangle-free graph on n vertices must contain an independent set of k vertices.  An examination of (appropriately defined) random graphs and random processes plays a key role in finding the asymptotics of R(3,k).

 

Our story takes us from three youngsters, George Szekeres, Esther Klein and Paul Erdös, in the winter of 1932/3 through Greewood, Gleason, Graver, Yackel, Ajtai, Komlos, Szemeredi, Alon, Krivelevich, Kim, Lovasz, Winkler, Suen and Wormald (to name a few!) to very recent work of Bohman. In Bohman's work stability of a system of differential equations plays a key role.

 

Sunday, June 29, 2008 at 10:30

Lecture III: Counting Connected Graphs 

 

 

Asymptotically, how many labelled connected graphs are there with k vertices and, say, 2k edges? We employ random graphs and breadth first search techniques to find the answer.

 

We give a randomized algorithm that efficiently generates a uniformly distributed connected graph with these parameters.  The methodology yields, in many important ranges, an asymptotic estimate for the probability that the random graph G(k,p) is connected.  It also gives the aymptotics for the joint distribution of the number of vertices and edges of the "giant component' of Erdös and Renyi.

 

At heart, we give an asymptotic analysis fo a random walk of length k, something like a Brownian bridge, which is appropriately tilted to the left.  Insights from mathematical physics play a key role.  Our methods work of k vertices and k-l+l  edges as long as both k and l are approaching infinity.