Random Graphs 

(Optional Course in Probability for the B. Stat. Third Year)

Academic Year 2020-2021 : Semester II

Instructor : Partha Pratim Ghosh [Certificate]

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.
    
    

Reference Texts :

1. S. Janson, T. Łuczak and A. Riciński: Random Graphs.

2. B. Bollobás: Random Graphs.

3. R. van der Hofstad: Random Graphs and Complex Networks: Volume I & II.