Assignment 5

A matroid is said to be irreducible if it cannot be written as the union of two matroids having non-zero rank. Let M be a matroid on a set E and let T be a subset of E. Prove the following statements:

a) If M|T is irreducible and r(T) = r(M) then M is irreducible. (M|T = M \ (E-T) is the restriction of M to T.)

b) Show that the converse of (a) may not hold.

c) Show that the assumption r(T) = r(M) is necessary.

d) Prove that F_7 is irreducible.

Prove that for a matroid M on a ground set E, the maximum of |X|-2r(X) taken over all subsets X of E equals the minimum of the intersection of B_1, B_2, taken over all pairs of bases B_1, B_2 of the dual M* of M.

Let G_1(A,B) and G_2(A,B) be two bipartite graphs on the same set of vertices. Prove that there exists a subset X of A with |X| = k, that can be matched to some (possibly different) subsets of B in both G_1 and G_2, iff for all X_1, X_2 subsets of B, |N_1(X_1) \cap N_2(X_2)| >= |X_1| + |X_2|+ k - 2|B|.

Let G(A,B) be a bipartite graph. Let M_1 and M_2 be matroids defined on A and B respectively. Prove that there exists a matching in G(A,B) of size k that matches an independent set of M_1 to an independent set of M_2 iff r_1(A-X) + r_2(N(X)) >= k for all X subset of A.

The Maker-Breaker game on a matroid is defined as follows. Given a matroid on a ground set E, two players alternately pick elements from E. The Maker wins by picking all elements of some basis of the matroid. The Breaker wins by picking all elements of some cocircuit. Show that either the Maker or the Breaker must win the game when all elements are picked. Find a necessary and sufficient condition on the matroid that ensures that the Maker has a winning strategy, even if the Breaker plays first.