Starting grant enables research on random graphs
When 2022’s grants decision came from the Swedish Research Council, mathematician Annika Heckel was on the recipient list. The four-year starting grant means more time for research on random graphs. “My research is in theoretical mathematics. But random graph theory is never too far away from possible applications to large and disordered networks in our daily lives, from the internet to social networks and models for the spread of disease.”
In the Swedish Research Council’s 2022 call, Annika Heckel at the Department of Mathematics turned out to be one of 46 grant recipients at the Faculty of Science and Technology. For four years, she will receive a total of SEK 4 million for the research project Concentration vs. spread – tools, lower bounds and applications. The subject belongs to probability theory and combinatorics, a branch of mathematics that studies in how many ways something can be done and combined.
Annika Heckel’s project is about random graphs that she and her colleagues usually study using equations and formulas. To illustrate, she takes out a coloured pencil and draws a few scattered dots on the chalkboard.
“A graph is basically a network that we achieve by drawing lines between some of these dots or nodes. It’s something we do randomly.”
Revealing patterns
What researchers strive for is to mimic the disordered networks of reality such as street networks, computer networks or connections between different services. After many repetitions of the random connections and links between the nodes, a pattern arises: a rule of randomness.
“A key phenomenon which has been observed in random graphs, as well as in many other branches of probability theory, is concentration. This means that while a graph statistic may in principle take many different values, in a random graph it almost always comes out as one of only a few values which are close together,” says Annika Heckel.
“Studying concentration helps me understand how ‘randomly’ a graph parameter behaves and how accurate model predictions based on past experience really are.”
Conflicts are described with chromatic numbers
Another goal of the project is to understand the behaviour of the so-called chromatic number of random graphs. This means that the nodes of the graph or network are coloured so that two nodes that are connected to each other by a line may not have the same colour. The chromatic number is then the minimum number of colours needed to colour a network or graph in this way.
According to Annika Heckel, it has many practical applications in scheduling and resource allocation.
“Take, for example, a computer and its various parts. They need to make use of the same resources, but cannot use them at the same time. You then need to calculate the number of time slots needed so that the different uses of the computer do not conflict with each other.”
It may also involve people who need to use the same assets.
“This requires a schedule for how people take turns and use the resources. Within a conflict network like this, a certain minimum number of time slots is needed, which is equal to the chromatic number.”
Focus on the theory behind probability
In society, there is a great demand for mathematical models based on random and probability analyses. Not least in industries that specialize in risk forecasting, such as financial companies, energy companies and insurance companies.
But answering reality-related questions is not Annika Heckel’s focus. Her goal is to develop mathematical methods in probability theory and in the project also link the methods to physics and computer science.
“When you come across a proof that really gives some insight into `why' a theorem holds, it’s an incredibly satisfying feeling. This is irrespective of whether you make the discovery yourself or read someone else’s proof. It’s the most fun if you have spent a lot of time thinking about the question and the solution is short and simple, although of course it is not easy to come up with it.”
Anneli Björkman