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]将达到预期的结果。 这项提案中的研究将把设计作为抽象的数学对象来研究，并将考虑几个未解决的问题。一个这样的问题是证明对于K和X的每一个选择，存在一个设计，其中L=1，并且具有一定数量的N个项，它可以被分成X个集合，但不能被分成X-1个集合。 几名学生和博士后研究员将与这项研究一起接受高级数学培训。除了帮助推进科学，他们还将为在学术界或其他需要复杂分析技能的环境中的职业生涯做好准备。

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.