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.