权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

A graph theoretical approach for combinatorial designs

组合设计的图论方法

基本信息

批准号：
EP/P002420/1
负责人：
Siu Lun Lo
金额：
$ 12.89万
依托单位：
University of Birmingham
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2016
资助国家：
英国
起止时间：
2016 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FP002420%2F1
关键词：
graph theoretical approach 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.

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