*** 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