A graph theoretical approach for combinatorial designs

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 error-correcting 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 non-complete systems (potential applications of these include communication networks). Since the deterministic problem of the existence of non-trivial designs in this non-complete 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 edge-disjoint 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.

The proposed project studies combinatorial designs, which can be viewed as decompositions of large objects into small ones. Designs are used for example in error-correcting codes, and thus are important in the context of establishing reliable and secure communication networks. Combinatorial designs also have wider applications, for example, they can be used to improve the reliability and the efficiency of group testing algorithms implemented in disease-screening of blood samples.

Direct impact will be achieved through proving longstanding and central open problems. (I have an excellent record of success in related areas, for example, with the proof of the 1-factorisation conjecture which dates back to the 1950s.) Publications in leading journals and speaking at high-profile international conferences will aid the dissemination of the results from the project. The findings of the project will also be available from arXiv.org and my personal homepage.

More generally, the project will also involve the development of novel combinatorial methods, which will have potential applications in solving further open problems. For example, I believe the 'iterative absorption' technique to be further developed in this proposal can be used to approach open problems on Hamilton cycles and perfect matchings in hypergraphs, where the existing methods fail. Some of these problems are motivated by applications such as image processing. The project will also provide a more systematic approach to decomposition problems arising in the probabilistic setting. There are several strong groups internationally working on such topics.

The project will enhance the UK's position at the frontier of combinatorics research. The project will include organising and hosting a two-day workshop which will highlight the UK's contribution toward the exciting developments in this area. The workshop will also facilitate discussions and collaborations between the UK and international researchers attending.

The project also aims to increase public awareness of the research. To publicise the general theme of the project and its outcomes, I will run a University of Birmingham popular mathematics lecture. Furthermore, I aim to inspire and nurture the future generation of young mathematicians through running University of Birmingham masterclasses for secondary school pupils.