EPSRC Reference: 
EP/P002420/1 
Title: 
A graph theoretical approach for combinatorial designs 
Principal Investigator: 
Lo, Dr SA 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
School of Mathematics 
Organisation: 
University of Birmingham 
Scheme: 
First Grant  Revised 2009 
Starts: 
01 November 2016 
Ends: 
31 October 2018 
Value (£): 
101,126

EPSRC Research Topic Classifications: 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
Many fundamental problems in combinatorics and related areas can be formulated as decomposition problems  where the aim is to decompose a large discrete structure into suitable smaller ones. Such problems have numerous applications to a wide range of areas, for example, to the design of experiments in biology and chemistry, to constructing errorcorrecting codes in coding theory and to constructing mutually unbiased bases in quantum information theory. Typical questions in this field also arise from considering scheduling problems, a famous recreational example being Kirkman's schoolgirl problem which dates back to 1850 and asks for an assignment of 15 schoolgirls into groups of 3 on 7 different days such that no two schoolgirls are allocated to the same group more than once. This particular problem is easy to solve and its solution is the simplest example of a Steiner triple system or, more generally, a combinatorial design. More general constructions of such combinatorial designs are often based on geometric and algebraic concepts such as projective planes and Hadamard matrices.
One limitation of existing results on combinatorial designs has often been the assumption that the underlying system is complete or highly symmetric. However, there have been recent breakthroughs (involving, for example, probabilistic techniques) which provide tools to approach problems that have been deemed out of reach until now. This project will seek combinatorial designs in noncomplete systems (potential applications of these include communication networks). Since the deterministic problem of the existence of nontrivial designs in this noncomplete setting is known to be computationally intractable, one goal of the project is to identify natural sufficient conditions for finding such designs. The loss of the symmetrical structure of these systems makes it difficult to apply constructions based on algebraic and geometric objects but the use of probabilistic ideas offers promising solutions.
The proposed research will approach these problems from a graph theoretical perspective. For instance, a Steiner triple system (such as the above example) can be viewed as a decomposition of a complete graph into edgedisjoint triangles. The project will yield powerful combinatorial and probabilistic techniques to find decompositions in a large class of graphs and hypergraphs which will have applications to further problems and areas such as decomposition problems into large structures.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

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 