A major initiative is under way in Swedish mathematics research. Funding by the Knut and Alice Wallenberg Foundation is helping to build an enhanced and more international mathematics research environment at Uppsala University. This is being done to meet the challenges posed by rapid technological developments, involving ever more advanced mathematical problems in applications such as internet modeling and better designed search algorithms.
Project Grant 2017
Random structures and algorithms
Principal investigator:
Svante Janson, Professor of Mathematics
Co-investigators:
Erik Ekström
Cecilia Holmgren
Institution:
Uppsala University
Grant in SEK:
SEK 27.5 million over five years
Uppsala is already recognized as a center of excellence in mathematical research. Professor Svante Janson explains that the new grant will further boost its position:
“We want to remain at the international forefront. Now we can build on the research we have been doing over the past few years, and develop new methods and techniques in the field.”
The funding enables Janson to recruit young researchers from across the world, and to invite visiting professors to join the team. Six postdocs and four PhD students have already been hired. In spring 2019 two visiting professors will be arriving in Uppsala – one from North America, and one from South Africa. Associate Professor Cecilia Holmgren elaborates:
“As the team grows, it becomes increasingly attractive to join us as a guest researcher, and when our guests return to their home countries, more is written about our research.”
Theoretical research with multiple applications
The research is theoretical, and the problems that Janson and his colleagues are studying are interesting from a mathematical viewpoint. But this does not mean the results will not have any practical applications. They may be of use to other researchers in a number of fields, particularly in computer science.
One example is that of “random trees”, which can be used to describe data algorithms. For many years now, Holmgren has explored various random trees, including binary search trees, which come from an algorithm called Quicksort, and are used to sort data. Initially, data algorithms of this kind could only be studied one at a time, but the Canadian scientist Luc Devroye introduced a common class uniting different search trees, naming it “split trees”. Subsequently, in her doctoral thesis, Cecilia was the first to prove theorems describing the general characteristics of split trees.
“It is important to be able to study large classes of random trees simultaneously. Our team and others have already successfully pursued this line of research, and now we want to go on to reach new heights,” Janson enthuses.
Biotech applications for random trees
Another type of random tree is the “Galton-Watson tree”, whose original application was in biology. In the 1870s two British researchers wrote a paper about aristocratic family names dying out, and developed a model to capture the phenomenon.
“This gave birth to branching process theory, which from the outset was a highly practical application, and which has had a huge impact in various fields,” Janson explains.
Nowadays random trees of this kind are found in fields such as modern biotechnology and genetics, in which enormous quantities of uncertain data are generated, and there is a need to use statistical models to draw conclusions about real-life situations.
“This is an example showing the potential our mathematics offers in many contexts. But we are good at performing theoretical studies and then leaving it to various experts to do what they are good at in their field,” Janson points out.
Sorting values under random uncertainty
Another sub-topic concerns sorting algorithms affected by uncertainty – what scientists call “noise”. Professor Erik Ekström’s field of research is financial mathematics, and the methods he is studying are of interest in the financial sector, including the stock market, for example.
“Normally, when one thinks of a computer crunching numbers, it is easy to compare the largest with the smallest. But in my field, those numbers represent the expectations of a stock, for example. Suddenly it’s not so easy to compare to see which number is the greatest – they are subject to randomness.”
Anyone wishing to sort stocks according to anticipated return must make repeated comparisons to get a result. But it is still hard to know when the list has been fully sorted. This means that the complexity of the sorting algorithms increases, because it must also be decided when the sorting should be considered complete.
“And here lies a central dilemma. The risk of a small degree of error must be weighed up against the increased expense of continuing sorting in order to attain higher statistical precision,” Janson adds.
For his part, Janson continues to concentrate his research on random graphs – graphs generated by random processes that describe how vertices are connected to each other. One use of random graphs is to describe networks in various applications. One example is the internet, either as a physical network of computers or as a logical network of websites and links. But they may also be used to describe social networks or routes for the spread of infectious diseases – of great interest to epidemiologists.
“We are grateful for this opportunity to work on a larger scale, supported by a growing research team. We are also convinced that we will solve some of the problems we identified in our funding application. But we don’t know in advance what the results will be – after all, if we did, it wouldn’t be research,” Janson says.
Text Nils Johan Tjärnlund
Translation Maxwell Arding
Photo Magnus Bergström
