Séminaire des doctorants Orléans
Owen Godin: Random graphs and k-core percolation.Owen Godin
Monday 07 July 2025 14:30 - IDP-Orléans - salle de séminaire
Résumé :
The k-core of a graph is the largest subgraph such that all vertices are of degree at least k.
We want to prove a theorem that gives the size of the k-core of a random graph as a function of the number of edges. First, we verify this theorem by performing several simulations. We start by looking at simpler things, such as the number of triangles in a random graph using the first two moments method, then the number of squares. Then we look at the number of subgraphs of fixed size s, satisfying the 3-core condition. Finally, we increase the size of the subgraph and look at the number of subgraphs of size s that contain at least as edges with a > 1.1. Next, we look at random multigraphs, which are graphs that can contain loops and multiple edges. Finally, we transform the vertices into urns and the degrees into balls, which allows us to construct a process that removes the balls one by one and which allows us to obtain at the end the k-core of the random multigraph, which allows us to prove the theorem. Finally, we make the link between the k-core and rigidity.
Liens :