Design Theory: Extremal and probabilistic perspectives
Final Report Abstract
The focus of this research project has been to explore various important themes in modern extremal and probabilistic combinatorics including the running time of graph bootstrap percolation processes, Ramsey properties of random structures and robustness of extremal thresholds. To give a flavour of the project’s findings, let us focus here on the case of graph bootstrap percolation, which is an example of so-called cellular automata and can be seen as a simple model for the spread of a virus through a population. In this model, one defines some network of people and a simple homogeneous rule for how the virus spreads. For example, one could imagine that every day each member of the population gets in several elevators and they get infected if everyone else in one of the elevators they travel in is already infected. To simplify further we impose constraints such as having just 3 people in each elevator and the collections of people who ride together in an elevator being the same day to day (which we define through a canonical hypergraph that is governed by copies of some fixed graph, in this case triangles). Despite this being a gross oversimplification of a realworld scenario, the mathematics that arises from such models is already a fascinating area and aspects of this model have been thoroughly studied from several perspectives. In particular, there has been a focus on whether the virus can eventually spread to the whole population when there is an initial infected set of people that is very small or when the initially infected set of people is some random selection. The latter has strong links with threshold phenomena in percolation processes, an area of probability theory for which Hugo Duminil-Copain was awarded one of the most recent Fields medals (the mathematical equivalent of a Nobel prize). Much less studied, although equally motivated by the human experience, is the question of how long the virus will spread for? In this vein, Bollobás recently raised the question of determining for a given model what the longest virus spreading time could be if you consider all possible choices of initially infected people. Before our work this had been studied on a few natural models generalising the “3 in an elevator” example above. During this project, with my coauthors David Fabian and Tibor Szabó, we initiated a systematic study of this question in graph bootstrap percolation models. Over the course of a series of papers we unearthed surprising relations between the rules for virus spread and the longest possible time that the virus will spread for, as well as raising many further questions. Interestingly, along the way we encountered and strengthened connections of this question with other areas of extremal combinatorics as well as algebra and number theory.
Publications
-
A canonical Ramsey theorem with list constraints in random graphs. Procedia Computer Science, 223, 13-19.
Alvarado, José D.; Kohayakawa, Yoshiharu; Morris, Patrick & Mota, Guilherme Oliveira
-
Slow graph bootstrap percolation I: Cycles, 2023.
D. Fabian, P. Morris & T. Szabó
-
Slow graph bootstrap percolation II: Accelerating properties, 2023.
D. Fabian, P. Morris & T. Szabó
-
Two-round Ramsey games on random graphs, 2023.
Y. Alon, P. Morris & W. Samotij
-
Universality for transversal Hamilton cycles, 2023.
C. Bowtell, P. Morris, Y. Pehova & K. Staden.
-
A robust Corrádi–Hajnal theorem. Random Structures & Algorithms, 65(1), 61-130.
Allen, Peter; Böttcher, Julia; Corsten, Jan; Davies, Ewan; Jenssen, Matthew; Morris, Patrick; Roberts, Barnaby & Skokan, Jozef
-
Schur properties of randomly perturbed sets. European Journal of Combinatorics, 121, 103843.
Das, Shagnik; Knierim, Charlotte & Morris, Patrick
-
Speeding up random walk mixing by starting from a uniform vertex. Electronic Journal of Probability, 29(none).
Díaz, Alberto Espuny; Morris, Patrick; Perarnau, Guillem & Serra, Oriol
