Answer FIVE questions, not more than one from each section

1. (a) Let p,q be positive integers and let r(p,q) 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 K_p or a blue K_q. Show that

(b) Let P₃ be the path on three edges and C₄ the cycle on four edges, and let r(P₃,C₄) denote 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 P₃ or a blue C₄. Show that

2 Let S₅ be the symmetric group consisting of all permutations of V = {1,2,3,4,5} and let S₅⁽²⁾ be the corresponding group of permutations induced by the action of S₅ on the set of unordered pairs of distinct elements of V.

If the cycle index of S₅ is

(``Burnside's'' counting lemma may be assumed.)

Answer FIVE questions, not more than one from each section

1. (a) Let G be a finite group of permutations acting on a finite set D. Suppose that the elements of D are to be coloured, and let r be the number of colours available. Show that the number of colourings of D which are non-equivalent under the action of G is P_G(r,r,...,r), where P_G(x₁,x₂,...,x_|D|) is the cycle index of G acting on D.

[``Burnside's'' counting lemma may be assumed.]

(b) A cardboard sheet is in the form of a regular pentagon. On one side of the pentagon straight lines are drawn from the centre of the pentagon to each of the pentagon's vertices. Each of the resulting five triangles is to be coloured with one of the colours c₁,c₂,...,c_r.

• In how many ways can this be done?
• In how many ways can this be done if the colour c₁ is used at least once? (Simplify your answer.)

(c) Now suppose instead that the five triangles in part (b) are to be coloured using any of the integers 1,2,3,... as colours. In how many ways can this be done if the total sum of the five colours used is to be equal to 5t, t ³ 1?

[Pólya's Theorem may be used without proof.]

2. (a) Suppose C is a q-ary code of length n, and suppose C is e-error-correcting. Let d be the minimum distance between elments of C. Give a lower bound for d in terms of e.

Prove that

Now let C be a linear code. What is the minimum non-zero weight in C?

Let H be a check matrix for C. Prove that any d- 1 columns of H are linearly independent.

Now let C be the binary Hamming code H(r,2) which is the code with check matrix H whose columns are all the distinct non-zero vectors in {0,1}^r. What is the length and the dimension of C?

Show that C is a perfect 1-error-correcting code.

(b) Suppose F is the field Z₅ and the following is a generator matrix for C: