Homework 2 att lämnas in fre 18/5

Again, the following exercises are of varying degrees of difficulty. Some, like nos. 10 and 11, are also quite long, but should be good practice. Partial solutions to the longer exercises will be accepted. Unless otherwise stated, all graphs G are simple and undirected. Q.1 Find the edge-chromatic number of the underlying graph of Fig. 12.2. Q.2 Draw an explicit 4-edge-coloring of the graph K_{4,4}. Q.3 Describe an explicit k-edge-coloring of the graph Q_{k} of exercise 8.8.5 (see exercise 10.2.6). Q.4 Use the augmenting path algorithm to construct a maximum matching of the underlying graph of Fig. 12.2. Q.5 Use Hall’s theorem to prove König’s theorem (see exercises 10.7.19 and 11.6.15). Q.6 Exercise 10.7.13. Q.7 Exercise 10.7.17. Q.8 Exercise 11.5.2 - also find a minimal cut. Q.9 Let D = (X, B) be a t − (ν, k, λ) design. Show that the following hold

(i) each element of X is in the same number r of blocks, where

r = λ\begin{matrix}( & \begin{matrix}ν − 1 \\ t − 1 \end{matrix} & ) \\ ( & \begin{matrix}k − 1 \\ t − 1 \end{matrix} & ) \end{matrix}.

(ii) the number b of blocks is given by

b = λ\begin{matrix}( & \begin{matrix}ν \\ t \end{matrix} & ) \\ ( & \begin{matrix}k \\ t \end{matrix} & ) \end{matrix}.

(iii) bk = νr.

Q.10 (i) Prove the following theorem, which you have probably seen in your linear algebra course :

Theorem : Let V, W be finite dimensional vector spaces over a field F and ϕ : V → W a linear mapping. Let

ker ϕ = {v ∈ V : ϕ(v) = 0},
im ϕ = {w ∈ W : w = ϕ(v) for some v ∈ V }.

Then (a) ker(ϕ) is a subspace of V, (b) im(ϕ) is a subspace of W, (c)

dim ( ker(ϕ) ) + dim ( im(ϕ) ) = dim V.

(ii) Let V = F^{n} the vector space of n-dimensional vectors with components in F, in which addition and scalar multiplication are componentwise. Let V be endowed with the usual scalar product (as described in class) and let v ∈ V. With the same notation as used in class, prove that

dim v^{⊥} = dim V − 1.

(iii) More generally, if W is a subspace of V, prove that

dim W + dim W^{⊥} = dim V.

(Hint : Together with part (i), use Gram-Schmidt orthogonalisation and/or the fact that every symmetric square matrix is diagonalisable).

Q.11 Construct an explicit 2 − (21, 5, 1) design. Note that you’ll need to choose a convenient representation of the elements of the field F_{4}, and know the addition and multiplication tables. You may ask me for a hint on this if you wish.