INDIAN STATISTICAL INSTITUTE

(Headquarters at Kolkata)

203 B. To Road, Kolkata 700 108

Random Graphs

Optional Course for B. Stat. IIIrd Year

Academic Year 2024 - 2025: Semester II

Instructor: Antar Bandyopadhyay
Email: antar (at) isid (dot) ac (dot) in
Office: (when in Delhi) Room # 208 on the First Floor of the Faculty Block, ISI, Delhi
(when in Kolkata) Room # 3.4 on the Third Floor of the A. N. Kolmogorov Bhavan, ISI, Kolkata

Class Time: Tuesday 04:00 PM - 06:00 PM and Thursday 09:30 AM - 11:30 AM (Note: TWO hours on every day of lecture)

Lecture Hall: Class Room # 704 on the Seventh Floor of the S. N. Bose Bhavan, ISI, Kolkata.
Also check the Google Classroom for all information.

Course Duration (including examinations): January 06 - May 09, 2024
[Total of 18 Weeks = 7 Weeks of Classes + 1 Midterm Examination Week + 7 Weeks of Classes + 1 week of study break + 2 weeks Final Examination Weeks].

Midterm Examination:
Date: February 24, 2025 (Monday)
Duration: 10:30 AM - 12:30 PM (Two hours)
Venue: Room No. 508 on the 5th floor of the Library Building

Final Examination:
Date: TBA
Duration:TBA

Course Outline:

• General Probability Topics:
  • Revision of Inequalities: First and Second Moment Methods.
  • Weak convergence by method of moments.
  • Basic Concentration inequalities for sum of independent Bernoulli variables, binomial and general case.
  • Basic theory of discrete time Galton-Watson branching processes; extinction probability. Poisson Galton-Watson Tree.
  
  

• Classical Random Graphs:
  • Two basic models of random graphs, also known as, Erdős-Rényi random graphs: binomial random graphs and uniform random graphs.
  • Concept of Monotonic properties. Asymptotic equivalence of the two models.
  • Concept of thresholds and proof of every monotone property has a threshold. Connectivity threshold. Basic idea of sharp thresholds.
  • Dense and sparse random graphs.The evolution of the sparse random graph, the emergence of the giant component, phase transition. Sub-critical, critical and super-critical phases.
  • Random regular graphs. Configuration model. Asymptotic of small cycles.
  
  

• Other Models of Random Graphs:
  • Configuration Model revisited. Asymptotic Degree distribution.
  • Albert-Barabaśi model of preferential attachment model. Asymptotic Degree distribution.
  • Definition and basic properties of Geometric Random Graphs. Question of connectivity.
  • Modern models: Super-linear, sub-liner and de-preferential attachment models.

References:

• R. van der Hofstad: Random Graphs and Complex Networks: Volume I & II.
• S. Janson, T. Łuczak and A. Riciński: Random Graphs.
• B. Bollobás: Random Graphs.

Prerequisites:

• Real Analysis (at the level of Principles of Mathematical Analysis, W. Rudin).
• Liner Algebra (at the level of Finite Dimensional Vector Spaces, P. R. Halmos).
• Basic Probability (at the level of Introduction to Probability Theory, P. G. Hoel, S. C. Port and C. J. Stone).

Grading Policy:

• Midterm Exam: 20% of the total credit
• Projects/Presentations: 30% of the total credit
• Final Exam: 50% of the total credit

Projects:

• List of Proposed Projects:

  • Single Student Projects:

    • Project S1: Cayley's Formula and Uniform Spanning Tree of the Complete Graph on n vertices

    • Project S2: Large Deviation Bounds: Binomial and Poisson Rate Functions

    • Project S3: Asymptotic Degree Distribution of Erdős-Rényi Binomial Random Graphs

    • Project S4: Sub-Graph Containment Threshold for the Erdős-Rényi Binomial Random Graphs

    • Project S5: Central Limit Theorem for the Size of the Giant Component for the Super-Critical Erdős-Rényi Binomial Random Graph

    • Project S6: Erdős-Gallai Theorem

    • Project S7: Factorial Moment Convergence and Weak Convergence to Poisson Distribution

  • Paired Student Projects:

    • Project P1: Studying the Structure of the Local Neighborhood of a Randomly Selected Vertex of a Large but Sparse Erdős-Rényi Binomial Random Graph

    • Project P2: Comparison between Configuration Model with i.i.d. Binomial(n, p) distribution and corresponding Erdős-Rényi Binomial Random Graph

    • Project P3: Collect a Data of "Friendship Network" among the B.Stat. Students who are currently present in ISI, Kolkata and Fit the Erdős-Rényi Binomial Random Graph

• Policies:

  • There are five single student projects and three double students projects.
  • Each project will be assigned to one student or to a pair of students.
  • Students should discuss among themselves and make appropriate choice and pairs as they deem fit.
  • Each project need to have a report to be submitted electronically within the deadline which will be announced in the class. So a total there will be eight project reports.
  • Each student has to give a final presentation for 30 minutes on his/their work. Single student projects will be of 30 minutes duration while a pair project will have an one hour presentation back to back by the two students who have taken up the project.
  • The grading will be based on the reports and the final presentations.
  • The dates of the presentations will be announced later in the class.

Exam Policies:

• The Midterm and the Final Examinations will be open notes examinations. That means, students will be allowed to bring his/her own hand written notes, study materials, list of theorems etc. But no printed or photocopied materials will be allowed.
• Any unfair means used by any students in the examinations will be dealt with the strictest possible measures, as per the Institute rules. In particular, if any student is found to be using any kind of unfair practice during any of the examinations (including the quizzes) then he/she will be awarded ZERO in that examination.

Regrading Policy:

• Regrading of the exams will only be undertaken in cases where, you believe there has been a genuine error or misunderstanding. Please note that our primary aim in grading is consistency, so that all students are treated the same; for this reason, we will not adjust the score of one student on an issue of partial credit, unless the score allocated clearly deviates from the grading policy we adopted for that problem.
• If you wish to request a regrading of a homework or exam, you must return it to the instructor with a written note on a separate piece of paper explaining the problem.
• The entire assignment or the exam may be regraded, so be sure to check the solutions to ensure that your overall score will go up after regrading.
• All such requests must be received within one week from the date on which the homework or exam was made available for return.

Last modified on April 16, 2025.