Studying random networks 

Associate Professor Cecilia Holmgren will receive funding from the Knut and Alice Wallenberg Foundation to recruit an international researcher for a postdoctoral position at the Department of Mathematics at Uppsala University, Sweden.

The goal of the project is to solve important problems in probability theory and combinatorics, especially in the field of random graphs and trees. This is now one of the most dynamic fields in mathematics, due both to its many interesting “pure” mathematical questions and to its important applications in e.g. computer science, physics and biology.

A graph consists of vertices and line segments, connecting some of them pairwise. Connections in random graphs arise at random. An important part of the project is a study of random trees, which resemble the well-known genealogical trees. Random trees are often used as tools when computer scientists analyze data, such as when studying search algorithms.

Split trees form a large class of random trees. These are constructed by using a random process for distributing items (that often symbolize data) to the vertices. Quicksort is the most prominent example of such a model and is an algorithm that is used for searching and sorting data. An important issue in the project is to analyze the extent to which certain types of subtrees so-called fringe trees can provide knowledge of the entire tree structure for different types of split trees.

Percolation theory which studies phase transitions for random processes is another part of the project. The project is particularly focused on bootstrap percolation, which can resemble a model for how an infection is spread in a population. In this model each vertex represents an individual who may or may not have an infection. New infections may arise in individuals who have a certain number of infected neighbors and the dependence of such a model on the initial set of infected individuals can be analyzed. In the project e.g., the time until all individuals in the graph have been infected will be studied.

The project also treats random networks that can be represented by random graph models, e.g., the configuration model. The project analyzes the probability that a correct random graph can be constructed for such a network, so that it does not contain any "self-loop", i.e., any connection that goes back to the vertex itself and no multiple edges between two vertices.

Photo: Uppsala University