Designs, colourings and hypergraphs

设计、着色和超图

• 批准号: 217627-2010
• 负责人: Pike, David
• 金额: $ 1.46万
• 依托单位: Memorial University of Newfoundland
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570192
• 关键词: Designs; colourings; hypergraphs

The research in this proposal is in the field of discrete mathematics known as design theory. In essence, a design having parameters N, K and L is a mathematical model in which each of N items is a member of several groups where (1) each group contains exactly K items, and (2) each pair of items are found together in exactly L of the groups. For example, if N=7, K=3 and L=1, and if the seven items of the design are represented by the letters A to G then the following seven groups produce a valid design: ABD, BCE, CDF, DEG, AEF, BFG, ACG. Designs can be used to schedule or coordinate situations in which groups with this type of structure are needed. For instance, if a farmer with seven crop varieties to plant wants to sow a mixture of three varieties in each field such that no pair of varieties is grown together in more than one field, then the example design just presented would provide a solution in which varieties A,B,D are planted in one field, B,C,E in the next field, and so forth. Sometimes the items of a design also need to be divided into collections so that no group has all K of its items coming from just one of the collections of items. For example, suppose a farmer can have one of X available treatments for disease control applied to each seed variety; varieties with a common treatment then form one collection. To reduce the risk of crop failure in each field, sowing any field with K varieties that have all had the same seed treatment is to be avoided. The design above cannot be split up into X=2 collections in this manner, but if X=3 then the three collections [A,C,E], [B,D] and [F,G] would achieve the desired result. The research in this proposal will study designs as abstract mathematical objects, and will consider several unsolved problems. One such problem is to prove for each choice of K and X that there exists a design with L=1 and with some number N of items that can be partitioned into X collections, but not into X-1 collections. Several students and post-doctoral fellows will receive advanced mathematical training in conjunction with this research. In addition to helping to advance science, they will be prepared for careers in academia or other settings in which complex analytical skills are required.

本提案的研究是在离散数学领域被称为设计理论。本质上，具有参数N， K和L的设计是一个数学模型，其中N个项目中的每一个都是几个组的成员，其中(1)每个组恰好包含K个项目，(2)每对项目恰好在L个组中同时出现。例如，如果N=7， K=3， L=1，并且如果设计的七个项目由字母A到G表示，则以下七个组产生有效设计：ABD， BCE， CDF， DEG， AEF， BFG， ACG。设计可以用于安排或协调需要这种类型结构的组的情况。例如，如果一个农民有七种作物品种要种植，他想在每一块地里播种三种混合品种，这样就不会有两种品种同时种植在一块地里，那么刚才展示的示例设计将提供一种解决方案，即品种a、B、D种植在一块地里，B、C、E种植在另一块地里，以此类推。有时候，设计中的道具也需要被划分成集合，这样就不会有一个组的所有K个道具都来自于其中的一个集合。例如，假设农民可以对每种种子品种采用X种可用的疾病控制方法中的一种；具有共同处理的品种然后形成一个集合。为了减少每一块地作物歉收的风险，应避免在任何一块地播种经过相同种子处理的K品种。上述设计不能以这种方式分成X=2个集合，但如果X=3，则三个集合[A，C,E], [B，D]和[F，G]将达到预期的结果。