Designs, colourings and hypergraphs

设计、着色和超图

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

该提案中的研究属于离散数学领域，称为设计理论。 本质上，具有参数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]将实现期望的结果。