Level: MSci, MSc
Title: The giant component in random graphs
Supervisor:

Prof. Malwina Luczak
Research Area: Probability and Applications [Including Statistics]
Description:

There is a natural method to generate a random graph with a given degree sequence; under certain conditions on the degree sequence, the random graph is likely to have one "giant'' connected component, containing a constant proportion of the vertices, with the remaining vertices on small components. In the limit as the number of vertices tends to infinity, with the proportion of vertices of each degree fixed, the expected proportion of vertices in the giant component can be calculated [1]. The same is true of the k-core, which is the largest connected subgraph where every vertex has degree at least k [2].

  1. S. Janson and M. Luczak, A new approach to the giant component problem, Random Structure and Algorithms 34 (2009): 197–216.
  2. S. Janson and M. Luczak, A simple solution to the k-core problem, Random Structures and Algorithms 30 (2007): 50–62.
Further Reading:
Key Modules:

MTH4105 Introduction to Mathematical Computing

MTH6141 Random Processes

MTH5121 Probability Models

MTH6109 Combinatorics
Other Information:
Current Availability: Yes