A graph theoretical approach for combinatorial designs

组合学及相关领域中的许多基本问题可以表示为分解问题，其目的是将一个大的离散结构分解成合适的小结构。这类问题在许多领域都有广泛的应用，例如，在生物和化学实验的设计，在编码理论中构造纠错码，在量子信息理论中构造相互无偏的基。这一领域的典型问题也是在考虑日程安排问题时产生的，一个著名的娱乐例子是柯克曼的女学生问题，该问题可以追溯到1850年，要求在7个不同的日子将15名女学生分成3人一组，这样不会有两名女学生被分配到同一组超过一次。这个特殊的问题很容易解决，它的解是斯坦纳三元系的最简单的例子，或者更广泛地说，是组合设计。这种组合设计的更一般的构造通常基于几何和代数概念，例如射影平面和Hadamard矩阵。关于组合设计的现有结果的一个局限性通常是假设基础系统是完全的或高度对称的。然而，最近已经有了一些突破(例如，涉及概率技术)，它们提供了工具来处理到目前为止被认为遥不可及的问题。该项目将寻求非完整系统的组合设计(这些系统的潜在应用包括通信网络)。由于在这种非完全设置中存在非平凡设计的确定性问题在计算上是已知的，因此该项目的一个目标是确定寻找此类设计的自然充分条件。这些系统的对称结构的丧失使得基于代数和几何对象的构造的应用变得困难，但概率思想的使用提供了有希望的解决方案。例如，Steiner三系(如上例)可以看作是将一个完整的图分解成边不相交的三角形。该项目将产生强大的组合和概率技术，以在一大类图和超图中找到分解，这将应用于进一步的问题和领域，如将问题分解成大结构。

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.