MA 394
Techniques in Discrete Probability (MA 394, Fall 2018)

Instructor: Riddhipratim Basu. Email:
Meeting:LH-1, IISc Math department, TTh 14:00- 15:30.
Grading: Students taking this course for credit are required to scribe two lectures and submit typed up notes with all exercises solved. They are also required to do a (reading) project and submit a report and give a presentation on the same at the end of the semester. The relative weights of these two components will tentatively be 40-60, but is subject to change.

This is an ICTS/IISc Graduate course aimed at Ph.D. students from different fields who expect to use discrete probability in their research. Graduate level measure theoretic probability will be useful, but not a requirement. I expect the course will be accessible to advanced undergraduates who have had sufficient exposure to probability. For more information about the course, see this page.

Weekly Schedule: I shall be posting a weekly schedule of covered topics here, and post the scribe notes when available. Be aware that lecture notes below have not been reviewed properly and may contain inaccuracies.
August 7: Coupling and applications. Total variation distance, mixing times. Notes (Scribe: Sahasranand K. R.)
August 9: Mixing times continued. Notes. (Scribe: Neeladri Maitra)
August 14: Grand couplings, and contractions, first moment method, thresholds in random graphs. Notes. (Scribe: Manan Bhatia)
August 16: Second moment method. Notes. (Scribe: Raghavendra Tripathi)
August 21: Weighted second moment for k-SAT. Notes. (Scribe: Lakshmi Priya M. E.)
August 23: Concentration inequalities: Chernoff, Azuma-Hoeffding. Notes. (Scribe: Shivika Narang)
August 28: Applications of Azuma-Hoeffding and bounded difference inequalities. Notes. (Scribe: Sabyasachi)
August 28: Isoperimetric inequalities and concentration of measure. Talagrand's inequality and applications. Notes. (Scribe: Ratul Biswas)
September 4: Basics of Bernoulli percolation, non-trivial phase transition, Burton-Keane. (Scribe: Ashwin)
Week of September 3: FKG and BK, Russo's formula. (Scribe: Aditya)
Week of September 10: No class.
Week of September 17: sharp transition, Kesten's theorem, RSW.
Week of September 24: Subadditivity and applications, shape theorem for FPP.
Week of October 1: FPP continued, variance bounds, LPP.
Week of October 8: Fourier analysis on hypercube, noise sensitivity.
Week of October 15: Kahn-Kalai-Linial bounds, applications.
Week of October 22: Sharp threshold phenomena, Friedgut's theorem.

Possible Project Topics: See below for a list of possible project topics. You are free (and encouraged) to choose your own project topic subject to instructor approval. Please write/talk to me if you want more information about any of the topics mentioned below.
1. Coupling from the past.
2. Approximate counting and FPTAS.
3. Random Constraint Satisfaction Problems. (Neeladri)
4. Combinatorial Optimization in random environment.
5. Conformal Invariance and Cardy's formula. (Lakshmi Priya)
6. Random Cluster Model.
7. Bootstrap Percolation.
8. Long range percolation.
9. Busemann Functions and applications.
10. Representation theory of symmetric group and applications. (Ratul/Raghavendra)
11. Superconcentration and chaos.
12. Property testing. (Vipul)
13. Stein's method beyond Poisson approximation. (Raghavendra ?)
14. Different models of random graphs: random regular graphs, preferential attachment models, random graphs with power law degree distribution. (Sabyasachi ?)
15. Community detection in networks.

Copyright © 2011 ICTS