Answer FIVE questions-but not more than three from any section
1. (a) Let G be a finite group of permutations acting on a finite set D.
For each g Î G, let F(g) be the set
{x Î D: g(x) = x}. Prove that the number of orbits under the action
of G is given by
|
(b)
Identity cards are to be manufactured from plastic squares marked with
an n×n grid
on both sides and with two holes punched into them
(one hole through each of two cells of the grid). Find the number of
distinguishable identity cards that can be manufactured in this way.
[Treat separately the cases n odd and n even.]
2. (a) Let p,q be positive integers and let r(p,q) be
the least value of n such that any 2-colouring of the edges of
the complete graph Kn
contains a monochromatic Kp or Kq as a subgraph. Show that
|
|
(b) In the rest of the question you may assume that in any 2-colouring of the edges of K6 there are at least two monochromatic triangles.
Consider a 2-colouring of the edges of K7, containing t monochromatic triangles. Call a pair (H,T) a good pair if H is a complete subgraph of K7 on six vertices, T is a monochromatic triangle of K7, and T is contained in H. By counting the number of good pairs in two ways, show that t ³ 4.
3. (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 PG(r,r,...,r), where PG(x1,x2,...,x|D|) is the cycle
index of G acting on D.
[The result in Question 1(a) may be used without proof.]
(b) Two diagonals are drawn on one side of a square cardboard sheet. Each of the four triangles so obtained is to be coloured with one of the colours c1,c2,...,cr.
(c) Now suppose instead that the four triangles in part (b) are to be coloured using any of the integers 0,1,2,3,... as colours. In how many ways can this be done if the total sum of the four colours used is to be equal to 4t?
[Pólya's Theorem may be used without proof.]
4. (a) Suppose that C is a q-ary code of length n, and suppose
that d is the minimum (Hamming) distance in C. Show that if
d ³ 2e+1, then C is an e-error-correcting code.
Now suppose that C is a linear code over a field F of order q, and let w be the minimum weight of the non-zero vectors in C. Prove that w = d.
(b) Let H be a check-matrix for C. Prove that any d-1 columns of H are linearly independent.
How many non-zero vectors are there in Fr? If v is such a vector,
how many non-zero scalar multiples av are there in Fr? Deduce
that the maximum number of vectors in Fr such that no two are linearly
independent is equal to
|
Part (c) continued next page
(c) Suppose F is the field \Bbb Z3 and the following is a generator
matrix for C:
| |||||||||||||||||||||||||||||||||||||