CSL866: Percolation and Random Graphs
I semester: 2007-08
Arzad Kherani and Amitabha Bagchi
Class Timings: M Th 5PM to 6:30PM .
Room: CSE Discussion room, 404 Bharti Building.
Overview
The theory of percolation in grids has had wide application in physics
and is beginning to make its presence felt in the area of computer
networks. We provide an introduction to this area, presenting the
notion of critical probabilities, analyzing the subcritical and
supercritical phases, building towards Kesten's famous proof that the
critical probability for the 2-dimensional grid is 1/2.
Additionally we study various random graph models and their applicability
to the study of wireless and ad-hoc networks.
A detailed breakup of topics will follow.
Lecture notes
- Lecture 1. (30/7, 2/8, 6/8): Overview of percolation
theory, Borel-Cantelli lemmas, Kolmogorov's zero-one law (ps, pdf.)
Scribe: Amitabha Bagchi. Posted 9th August 2007.
- Lecture 2. (9/8, 13/8): Intro to percolation and critical
probability (ps, pdf.)
Scribe: Ayush Nayyar. Posted 5th September 2007.
- Lecture 3. (23/8): Increasing events and the FKG inequality (ps, pdf.)
Scribe: Arpit Nanda. Posted 6th September 2007. Reposted with general FKG inequality added 20th September 2007.
- Lecture 4. (27/8, 6/9): BK Inequality, with some example
applications (ps, pdf.)
Scribe: Arindam Pal. Posted 31st August 2007. Reposted with examples
18th September 2007.
- Lecture 5. (10/9): Russo's formula (ps, pdf.)
Scribe: Sumeet Agarwal. Posted 17th September 2007.
- Lecture 6. (17/9, 24/9, 27/9, 1/10): Subcritical phase:
Exponential deacy of the radius of the open cluster (ps, pdf.)
Scribes: Amandeep Singh and Rohan Choudhary. Posted 6th November
2007.
- Lecture 7. (4/10, 8/10): Subcritical phase: Exponential decay of
the cluster size distribution. (ps, pdf.)
Scribe: Arindam Pal. Posted 19th October
2007.
- Lecture 8. (11/10): Subcritical phase: Asymptotic tail behaviour
of the radius of an open cluster. (ps, pdf.)
Scribe: Saptak Narula. Posted 23rd October
2007.
- Lecture 9. (22/10): Supercritical phase: The infinite cluster is
unique. (ps, pdf.)
Scribe: Arpit Nanda. Posted 20th November 2007.
- Lecture 10. (25/10, 29/10, 1/11): Supercritical phase: Exponential
decay of the radius of a finite cluster. (ps,
pdf.)
Scribe: Anil Kumar Maheshwari. Posted 21st November 2007.
- Lecture 11. (15/11): The critical probability for the
2-dimensional lattice is 1/2. (ps, pdf.)
Scribe: Saptak Narula. Posted 20th November 2007.
- Lecture 12. (19/11, 22/11): Percolation on general finite
graphs.
Download the paper by Alon, Benjamini and Stacey here. Scribe notes forthcoming.
Exams and homework assignments
- Minor 1. (ps, pdf). Posted 30th August 2007.
Due in class on Thursday, 6th September 2007.
Solutions. (ps,
pdf).
Local access only. Posted 20th September 2007.
- Minor 2. (ps, pdf). Posted 22nd October 2007.
Due in (or before) class on Monday, 29th October
2007.
Note. Solutions must be submitted in latex.
- Major exam. (ps, pdf). Posted 23rd November 2007.
Due in my mailbox by 11:59AM on Wednesday, 28th November
2007.
The exam can be handwritten, it need not be latexed.
Other notes and texts
- The primary text for the intro to Percolation will be
Percolation 2nd ed. by Geoffery Grimmett,
Springer, 1999.
- Lecture notes from Grossglauser and Thiran's class on Methods and
Models for Random Networks are available here.
Evaluation
| Scribing lecture notes | 25% |
| Homework | 15% |
| Minor I | 20% |
| Minor II | 20% |
| Major | 20% |
Scribing
- Each student will be expected to scribe at least one lecture. This
will involve taking careful and complete notes during the lecture and
then typing them out in latex.
- Please download the template file and the
latex class file that will be needed.
- Three days after the lecture the first draft will be due. This will
have to be emailed either to Dr Bagchi or Dr Kherani, whoever gave the
lecture that is being scribed. If the lecture is given by a guest then
please send the first draft to Dr Bagchi.
- The instructor will return
the draft with comments and, three days after that, a final version will
have to be made and submitted with all the required changes
incorporated.
- Here are some general
guidelines which may help you with scribing class notes. Please
read them before you begin typing.
- Also the tex source for lecture
1 and lecture
4 are available for your reference (local access only.)
- Some latex tips here.
Arzad
Kherani
Amitabha
Bagchi