EPSRC logo

Details of Grant 

EPSRC Reference: EP/N019504/1
Title: Combinatorics, Probability and Algorithms
Principal Investigator: Kuehn, Professor D
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: School of Mathematics
Organisation: University of Birmingham
Scheme: EPSRC Fellowship
Starts: 01 September 2016 Ends: 31 August 2021 Value (£): 822,432
EPSRC Research Topic Classifications:
Logic & Combinatorics Statistics & Appl. Probability
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
20 Jan 2016 EPSRC Mathematical Sciences Fellowship Interviews January 2016 Announced
23 Nov 2015 EPSRC Mathematics Prioritisation Panel Meeting November 2015 Announced
Summary on Grant Application Form
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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.bham.ac.uk