Combinatorial designs and their generalizations

组合设计及其概括

• 批准号: RGPIN-2017-03891
• 负责人: Dukes, Peter
• 金额: $ 1.75万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=679590
• 关键词: 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个不同的点将包含在相同数量的区组中。在图分解中，成对之间的边或连接将被划分为给定小结构的副本。另一种可能的扩展包括使用边缘颜色来模拟两个或更多个同时发生的关系。举一个玩具例子，桥牌锦标赛可能要求每对玩家成为搭档一次，成为对手两次。*虽然有许多特殊的结构，但设计和图分解的一般存在性问题是非常困难的。本研究主要关注具有挑战性和最一般的情况，特别是在标准方法不适用的情况下。*最近一个著名的定理存在的设计带来了这个问题的前沿组合数学。即使这一理论对于非常大的设计来说是完整的，仍然有相当多的工作要做。特别是，为什么特定的设计不存在的原因导致了数学的其他领域，包括代数，分析和几何的奇妙联系。与应用数学和其他科学相比，这项研究确实离直接的工业应用还有一步之遥。然而，抵消这一点，它是足够普遍的，在各种各样的应用中具有最终用途。此外，基于信息的问题对设计、代码或阵列施加的附加结构通常在数学上是自然的。 这样，研究就受到其应用的密切指导。