INDIAN STATISTICAL INSTITUTE

(Headquarters at Kolkata)

203 B. To Road, Kolkata 700 108

Random Graphs

Optional Course for B. Stat. IIIrd Year

Academic Year 2019 - 2020: Semester II

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

Class Time: Tuesday and Friday 11:00 AM -- 01:00 PM (Note: TWO hours on every day of lecture)

Lecture Hall: CSSC VC Room on Fourth Floor of the S. N. Bose Bhavan, or Class Room # 504 on the Fifth Floor of the S. N. Bose Bhavan.

Course Duration (including examinations): January 13 - May 15, 2020
[Total of 18 Weeks = 7 Weeks of Classes + 1 Week of Break (February 24 - February 28, 2020) + 1 Midterm Examination Week + 7 Weeks of Classes + 2 Final Examination Weeks].

Midterm Examination:
Date: March 03, 2020
Duration: 14:30 hours - 16:30 hours
Venue: Class Room # 520 on the Fifth Floor of the S. N. Bose Bhavan

Final Examination:
Date: In the week July 20 - 24, 2020
Duration: 5 days (TAKE HOME)

Course Outline:

• General Probability Topics:
  • Revision of the 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.
  
  

References:

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

Practice Problems for the Midterm (all are from Random Graphs and Complex Networks: Volume I by R. van der Hofstad):

• Exercises: 2.5, 2.6, 2.7, 2.13, 2.14, 2.15, 2.16, 2.17, 2.18, 2.19;
• Exercises: 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7, 3.24;
• Exercises: 4.1, 4.2, 4.4, 4.5, 4.6, 4.22;
• Exercises: 5.6, 5.7, 5.8, 5.16.

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: 30% of the total credit.
• Final Exam: 70% of the total credit (including 40% for the Project and Class Presentation).

Projects:

• List of Proposed Projects:

  • Project 1: Sub-Graph Containment Threshold for the Erdős-Rényi Binomial Random Graphs : Report; Online Presentation Slides

  • Project 2: Cayley's Formula and Uniform Spanning Tree of the Complete Graph on n vertices : Report; Online Presentation Slides

  • Project 3: Asymptotic Degree Distribution of Erdős-Rényi Binomial Random Graphs : Report; Online Presentation Slides

  • Project 4: Studying the Structure of the Local Neighborhood of a Randomly Selected Vertex of a Large but Sparse Erdős-Rényi Binomial Random Graph : Report; Online Presentation Slides

  • Project 5: Connectivity Properties and Structure of Random Graphs Obtained by Vertex Percolation on Erdős-Rényi Binomial Random Graph : Report; Online Presentation Slides and Online Presentation Slides

  • Project 6: Typical Distance between Two Randomly Selected Vertices of a Erdős-Rényi Binomial Random Graph : Report; Online Presentation Slides and Online Presentation Slides

• Policies:

  • There are four single student projects and two double students projects.
  • Each group consisting of only one students or at most two students will be submitting one report on his/their work and will make a final presentation for 20 or 40 (= 20 x 2) minutes each depending on whether there are one or two student(s) in the group respectively.
  • The grading will be based on the reports and the final presentations.
  • Each student will give presentation for 20 minutes on the part they have worked.
  • The dates of the presentations are June 17 & 18, 2020. The last date of submission of the reports is June 07, 2020. You must submit the reports electronically.

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 homeworks or 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 June 26, 2020.