CS 604 Assignment 5: my solutions

Initial ideas for solutions discussed with Shaunak Dhar.

Problem 1

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.

a) Suppose M were reducible. Then every basis can be written as $X\cap Y$ with $X\subseteq M_{1}\subset M$ and $Y\subseteq M_{2}\subset M$ , $M_{1}\cap M_{2}=\phi$ . Since $r(T)=r(M)$ , T contains at-least one basis. Restricting to T, every basis in T can be written as $X\cap Y$ with $X\subseteq M_{1}|T\subset M|T$ and $Y\subseteq M_{2}|T\subset M|T$ . But this is not possible since T is irreducible. Hence M cannot be reducible.

b) Take a 2-connected graph such that one subgraph is connected to another through 2 vertices. Delete edges from one of the two vertices to make the other vertex a cut-vertex. The original graphic matroid was connected but the restricted matroid after edge deletions is reducible.

c) If $r(T)=r(M)$ condition is removed, then we may have a matroid which is, say, union of two irreducible matroids one of which is T.

d) $F_{7}$ has $U_{3,4}$ as restriction to a subset. $U_{3,4}$ is irreducible (Since every 3 elements are independent, the ground sets in the two components would be independent and hence the total ground set would be independent if it were reducible), and also $U_{3,4}$ has the same rank as $F_{7}$ . Hence $F_{7}$ is irreducible.

Problem 2

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.

Problem 3

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})|\geq|X_{1}|+|X_{2}|+k-2|B|$ .

a) We show that if there exists a matching of size k then $2|B|-|X_{1}|-|X_{2}|\geq k-|N_{1}(X_{1})\cap N_{2}(X_{2})|$ . This is clearly true if LHS is greater than or equal to k. Assume that $LHS=m<k$ . Since a k-matching exists there exist k vertex disjoint paths $p_{i}-q_{i}-r_{i}$ where $p_{i},q_{i},r_{i}$ belong to $B_{1}$ (B of $G_{1}$ ), A, and $B_{2}$ (B of $G_{2}$ ) respectively. If LHS is m, it means we select all but m points in $X_{1}\cup X_{2}$ from $B_{1}\cup B_{2}$ . This would correspond to losing a maximum of m paths from the matching with $k-m$ paths still remaining. Hence $|N_{1}(X_{1})\cap N_{2}(X_{2})|\geq k-m\Rightarrow k-|N_{1}(X_{1})\cap N_{2}(X% _{2})|\leq m$ . Hence $LHS\geq RHS$ .

Problem 4

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))\geq k$ for all X subset of A.

Problem 5

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.

Consider a 2-partition of the ground set. If Maker’s part contains a basis, he would win (Breaker’s part won’t contain a co-circuit in this case since his part does not intersect the basis contained in Maker’s part). If the Maker’s part does not contain any basis, then Breaker’s part intersects with every basis and hence contains a co-circuit, in which case the Breaker wins.

If there exist two disjoint bases of size r each, then Maker would always have a winning strategy. Suppose the two bases are A and B, the Maker takes the following steps. If Breaker takes an element from A (B), the Maker discards that element and replaces it with an element from B (A), while also choosing that element. At the end of k turns by Maker and Breaker each, A and B have k common elements, all of which have been chosen by Maker. Also, at each step A and B remain bases (by exchange property). Hence at the end of r turns by each player, A and B will be the same basis obtained by Maker and hence Maker would win. It is easy to see that in case Breaker chooses to pick an element from outside A and B, his step won’t affect Maker’s strategy.

If there are no two disjoint bases, then every basis intersects every other basis and hence contains a co-circuit. In this case, if Maker would have a winning strategy to obtain a basis, then so can the Breaker have a winning strategy to obtain a co-circuit, depending on who plays first. Hence, a definite winning strategy irrespective of who plays first is not possible.