As its title suggests, this project focused on resolving problems at the interface between the theory of extremal combinatorics and random graph theory. Roughly speaking, the problems we tackled can be grouped into one of the following categories.
In classical extremal graph theory, we study simple sufficient conditions for a graph to satisfy a given property (for example, a sufficient minimum-degree condition). In random graph theory, we instead study the average-case behaviour, looking for conditions under which an average graph will satisfy the property. With the theory of randomly perturbed graphs, these two directions merge: we are interested in understanding the average-case behaviour of supergraphs of graphs which satisfy some density condition. Most often, we consider graphs with some minimum-degree condition which is not sufficient to guarantee some property, and study how many random edges must be added to this graph so that it will satisfy the desired property.
Given a graph which satisfies a desired property (like being connected), we could be interested in understanding how robustly they satisfy it. This can be interpreted and studied from many different directions. One of the most frequent directions (generally dubbed robustness) considers some probability distribution on the subgraphs of the given graph, and studies under which distributions the common random subgraphs still satisfy the desired property. In particular, there has been a lot of interest on the robustness of graphs with respect to a property which is guaranteed by them satisfying a sufficient density or minimum-degree condition for it.
Assume that there is a large network that satisfies some important property (say, it is connected). Since this property is relevant for us, we want to study how resilient this property of our network is in case of an adversarial attack. This can be studied from different perspectives; in the case of local resilience, we assume that an adversary can delete as many edges as they want, with the restriction that they cannot delete more than a certain proportion of the edges incident to each vertex. When studying local resilience, the goal is to understand, for each graph and each desired property, what is the maximum proportion of edges that the adversay can be allowed to delete while still guaranteeing that they will not be able to destroy the property.
The random graph process is a model for the study of the evolution of random graphs as they become denser. Essentially, we begin with an empty graph and add edges to it one by one, each of them chosen randomly, until we reach a very dense graph, and we are interested in studying the (likely) properties of the graph at any given point in the process. This is one of the most studied objects in random graph theory.
If we are interested in constructing a graph which satisfies a certain property (say, that it contains some given substructure), we can construct it by letting the random process run until the property is satisfied, and our knowledge of the random graph process allows us to estimate the number of steps that this will take (that is, the number of edges that the final graph will have). However, what would happen if we had to pay a price for each edge that we add to the graph? Is there some way to reduce the costs, while still working with the same framework of the random graph process?
A few years ago, Frieze, Krivelevich and Michaeli proposed a modification of this model where, each time a random edge is "offered" for the random graph, we may in fact choose to not add it to the graph. The idea then is to study the interplay between the budget that we have available for constructing a graph with a given property and the time that it will take to achieve this within the budget (if that is even possible). In particular, this requires designing good strategies for constructing graphs with the desired property.