Cecilia Holmgren

Projektsammanfattning

Analysis of random graphs and trees with a focus on fringe trees, percolation and random networks

My focus is on random graphs, a research area in the intersection between probability theory and combinatorics. This is one of the most dynamic fields in mathematics with many interesting “pure” mathematical questions as well as important applications in e.g. computer science, physics, bioinformatics and communication reliability (e.g. the Internet). Random graphs are graphs generated by random processes describing how the vertices are connected to each other through edges. I have a special interest in random trees. Trees are connected graphs without cycles, and random trees have become an increasingly hot area due not least to their importance for algorithms in computer science.

My goal is to advance the field of random graphs, especially random trees. By introducing novel methods into the field, alone and in combinations, and using these methods I aim to obtain general results valid for whole classes of random graphs. A special ambition is to combine probabilistic methods, such as Pólya urns, branching processes, Stein’s method with couplings, and renewal theory with innovative combinatorial approaches to solve important problems.

 

Three main topics will be addressed:

 

1. Random trees, with a focus on the study of fringe trees as a novel approach to obtain general results for whole classes of random trees;

 

2. Percolation theory, especially bootstrap percolation, for studies of mathematical “infectiosity” in graph networks (with broad applications in e.g. physics, biology and epidemiology); and

 

3. Random networks, specifically (i) the configuration model (an important random network model due to its proven usefulness for studying various real world networks in e.g. biology and sociology); (ii) CTM protocols (commonly used to avoid collisions in e.g. radio, electricity and internet communications); and (iii) stochastic block models (that have become increasingly important in biological and sociological research on community interactions).

 

Cecilia Holmgren was awarded a Swedish Foundations’ Starting Grant (SFSG) 2017.