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

Project S1

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

• Assigned To: Ritwick Pal (BS2222)

• Goal:The main goal of this project is to establish the famous formula for the total number of tress on n labeled vertices. The proof may be given through the connection with Critical Galton-Watson Tree. The project should also relate this result with other combinatorial and/or probabilistic results, such as, Matrix-Tree Theorem, Ballot Problem, Möbius Inversion Formula.

• Remarks: This is essentially a reading project. A lot of materials can be found in the Section 3.6 of R. van der Hofstad: Random Graphs and Complex Networks: Volume I. book and other references therein.