Show how to think of Fisher’s 2-designs as a k-uniform, r-regular hypergraphs of
ID: 3293646 • Letter: S
Question
Show how to think of Fisher’s 2-designs as a k-uniform, r-regular hypergraphs of order m and size n in which the number of edges containing each pair of distinct vertices is exactly . For the rest of the parts, suppose the hypergraph H = (V, E) is a 2-design.
This homework is about a highly constrained hypergraph, called a 2-design. Ronald Fisher, a population geneticist, was interested in studying n varieties of plants under m different growing conditions, each of which he called a block. He wanted · each block to grow k n different varieties of plants (and no duplicates). ·any single variety to grow in exactly r blocks, . and any pair of distinct varieties to grow together in exactly blocks. Ronald Fisher wanted to find out how few1 blocks he could use create a 2-design for n varieties of plants. The challenge problem shows m 2 n, that is, he always needs more blocks than varieties of plants. It is not even known for which n we can achieve2 with m n and -1.Explanation / Answer
By averaging there exists a vertex x V (H) contained in at least ¡n1 t ¢ (t+1)k edges of H.
Thus apart from at most (t+1)k exceptional sets all subsets 7 of size t on the remaining n 1 vertices form an edge of H together with x.
Let us denote the union of the vertices in the exceptional subsets by U.
Thus |U| (t + 1)kt.
Take a cyclic permutation on the remaining vertices where two vertices from U are never neighbors. Since n > 2(t + 1)tk, this is possible.
But then this cyclic permutation is actually a t-tight Berge-cycle, i.e. C (t+1,t) n1 .
Indeed, any set of t consecutive vertices on the cycle contains a non-exceptional vertex and thus it forms an edge with x.
Furthermore, since n > 2(t+1)tk, there must be two non-exceptional vertices, denoted by x1 and y1, that are neighbors on the cycle.
Consider the 2t consecutive vertices along the cycle that include x1 and y1 in the middle, and denote these vertices by xt, . . . , x1, y1, . . . , yt.
Consider also a vertex z along the cycle that is not among these 2t vertices. We claim that x can be inserted between x1 and y1 on the cycle and thus giving a Hamiltonian t-tight Berge-cycle in H.
Indeed, for those sets of t consecutive vertices which do not include x, we can add x to get the required edge Ei .
If a set of t consecutive vertices includes x, then it also must include either x1 or y1 (or maybe both), i.e. a non-exceptional vertex.
But then we can add z to get the required edge. It is easy to check that all the used edges are distinct.
For S V (K (g) n ), |S| < g, let ES = {e|e E(K (g) n ) with S e}, the set of edges containing S.
Thus |ES| = ¡n|S| g|S| ¢ .