Random Graph Percolation
Lead Research Organisation:
University of Cambridge
Department Name: Pure Maths and Mathematical Statistics
Abstract
The study of percolation is the study of random graphs generated through the following process. We start with a given a graph and assign each vertex (or edge) a value between 0 and 1 and independently retain that vertex (or edge) with that probability. The main questions are what the likely structure is of the graph that remains, e.g. when starting with the two dimensional grid and using some uniform probability p, will there be an infinite connected component. Within the topic of percolation, I focus on different problems for instance the bunkbed conjecture which asserts the following. Starting with a graph G, we form the bunkbed of G, by considering two disjoint copies of G and connecting the corresponding vertices. We consider percolation on the bunkbed graph with the restriction that corresponding edges in the two copies of G must be retained with the same probability. The conjecture now asserts that the probability that two vertices u and v in the same copy of G have a greater probability of being connected than the corresponding vertex u' in the other copy of G has of being connected to v. In my first year, I have proved this for complete graphs G and I hope to extend the proof to wider classes of graphs and ideally to all graphs.
Organisations
People |
ORCID iD |
Bela Bollobas (Primary Supervisor) | |
Peter Van Hintum (Student) |
Publications
Herrman R
(2022)
Capture times in the bridge-burning cops and robbers game
in Discrete Applied Mathematics
Herrman R
(2020)
Capture times in the Bridge-burning Cops and Robbers game
Van Hintum P
(2021)
Combinatorics and Metric Geometry
Van Hintum P
(2019)
Locally biased partitions of Z n
in European Journal of Combinatorics
Dvorák V
(2022)
Radius, girth and minimum degree
in Journal of Graph Theory
Herrman R
(2021)
The ( t , r ) broadcast domination number of some regular graphs
in Discrete Applied Mathematics
Van Hintum P
(2019)
The bunkbed conjecture on the complete graph
in European Journal of Combinatorics
Dvorák V
(2021)
The eternal game chromatic number of random graphs
in European Journal of Combinatorics
Studentship Projects
Project Reference | Relationship | Related To | Start | End | Student Name |
---|---|---|---|---|---|
EP/N509620/1 | 01/10/2016 | 30/09/2022 | |||
1951104 | Studentship | EP/N509620/1 | 02/10/2017 | 30/09/2020 | Peter Van Hintum |