Cecilia Holmgren tells about her research on random graphs

When Cecilia Holmgren was 15 in 1999, she had already completed every maths course at her high school and was allowed to study mathematics at Chalmers. She soon became interested in random graphs, random trees, and split trees. When defending her doctoral thesis Split Trees, Cuttings and Explosions in Uppsala (2010), she was the first to establish the general characteristics of split trees, which is a large class of random trees. One well-known type of split tree is binary search trees, which corresponds to the sorting algorithm Quicksort, that is used to sort data.

Cecilia’s research is pure mathematics. It lies at the intersection of probability theory and combinatorics, but large parts of it have practical applications.

“Random graphs and split trees are used, among other things, to develop algorithms for searches and recommendations on the Internet, to study how infections or rumours spread, and to analyse data sorting algorithms. The results can also be applied in artificial intelligence, where studying social networks and developing different types of algorithms are important.”

Cecilia, who is now an associate professor with habilitation, also works with conditional Galton Watson trees, which is another large class of random trees used for instance to describe a family’s survival or extinction.

“I like working with large classes of random graphs at the same time instead of individual random graphs,” she says.

One interesting feature of several random structures is that relatively small changes in probabilities produce large global changes. An example is a family tree. If the number of children in the average family is less than 1, the family dies out, but if the number is larger than 1, it may survive. Another example is the spread of infection, where a small change in immunity/spread (e.g. caused by how many members receive a vaccination) can determine whether an infection dies out or spreads around the world. Such breakpoints are called thresholds and are connected to percolation theory.

Cecilia also works with the configuration model, a general random graph model used in everything from Facebook and other social networks to biological networks such as the brain, telecommunications, and electrical grids.

Cecilia’s success has led to her receiving several large grants, giving her the opportunity to recruit talented doctoral students and postdocs to her research group.

“I am happy to have a strong research group. My PhD students and postdocs are doing exciting work and hold interesting seminars and lectures at conferences. This, in turn, attracts other talented researchers and international contacts.”

The image of the lone mathematician surrounded by stacks of books and checkered paper is an ill fit for Cecilia.

“I enjoy it the most when working with others, both senior researchers, postdocs, and doctoral students. At Uppsala University, I also meet students and am able to spark their interest in my field, which is really nice. Thanks to the University’s reputation and that of myself and my research group, we get many talented students and researchers.”

Random graphs and split trees

A graph consists of nodes and edges between nodes. The nodes can correspond to websites, and the edges then represent links between them, or the nodes can correspond to individuals, and the edges then represent contacts between them, such as sexual relations or handshakes. A tree is a graph where there is only one path of edges between two nodes, that is to say, there are no cycles in the graph. Think of a family tree where the nodes represent individuals, and there is an edge between two individuals if one is a child to the other.

Random graphs and random trees are then graphs and trees generated by random processes. For instance, we can flip a coin to decide if we should draw an edge between two nodes. Split trees are random trees designed to model different sorting algorithms. By studying the corresponding split tree, we can analyse the properties of the algorithm (e.g., the search time, which measures the algorithm’s efficiency).