Supervisor: Dr Omer Bobrowski
Project description:
In 1959, Erdős and Rényi established the study of random graphs, analysing the phase transition where a uniform random graph becomes connected. In this project we explore a higher-dimensional analogue of this phenomenon known as “homological connectivity”.
Given a random graph, we can look for cliques in the graph and add the corresponding faces (triangles, tetrahedra, etc.) to form a random simplicial complex. Considering this high-dimensional random structure, we are interested in its homology, i.e., structures such as “holes”, “air-pockets”, and their higher-dimensional analogues known as “k-cycles”. If the random graph is sufficiently dense, it contains no holes, and its homology is trivial. In this project we will focus on the transition where homology vanishes (i.e. all holes are filled).
Previous work has established roughly where these transitions take place. Our goal in this project is to provide a sharper description of such phase transitions, along with providing detailed Poisson limits inside the critical window. To do so, we plan to develop a Morse-theoretic approach to this problem. Briefly, discrete Morse theory allows us to identify faces in the simplicial complex that are “critical”, in the sense that they either generate new cycles or terminate existing ones.
Once the theory is established for the uniform random graph, we plan to examine a different type of a clique complex known as the Vietoris-Rips complex. Here the vertices are formed by random point clouds, and connections are made by proximity. While this object is of a similar nature, the source of randomness is vastly different, and we expect the analysis of this setting to provide new challenges.
Finally, we remark that homological connectivity is tightly related to contemporary challenges in topological data analysis. Specifically, it provides significant insight into the problem of “topological inference” – the recovery of the structure underlying the data.
Further information:
How to apply
Entry requirements
Fees and funding