Combinatorics, Probability and Algorithms

The interface of Combinatorics, Probability and its applications (in particular to algorithms) has been developing into an exciting area, with connections and applications, e.g. to Theoretical Computer Science, Statistical Physics and Operations Research. The project will focus on three themes in this area with interrelated objectives:

(i) Randomized Algorithms with a particular focus on randomized property testing:
Property testing aims to infer global structure from local random sampling algorithms. More precisely, given a combinatorial object, we aim to distinguish very quickly if it satisfies some property or if it is far away from satisfying this property. So the main goal is to design randomized algorithms which only consider a tiny part of the input, and then distinguish with high probability between the two above cases.

(ii) Random Discrete Structures:
The study of random graphs is motivated by understanding the typical behaviour of objects. This area has connections to statistical physics (in particular, the study of phase transitions, where small parameter changes give rise to major structural changes) and underpins the average case analysis of algorithms as well as the study of network processes, e.g. of epidemic nature. We will concentrate on the global structure of probability models defined by local constraints as well as on complex networks.

(iii) Randomized Constructions:
This theme is concerned with the use of randomized processes to build combinatorial objects with desired properties, with a focus on longstanding graph decomposition problems. (The main aim in such problems is to split a large object into suitable small pieces, which has applications, e.g. in statistical testing and information theory.)

The aim of the project is to make decisive progress on central questions within these three themes, whose solution relies on the interplay between Combinatorics and Probability. The three themes are connected by several common features. For example, a fundamental paradigm underlying many of the objectives is that of "local-global" structure: how do local patterns influence (typical) global structure? The investigation of this paradigm has been enormously fruitful in the field of Extremal Combinatorics over the last few decades. Within the project we will consider this from a probabilistic perspective. This is particularly relevant for computational problems where the graphs under consideration are large: in "traditional" graph theoretical problems the whole graph is exactly given, but for large networks this is often no longer the case. So we need to infer their global properties from local considerations.

Large graphs and networks underlie much of modern society and science. Correspondingly, in the past decade, the study of networks has increased dramatically and includes researchers from biology, computer science, economics, engineering, mathematics, physics, sociology, and statistics. Prominent examples of networks are the world wide web, social networks as well as biological networks such as the brain.

All these networks are huge and often constantly evolving. So it is not feasible to have a complete and exact understanding of their structure as well as of precise solutions to the corresponding optimization problems. Probabilistic approaches provide a way out of this dilemma: in particular, randomized property testing has the potential to quickly give an informed guess about the global structure of a network (see Theme RA). Conversely, the study of random graphs (see Theme RS) underpins the average case analysis of algorithms as well as the study of dynamic processes (e.g. epidemics or information distribution).

I believe that I have identified core problems associated with the mathematical foundations of such questions, which are (i) central to the area and (ii) whose solution will yield a body of coherent and broadly useful methods. So part of the long-term impact will be a significantly enhanced toolbox for the probabilistic analysis of large (random) graphs and networks.

Similarly, the project will also establish probabilistic tools for constructing combinatorial objects relevant to design theory (the Erdös conjecture on sparse designs), combinatorial number theory (k-term AP-free process) or extremal combinatorics (the Gyarfas-Lehel conjecture).

The solution of the proposed problems, which either have resisted attack for several decades (e.g. decomposition problems) or else are central in areas arisen much more recently (e.g. from randomized property testing) obviously also has a significant direct impact on the field.

As described in "Academic Beneficiaries", there is a wide range of research groups from several areas (both in the UK and overseas) who would benefit from the proposed research. So as described in "Pathways to Impact", I will be disseminating the results from the project as widely as possible and will organize corresponding activities. Moreover, I will provide the junior researchers on the project with suitable training and guidance. (I believe that I have an excellent track record in these respects.) Finally, I will make use of the opportunities provided by the fellowship to broaden my research by increasing the emphasis on probabilistic and algorithmic aspects. Altogether, this will contribute to the UK being at the forefront of developments in this rapidly developing and influential area.