Probabilistic Combinatorics and Algorithms | MATH 261A
Jacques Verstraete
Department of Mathematics UCSD
9500 Gilman Drive
La Jolla CA 92093-0112
jacques at ucsd dot edu
Content.by section
general.information
Instructor : Jacques Verstraete Office 6250 x42651Class times : 0900-0950 Mon Wed Fri | Class location : APM 5402
Units 4 | MATH 261A
OFFICE HOURS 6250 MW 1330-1530
jacques at ucsd dot edu
Corrections to jacques at ucsd dot edu.
books.notes
Recommended reading includes The Probabilistic Method, by N. Alon and J. Spencer and Random Graphs by B. Bollobas. A basic knowledge of probability, analysis, and linear algebra is required. For background in probability theory, Probability with Martingales by D. Williams and An Introduction to Probability Theory with applications by W. Feller are ideal, though both contain more theory than we will actually use. A set of notes will be provided for those attending the course as the course is lectured. For the assignments as well as the lectures, please email me if you see typos.
assignment.files
There is no exam in this course, and no written work will be submitted. There will be three assignments, roughly every three weeks. I will require each student to present solutions to one or two problems on the assignment. Agreement between the instructor and students will be reached one week before the presentations on which students should prepare which problems. It is on these oral presentations that you will be graded for the whole course, and as such, the presentations are to be taken seriously and they are to be thorough.
Course.Outline
The following sums up the central theme of probabilistic methods in combinatorics. It is a quote from Tim Gowers' paper entitled the two cultures of mathematics.
if the constraints seem to force the extremal examples to be spread about in a uniform sort of way
then choosing an example randomly is likely to give a good answer
The lectures will begin with the basic method: linearity of expectation, Markov and Chebyshev inequalities, and the deletion method, with short but attractive applications in many areas of mathematics. Then we move on to the slightly more advanced topic of concentration of measure and martingales, including Chernoff's Bound, Hoeffding-Azuma inequalities, Talagrand inequality, and correlation inequalities. After this, we move on to special topics, including random graphs, pseudorandom graphs, extremal combinatorics, and algorithms. The emphasis will be on methods and ideas, rather than just solving isolated problems.