Instructor: Antar Bandyopadhyay (Email: antar (at) isid (dot) ac (dot) in Office: 208 Faculty Building).

Class Time: Tuesday and Friday 11:00 - 12:30 hours in the Seminar Room 2 on the 1st floor of the Administrative Block.

Instructor's Office Hours: Tuesday and Friday 12:30 - 13:30 hours.

Course Duration: May 21, 2013 - July 05, 2013 (7 weeks).

Course Outline:

• Basic probability tools: First and second moment methods. Weak convergence by method of moments. Concentration inequalities for sum of independent Bernoulli variables, binomial and general case. Azuma's inequality (statement only). The FKG inequality for finitely many variables, probability of non-existence. (1 week)
• Two basic models of random graphs (Erdös-Rényi random graphs): binomial random graphs and uniform random graphs. Monotonicity property of these graphs. Asymptotic equivalence of the two models. (1 week)
• Concept of thresholds and proof of every monotone property has a threshold. Thresholds for subgraph containment. Connectivity threshold. Basic idea of sharp thresholds. (2 weeks)
• 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. (2 weeks)

References:

• S. Janson, T. Łuczak and A. Riciński: Random Graphs (ISI, Delhi Library Call Number: 511.5 J35.RG).
• B. Bollobás: Random Graphs (ISI, Delhi Library Call Number: 511.5 B692.RG).
• R. van der Hofstad: Random Graphs and Complex Networks.

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).

Class Presentations:

• Threshold, Sharp Threshold and Threshold for sub-graph containments (Sections 1.5, 1.6 and 3.1 of S. Janson, T. Łuczak and A. Riciński: Random Graphs) by Mr. Souvik Dhara. Date: June 18, 2013.
• Connectivity Threshold (Section 5.2 of R. van der Hofstad: Random Graphs and Complex Networks.) by Mr. Debankur Mukherjee. Date: June 21, 2013.
• The Emergence of the Giant Component (Section 5.2, 5.3 and 5.4 of S. Janson, T. Łuczak and A. Riciński: Random Graphs) by Mr. Sourav Sarkar and Ujan Gangopadhyay. Date: June 25, 2013 and June 28, 2013.

Last modified May 20, 2013.