Designs, colourings and hypergraphs

设计、着色和超图

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