*** New for 2006: Analysis of Breadth First Search on Random Graphs

# Random Graphs -- Spring 2006

## Basic Information

Text: The Probabilistic Method, Noga Alon and Joel Spencer, John Wiley & Sons, 2nd Edition. This course could be called The Probabilistic Method or The Erdos Method or, my favorite, Erdos Magic. We will study a variety of random structures with particular emphasis on Random Graphs. We will analyze various algorithms on those structures. We will use random structures to prove the existence of combinatorial objects (this is, more specifically, the Erdos Magic) such as colorings, tournaments, and simultaneous roundoffs. We give methods (2nd moment method, Janson's Inequality, ...) that allow us to estimate and/or bound probabilities, particularly very small probabilities. (A basic knowledge of probability -- expectation, variance, binomial distribution and the like, would be helpful but is not required.) (Also, a prior acquaintance with Discrete Mathematics - graphs, trees, colorings, ... - would be helpful but is not required.) A common theme throughout the course is asymptotic estimation. There will be plenty of big-Ohs, little-ohs, Thetas and Omegas. Grading: Last time we had assignments every week or so that were part of the grade plus an oral exam at the end. I expect to do the same this time around.

## Assignments

Due Jan 30 LaTeX postscript pdf Due Feb 6 LaTeX postscript pdf Due Feb 13 LaTeX postscript pdf Due Feb 27 LaTeX postscript pdf Due Mar 6 LaTeX postscript pdf Due Mar 20 LaTeX postscript pdf Due Mar 27 LaTeX postscript pdf Due Apr 3 LaTeX postscript pdf Due Apr 10 LaTeX postscript pdf Due Apr 17 LaTeX postscript pdf

## Assorted Stuff

Notes on Asymptotics LaTeX postscript pdf Notes on number of Prime Factors (Turan, Erdos-Kac) LaTeX postscript pdf