Math 500, Discrete Probability

Paul Horn
Email: phorn (at) mathcs dot emory dot edu
Office: MSC W434
Office Hours: TBA

Classes: MWF, 11:45-12:35, MSC E406

This is a graduate class. This class will be set up, first and foremost, as a course in discrete probability. We will, however, focus on many applications in combinatorics and graph theory.

From the official course description - Included will be: events and their probabilities, random variables and their distributions, limit theorems, martingales, concentration of probability, random walks and Markov chains.

Our approach will not be particularly measure theoretic (so there is no graduate analysis pre-requisite), but the we will touch on some of the related issues as necessary. As mentioned, this course is focused on applications in combinatorics and probability, so we will touch on some topics which are infrequently covered in a graduate probability course; for instance the Lovasz Local Lemma.

Time depending, I may touch on some related topics: Quasirandomness, Markov Processes on graphs, etc.

Also, there is some flexibility in topics - if you have some topics which you'd really like to have covered, let me know!

Assignment 1 Updated 1/29. Will hand out problems on Monday.
Assignment 2 Again, I may add more over the next few days.
Assignment 3

The survey article I mentioned on concentration inequalities: Concentration inequalities and martingale inequalities - a survey, by Chung and Lu.

The official textbook is Probability and Random Processes by Grimmett and Stirzaker. I will not follow this closely, and it is not required in any true sense, but it will serve as a good reference. Probably some of the assigned problems will come from it's supplemental volume 'One Thousand Exercises in Probability.'

Other volumes I will pull things from (and which may be good references):
The Probabilistic Method by Alon and Spencer: The bible of probabilistic methods in combinatorics.
Graph Colouring and the Probabilistic Method by Molloy and Reed: A book which essentially is a probabilistic method course which builds up and uses the basic probabilistic method tools, motivating them with various colouring problems.
Random Graphs by Bollobas, and also by Janson, Luczak and Rucinski: These two books are great monographs on Random graphs. This isn't a course on random graphs, but we will certainly treat some topics from these books, and I may pull some examples. Both are good books - I find Janson, Luczak and Rucinski to be a bit more accessable, and Bollobas to be a bit more encyclopedic.

Also, these two (drafts of) books may be useful references and are available free online!

Reversible Markov Chains and Random Walks on Graphs by Aldous and Fill - I don't know how much we're actually use the material in here, but it's good to know about. This has been sitting in draft form forever!

Probability on Trees and Networks by Lyons and Peres - This is still in process too, but it's been worked on more lately. Some of it is beyond where we will probably end up in this course, but some may be useful. We may (for instance) talk some about Galton-Watson processes, which are a good mix between 'classical' probability theory and our more discrete flavour.

I will post occassionally (weekly, or so) some problems. We will, 4-5 times during the semester, take a day and discuss problems. Students will present solutions to some of the problems; these will be assigned in advance. The majority of your grade will be determined by your presentations.

There will not be a final during finals week, but currently I am planning to give a takehome final. 2 weeks before the end of class, I will distribute the final (which should not take two weeks to complete, but I want you to give plenty of time.)