Image: Victor Falgas Ravry
Image: Victor Falgas Ravry
Research project financed by the Swedish Research Council.
This project is about extremal and probabilistic combinatorics, a vibrant area of contemporary research in discrete mathematics.The focus is on extremal problems for multicoloured graphs and locally dependent percolation. The grand aims of the project are to obtain multicolour generalisations of the Alekseev—Bollobás—Thomason theorem, and locally dependent analogues of the celebrated Harris—Kesten theorem.
Much of this project is concerned with graphs, which are the mathematical objects used to model networks. Formally, a graph consists of a set of vertices (or nodes) and a set of edges (or links) joining pairs of vertices.
Graphs are of fundamental importance due to their ubiquitous applications both within mathematics (they crop up in number theory, group theory and probability theory, for example) and outside it (modelling social networks, transport and telecommunications, or just navigating the internet). As such, they have been the subject of intense study by mathematicians over the past seventy years.
One central question in graph theory is determining how many edges a graph can have if it does not contain some specified configuration as a subgraph. For instance Mantel's theorem from 1907 give the maximum number of edges a graph on n vertices can have if it does not contain a triangle. Extremal problems of this kind are known as Turán-type problems, honouring Pál Turán's pioneering contribution to the field.
Another important question has been estimating the number of graphs with a given property, and characterizing their typical structure. For hereditary properties of graphs, theorems of Alekseev and Bollobás—Thomason in the 1990s asymptotically answered the counting question, while typical structure characterizations were obtained in the early 2010s by Alon, Balogh, Bollobás and Morris. More recently, the development of power theories of hypergraph containers by Balogh, Morris and Samotij and Saxton in Thomason, has enabled us to give new proofs of these results by reducing them to Turán-type extremal problems for graphs.
However, in many of the networks arising in applications, edges may come in different weights, intensities or types. To model such networks, one should consider multicoloured graphs instead, for which we do not have an satisfactory extremal theory at present. The first of the main goals of this project is to address this gap in our knowledge by building a general theory of Turán-type problems for multicoloured graphs, and applying the theory of hypergraph containers to derive multicolour analogues of the counting and typical structure theorems of Alekseev, Bollobás--Thomason and Alon—Balogh—Bollobás—Morris.
Mathematical percolation lies at the interface of graph theory, combinatorics, probability theory and statistical physics. It is concerned primarily with the study of random subgraphs of infinite graphs, and in particular with critical phenomena such as the emergence of an infinite component.
Motivation for this area research arises from the study of liquids percolating through porous media —indeed, many of us experience percolation on a daily basis when we make filter coffee. We set the coffeemaker in motion, and hear first the hiss of the steam rising up and cooling down again, depositing droplets of hot water on the ground coffee powder. At first nothing happens: the water is absorbed by the coffee, but there is not enough of it to saturate the powder and penetrate to the bottom of the filter to drip down into the pot. And then suddenly it comes in rush: not one or two droplets but steady rivulet of coffee that quickly fills the clear-glass pot with black liquid. Percolation has occurred.
This familiar phenomenon is fascinating to analyse. Physically, what happens at the rapid phase transition in percolation — the moment when, suddenly, the coffee begins to percolate — and how can you predict when it will take place? These questions have led statistical physicists and mathematician to study theoretical models for percolation, in the hope of better understanding it in the real world.
One of the cornerstones of percolation theory is the celebrated Harris—Kesten theorem, which is concerned with bond percolation in the square lattice. Think of an infinite square grid in the plane, and for each edge in this grid keep it with probability p and delete it otherwise, independently at random. The result is a random graph, which is a subgraph of the square lattice. The remarkable Harris—Kesten theorem states that if p is at most 1/2, then the components (connected pieces) of this random graph are all finite, while if p>1/2 then the random graph contains a unique infinite component. Thus 1/2 is a critical probability for this random graph model, i.e. a point at which the model’s behaviour undergoes a radical transition — a mathematical analogue of the precise instant when a steady trickle of coffee begins to drip into the pot.
In this project, we consider a related problem, for which much less is known about the location of the critical probability. Namely, suppose we had a random graph model on the square lattice again, in which each edge is individually included with probability p, but where this time the state of an edge (whether it is included in the random graph or not) is allowed to depend on that of neighbouring edges. How large does p now need to be to ensure the existence of an infinite component? In other words, to what extent can we use local dependencies to delay the onset of the percolation? Determining the associated critical probability — and thus establishing a locally dependent analogue of the Harris—Kesten theorem — has been an open problem for at least 15 years, and is the second grand objectives of this project.
