Description

‘A Random graph’ means that a given graph structure is random, i.e., vertices could be randomly located and edges between vertices could be randomly connected, according to some probability distribution. One of the famous models is a Erdős–Rényi-Gilbert model G(n, p), where the number of (labelled) vertices is n, and each pair of vertices is connected with probability p independently of every other edge. The main interest of the random graph theory is to study the asymptotic behaviour of G(n, p) when n is very large:

Ø  How many connected components exist in G(n,p)?

Ø  What is a typical size of connected components in G(n,p)?

Ø  How many Hamilton cycles exist in G(n,p)?

In the project, students will choose and study some topics from the random matrix theory, including Erdős–Rényi-Gilbert models, percolation models, Ramsey theory, random matching problems, sorting problems and many other.

Prerequisites

Discrete Math and Probability I, II are essential.

Resources.

• M. Penrose, Random Geometric Graphs, Oxford Studies in Probability 5
• B. Bollobás, Random Graphs, 2^nd edition, Cambridge Studies in Advanced Mathematics 73.

Get in touch by email if you have questions.