EXERCÍCIOS DE MATEMÁTICA DISCRETA 2O. SEMESTRE DE 2003

[Os exercícios desta lista são reciclados de edições anteriores desta e disciplinas semelhantes. Alguns exercícios estão em sua versão original, em inglês. (Melhor assim do que demorar mais ainda para eu disponibilizá-los).]

1. Let A = {A_{λ}: λ ∈ Λ} be a family of subsets of a finite set W. Consider the subsets Λ′ ⊂ Λ such that the family of sets A_{λ} (λ ∈ Λ′) admits a system of distinct representatives. Show that any two such maximal sets (under inclusion) have the same cardinality.

2. Let M_{i} = M_{i}(S_{i}) (1 ≤ i ≤ k) be matroids on pairwise disjoint sets S_{i}.

Let

I = { ⋃_{1≤i≤k} I_{i}: I_{i} ∈ I(M_{i})}  (1)

be the family of unions of independent sets in the matroids M_{i} (one independent set I_{i} for each i). Clearly, I ⊂ 2^{S}, where S = ⋃_{1≤i≤k} S_{i}.

(i) Show that I is the set of independent sets of a matroid on S. This matroid is called the direct sum of the matroids M_{i} (1 ≤ i ≤ k), and is usually denoted ⨁_{1≤i≤k} M_{i}.

(ii) Determine the rank function of ⨁_{1≤i≤k} M_{i}.

3. Let f: S → T be a surjection, where S is a finite set. Suppose M = M(S) is a matroid on S. Let

I = {f(I): I ∈ I(M)}  (2)

be the family of images of independent sets in M under f. Clearly, I ⊂ 2^{T}.

(i) Show that I is the set of independent sets of a matroid on T. This matroid is sometimed called the homomorphic image of M under f.

(ii) Let N = N_{f} be the homomorphic image of M under f. Show that the rank function r_{N} of N is given by

r_{N}(A) = min{r_{M}(f^{−1}(B)) + |A \ B|: B ⊂ A}  (3)

for all A ⊂ T, where r_{M} is the rank function of M.

4. [Horn] Let k be a positive integer. Suppose x_{1}, …, x_{n} are vectors in some vector space such that, for any J ⊂ [n], there is J′ ⊂ J such that |J′| ≥ |J|/k and the vectors x_{j} (j ∈ J′) are linearly independent. Prove that x_{1}, …, x_{n} may be partitioned into at most k families of linearly independent vectors.

Date: Versão de 27 de novembro de 2003.

5. [Nash-Williams] Let G be a multigraph with no loops and at least one edge. Prove that the edge set of G may be written as a union of k forests if and only if

k ≥ \frac{|E(H)|}{|V (H)| − c(H)}  (4)

for all subgraphs H ⊂ G of G with |V (H)| − c(H) > 0, where c(H) denotes the number of components in the graph H.

6. [Tutte] Let G be a connected graph. Prove that G contains k edgedisjoint spanning trees if and only if for any partition π of the vertex set of G, the number of edges joining vertices in distinct blocks of π is at least k(|π| − 1), where |π| denotes the number of blocks in π.

7. [Edmonds] Let M = M(S) and N = N(S) be two matroids on S. Prove that

max{|I|: I ∈ I(M) ∩ I(N)}
= min{r_{M}(A) + r_{N}(S \ A): A ⊂ S}. (5)

[Sugestão. Consider the matroid M ∨N^{∗}, where N^{∗} is the dual of N.]

8. Let G be a connected graph, and suppose that the edges of G are coloured in an arbitrary way. Prove that G contains a spanning tree with all its edges coloured with different colours if and only if, for all subgraphs H ⊂ G of G, the number of colours that occur in E(G) \ E(H) is at least c(H) − 1, where, again, c(H) denotes the number of components in H. [Sugestão. Observe that, if S is a finite set, then the family of all sets of cardinality at most m is the family of independent sets of a matroid (this is the uniform matroid U_{n,m}, where n = |S|). Use this observation for m = 1 and S the colour classes of the edge colouring of G. Apply the above theorem of Edmonds. Alternatively, give a proof from first principles.]