Designs, colourings and hypergraphs

本提案的研究是在离散数学领域被称为设计理论。本质上，具有参数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]将达到预期的结果。

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.