Answer FIVE questions, with at least two questions from each section

1. (a) Let p be a positive integer and let r(p) be the least value of n such that any colouring of the edges of the complete graph K_n with colours red and blue contains either a red or a blue K_p. Show that

(b) Show that every graph on \binomk+lk vertices contains either a complete graph on k+1 vertices or a set of l+1 mutually non-adjacent vertices.
[Hint. Let d(v) be the degree of v and let d¢(v) be the number of vertices not adjacent to v. Use induction on k+l. Consider d(v)+d¢(v), and use \binomnr = \binomn-1r-1+\binomn-1r and the pigeon-hole principle.]

2. (a) Let s = (1 2 3 ¼ n) be the cyclic permutation of the set D = {1,2,¼,n}. Show that the cycles of sⁱ are all of the same length. Hence obtain, in terms of Euler's f-function, the cycle index of the cyclic group of permutations of D generated by s.

(b) Let p be a prime number and let r and t be positive integers. Prove that p^t divides

Turn over

3. (a) Suppose C is an e-error-correcting q-ary code of length n. Let d be the minimum distance between elements of C. State a lower bound for d in terms of e.

Prove the Hamming bound

Suppose that the Hamming bound gives an upper bound of 5 for a 3-error-correcting binary code of length 10. Show that such a code cannot have more than two codewords.

(b) Show that if a perfect 2-error-correcting ternary code of length n exists, then 2n²+1 is a power of 3.

(c) Let C be a linear, perfect e-error-correcting binary code of length n. Let B be the collection of all codewords of weight 2e+1. Let each codeword c in B correspond to the subset A of {1,2,¼,n} defined by i Î A if and only if c_i = 1.

Show that this family of subsets gives an (e+1)-design with l_e+1 = 1.
[Hint. The balls {B_e(c): c Î C} partition \mathbbZ₂ⁿ since C is perfect.]

4. Let (X,B) be a 2-design with |X| = v, and b blocks of size k each. Let r be the number of blocks containing any single element and let l be the number of blocks containing any given pair of elements. Prove that:

• bk = vr;
• r(k-1) = l(v-1);
• k £ v, and therefore r ³ l;
• b = v if and only if k = r.

Obtain also Fisher's inequality v £ b, assuming that the design is non-trivial, that is, r > l.