Random Graphs

Spencer, Joel

Graduate Division

Computer Science


Spencer G22.3033-006 Random Graphs Tu 5-6:50 wwh 513 Special Topics: Random Graphs Spring 2004 Prof. Spencer Description: Equally appropriate titles would have been "Probabilistic Combinatorics" or "The Probabilistic Method" or (personal favorite) "Erdos Magic." The Probabilistic Method is a lasting legacy of the late Paul Erdos. For "Uncle Paul" the purpose was to prove the existence of a graph, coloring, tournament, or other combinatorial object. A random object would be described, and then one would show that that object had the desired properties with positive probability. Today we are very interested in algorithmic implementation, both deterministically and with random algorithms. There is further great interest (the official title) in the study of random discrete structures (not just graphs, though that is the main one) for their own sake. The course involves probability, Discrete Math, and algorithms. Probability results include Chernoff Bounds, Martingales, the Lovasz Local Lemma and the Janson Inequalities and will be derived from scratch. Topics include: Ramsey Numbers, Continuous Time Greedy Algorithms, Graph Coloring, Discrepancy, the Liar Game and the Tenure Game. Prerequisites: Only that elusive "mathematical maturity." This topic takes from several areas but the material will be developed in the course. An acquaintance with, say, variance (in probability) and/or chromatic number (in graph theory) will be helpful but not mandatory. Text: Noga Alon, Joel Spencer, The Probabilistic Method, second edition publisher: John Wiley, 2000 More Info: Contact Prof Spencer directly at spencer@cims.nyu.edu or check out his website: http://cs.nyu.edu/cs/faculty/spencer and click on The Probabilistic Method under Topics.