Designs, colourings and 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.