Description
The course is an elective for M.Math 2nd year students. The prerequisites are measure theoretic probability, point set topology and some basic graph theory. Knowledge of advanced probability (limit theorems, weak convergence, martingales et al.) will be helpful but not strictly necessary. M.Math students are strongly recommended to attend Advanced Probability course in parallel.
General Information
D. Yogeshwaran (a.yogesh[AT]isibang.ac.in)
• Dense Graphs, Graph limits and Graphons.
SPARSE GRAPH LIMITS :
• Galton-Watson trees - Extinction probability and other basic properties.
• Sparse Erdos-Renyi random graphs - Subgraph counts, Cycle counts and Poisson approximation.
• Local weak convergence - Converging graph sequences. Basic examples. Convergence of Erdos-Renyi graphs. Applications to subtree counts and phase transition.
(Primary references for this part are Bordenave's notes and van der Hofstad's book - Volume II)
2. Introduction to Random Graphs - Alan Frieze and Michael Karonski
(https://www.math.cmu.edu/~af1p/Book.html)
3. Lecture notes on random graphs and probabilistic combinatorial
optimization - Charles Bordenave (http://www.i2m.univ-amu.fr/perso/charles.bordenave/_media/coursrg.pdf).
4. Random Graphs and Complex Networks - Remco van der Hofstad (https://www.win.tue.nl/~rhofstad/NotesRGCNII_11_07_2020.pdf and
https://www.win.tue.nl/~rhofstad/NotesRGCN.pdf )
5. Large Networks and Graph Limits - Laszlo Lovasz (American Mathematical Society)
6. Bollobas & Riordan - https://arxiv.org/abs/0812.2656
7. Spectra of sparse random graphs - J. Salez. https://www.ceremade.dauphine.fr/~salez/spectra.pdf
8. Lecture Notes on Random Geometric Models --- Random Graphs, Point Processes and Stochastic Geometry - B. Blaszczyszyn.
https://hal.inria.fr/cel-01654766
9. R. Abraham & J-F. Delmas : AN INTRODUCTION TO GALTON-WATSON TREES AND THEIR LOCAL LIMITS https://cermics.enpc.fr/~delmas/Publi/survey.pdf
10.Graph limits and exchangeable random graphs
PERSI DIACONIS AND SVANTE JANSON
https://arxiv.org/pdf/0712.2749.pdf
There will be two series of lectures in parallel - one on sparse graph limits (by D. Yogeshwaran) and the other on dense graph limits (by Siva Athreya).
First Class will be on Sep 1.
2 Take home exams : 25+25
Piazza and Class Participation : 5-10.
Announcements
At ISI, Bangalore.
Random Walks on Graphs - D. Yogeshwaran.
Topics in Applied Stochastic Process - Siva Athreya.
Theory of Large Deviations - Parthanil Roy
At ISI, Kolkata.
Weak Convergence and Empirical Processes - Soumendu Sundar Mukherjee
Brownian Motion and Diffusions - Arijit Chakrabarty
At IISc.
Probability in High Dimensions - Anirban Basak
Some more courses may be listed soon. You can contact the faculty if you are interested in the course.
Some mini-courses / Workshops. See http://math.iisc.ernet.in/~manju/Seminar/seminar.html for details.
#pin
Dear All,
I could not find a reference for Akshay's question : delta measures being extreme points,
but from some past references I discovered the above proof. Please let me know if it resolves.
best wishes
SIva
Starting tomorrow (20th October) onwards, the Tuesday lectures will be from 3.30 - 5.00 PM. The zoom link remains the same.
Sorry about the late notice again.
Dear All,
I have posted HW2. I will set it up on moodle for students enrolled in the course to submit online.
Thanks. Best wishes Siva
Please use Thursday zoom class link for Tuesday class. This is only for tomorrow.Thanks Siva
Assignment 1 for Sparse Random Graphs has been posted.
Students who are not crediting the course are requested not to post the solutions.
Once the deadline is over, the solutions of the crediting students will be posted online and then everybody is welcome to comment and discuss them.
Title: SG-Assignment1.pdf
http://www.piazza.com/class_profile/get_resource/kdepbsr4n8v7gt/kewvgtulsq74m
Due date: Sep 20, 2020
You can view it on the course page: https://piazza.com/isibang.ac.in/fall2020/m22020rgl/resources
Hi,
The last calculation (T2 for triangle counts) was perhaps a little quick for some of you. I have re-done it in the notes with some more explanations. I have also written-up the complete proof. I will go through this again during the Thursday class.
I forgot to record today's lecture. Sorry about it. Please read the notes and if there are any issues, do email me. I shall try to hold an extra class next week to clarify doubts or re-explain some parts.
This Thursday (10th September 2020), the class will be on sparse random graphs by me. The class link is same as that of Tuesday one.
Next week, both the classes will be on dense random graphs by Siva.
| Name | Office Hours | |
|---|---|---|
Yogeshwaran | When? Where? | |
Siva Athreya | When? Where? |