Combinatorial designs and their generalizations

组合设计及其概括

• 批准号: RGPIN-2017-03891
• 负责人: Dukes, Peter
• 金额: $ 1.75万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=710597
• 关键词: Combinatorial; designs; their; generalizations

This research aims to improve our understanding of combinatorial designs and some of their generalizations. In the most basic case, a design on some ground set is a collection of subsets which covers any two distinct elements equally often. This is a familiar idea in many geometric models, since two different points uniquely determine a line. Designs underlie well-known puzzles, such as Sudoku and the “prisoner's hat problem”. More importantly, by their nature designs are useful in information theory (through their connection with error-correcting codes), computer science (software testing, network design) and statistics (experimental design). These applications have placed the focus on finite designs, and the beautiful geometries arising from finite fields (binary sequences, for instance) form a natural starting point. It is possible to extend the basic definition above in a number of ways. In a t-design, any t distinct points are to be contained in the same number of blocks. In a graph decomposition, the edges or connections between pairs are to be partitioned into copies of a given small structure. A further possible extension includes the use of edge colours to model two or more simultaneous relationships. As one toy example, a bridge tournament might require every pair of players to be partners exactly once and opponents exactly twice. Although there are many special constructions known, the general existence question for designs and graph decompositions is notoriously hard. This research is mainly concerned with the challenging and most general cases, and especially in situations where standard methods don't apply. A recent celebrated theorem on existence of designs has brought this topic to the forefront of combinatorial mathematics. Even as this theory is complete for extremely large designs, there is still considerable work to be done. In particular, the reasons why specific designs fail to exist leads to wonderful connections to other areas of mathematics, including algebra, analysis and geometry. In comparison with applied mathematics and other sciences, this research is admittedly a step removed from direct industrial applications. However, offsetting this, it is sufficiently general to have end-use in a wide variety of applications. Moreover, the additional structure that information-based problems impose on designs, codes, or arrays is quite often mathematically natural. In this way, the research is guided closely by its applications.

本研究旨在提高我们对组合设计及其推广的理解。在最基本的情况下，某个基本集合上的设计是包含任意两个不同元素的子集的集合。这是许多几何模型中熟悉的想法，因为两个不同的点唯一地确定一条线。设计是众所周知的谜题的基础，比如数独和“囚犯帽子问题”。更重要的是，从本质上讲，设计在信息论(通过它们与纠错码的联系)、计算机科学(软件测试、网络设计)和统计学(实验设计)中是有用的。这些应用程序将重点放在有限设计上，而有限域(例如，二进制序列)产生的美丽几何构成了一个自然的起点。 可以通过多种方式扩展上述基本定义。在t设计中，任何t个不同的点都要包含在相同数量的块中。在图分解中，对之间的边或连接将被分割成给定小结构的副本。另一种可能的扩展包括使用边缘颜色来模拟两个或多个同时的关系。举个例子，桥牌锦标赛可能会要求每一对选手只做一次搭档，做两次对手。 尽管有许多已知的特殊结构，但设计和图分解的一般存在问题是出了名的难。这项研究主要涉及具有挑战性和最普遍的情况，特别是在标准方法不适用的情况下。 最近一个著名的关于设计存在的定理把这个话题带到了组合数学的前沿。尽管这一理论对于超大型设计是完整的，但仍有相当多的工作要做。特别是，特定设计不存在的原因导致了与其他数学领域的奇妙联系，包括代数、分析和几何。 与应用数学和其他科学相比，这项研究无可否认地远离了直接的工业应用。然而，抵消这一点的是，它足够普遍，在各种应用中都有最终用途。此外，基于信息的问题强加给设计、代码或数组的附加结构在数学上通常是很自然的。通过这种方式，这项研究受到其应用的密切指导。