CS 604 Assignment 3: my solutions

Rank, Closure, Duals.

Problem 1

Prove that a function r from $2^{E}$ to non-negative integers is the rank function of a matroid if and only if r satisfies: (a) $r(\phi)=0$ . (b) If X is a subset of E and x an element in E, then $r(X)\leq r(X\cup x)\leq r(X)+1$ . (c) If X is a subset of E and x, y are elements in E such that $r(X)=r(X\cup x)=r(X\cup y)$ then $r(X\cup x\cup y)=r(X)$ .

Let I be the class of subsets with $r(X)=X$ . We’ll show that the class follows the independence axioms of matroid.
a) $r(\phi)=0=|\phi|\Rightarrow\phi\in I$ .
b) If $X\subseteq Y$ and $Y\in I$ , then $r(Y)=|Y|\Rightarrow|Y|=r(X\cup(Y\cap X^{c}))\leq r(X)+|Y\cap X^{c}|\leq|X|+|Y% \cap X^{c}|=|Y|\Rightarrow r(X)=|X|\Rightarrow X\in I$ .
c) Let $X,Y\in I$ with $|X|<|Y|$ . Then there exists $y\in Y$ such that $X\cup y\in I$ i.e. $r(X\cup y)=|X+1|$ . If not, then for all $y\in Y$ , $r(X\cup y)=r(X)$ and hence $r(X\cup Y)=r(X).$ But $r(X\cap Y)\geq r(Y)>r(X)$ and we thus we obtain a contradiction.
Therefore, a function satisfying the three properties is a rank function for some matroid.

Now we will show that every rank function satisfies the three properties. We show that the three defining properties of the rank function imply the given properties.
a) $0\leq r(X)\leq|X|\Rightarrow 0\leq r(\phi)\leq|\phi|=0\Rightarrow r(\phi)=0$ .
b) $X\subseteq X\cup x\Rightarrow r(X)\leq r(x\cup x)$ . $r(X\cup x)+r(X\cap x)\leq r(X)+r(x)=r(X)+1\Rightarrow r(X\cup x)\leq r(X)+1$ .
c) $r((X\cup x)\cup(X\cup y))+r((X\cup x)\cap(X\cup y))=r(X\cup x)+r(X\cup y)% \Rightarrow r(X\cup x\cup y)+r(X)\leq r(X)+r(X)\Rightarrow r(X\cup x\cup y)% \leq r(X)$ . But we also have $X\subseteq X\cup x\cup y\Rightarrow r(X\cup x\cup y)\geq r(X)$ . Therefore, $r(X\cup x\cup y)=r(X)$ .

Problem 2

Let r* denote the rank function of the dual matroid M* of a matroid M. Prove that for any subset X of E, $r^{\ast}(X)=|X|-r(E)+r(E-X)$ .

r(X) is the size of the largest independent set contained in X i.e. the size of the largest subset of some basis that is contained in X. r*(X) is the size of the largest subset contained in X and having zero intersection with some basis. Let the corresponding basis be B. Since all the bases are of same size, and B has least intersection with X, it will have maximum intersection with $X^{c}$ , and hence $B\cap X^{c}$ will the largest independent set in $X^{c}$ . Also $|B|=r(E)$ , and hence,
$r^{*}(X)=|X\cap B^{c}|=|X|-|X\cap B|=|X|-(|B|-|B\cap X^{c}|)=|X|-r(E)+r(E-X).$

Problem 3

Let F be a collection of subsets of a set E. Prove that F is the set of flats of a matroid on E iff F satisfies the following: (a) E belongs to F. (b) If F1 and F2 are in F, then so is F1 intersection F2. (c) If F1 is in F, and e is an element in E-F1, then there exists a unique set F2 in F such that $F1\cup e$ is a subset of F2, and there is no set F3 in F, such that F1 is a proper subset of F3 and F3 is a proper subset of F2.

First we show the collection F of flats satisfies the properties:
a) Clearly $cl(E)=E$ , so $E\in F$ .
b) $F_{1}\cap F_{2}\subseteq F_{1}\Rightarrow cl(F_{1}\cap F_{2})\subseteq cl(F_{1% })=F_{1}$ . $F_{1}\cap F_{2}\subseteq F_{2}\Rightarrow cl(F_{1}\cap F_{2})\subseteq cl(F_{2% })=F_{2}$ . Therefore $cl(F_{1}\cap F_{2})\subseteq F_{1}\cap F_{2}\Rightarrow cl(F_{1}\cap F_{2})=F_% {1}\cap F_{2}$
c) If $F_{1}$ is a rank r flat, $F_{2}$ is a rank (r+1) flat, as there are no ranks in between, there cannot an $F_{3}$ contained in $F_{2}$ and containing $F_{1}$ .

Problem 4

Let M be a graphic matroid of rank r. Prove that for all $1\leq i\leq r$ , every (r-i)-flat of M is contained in at most $i(i+1)/2$ distinct $(r-i+1)$ -flats of M. Give an example of a binary matroid that does not satisfy this property. (Not for submission: Does this property characterize graphic matroids?).

An (r-i)-flat of a graph is obtained by partitioning the vertices into i+1 components and keeping the all the edges within each component. We can merge any two components to obtain an (r-i+1)-flat that contains the given (r-i)-flat. There are $i(i+1)/2$ such selections possible, but we can only select two components which have atleast one edge between them, giving at-most $i(i+1)/2$ possibilities.

Problem 5

Let B and B’ be any two bases of a matroid and suppose $(B_{1},B_{2},...,B_{k})$ is a partition of B. Show that there exists a corresponding partition $(B_{1}^{\prime},B_{2}^{\prime},...,B_{k}^{\prime})$ of B’ such that for all $1\leq i\leq k,(B-B_{i})\cup B_{i}^{\prime}$ is a basis.

We give a solution using induction on the number of parts. The theorem is true for 1-part partition as it would simply mean exchanging the two bases. Suppose the theorem holds for (k-1)-part partition. Let the two bases be B and B’ with the partition of B being $B_{1},\dots,B_{k}$ . From the basis exchange theorem there must exist a subset X of B’ such that $(B-B_{k})\cup X$ is a basis. Call this basis C. Construct a (k-1)-part partition of C such that $C_{i}=B_{i}$ for $i<k-1$ and $C_{k-1}=B_{k-1}\cup X$ . By induction hypothesis there exists a (k-1)-part partition of B’ such that each part can be exchanged with a corresponding part of C. A simple observation shows that if an element occurs in both the bases, it must go in the parts with the same indices in the two partitions (else the size of the basis will not be preserved upon exchange). Label this partition of B’ by $B^{\prime}_{i}$ for $i<k$ . From the observation $X\subseteq B^{\prime}_{k-1}$ . Split the part as $B^{\prime}_{k-1}\rightarrow B^{\prime}_{k-1}-X$ and $B^{\prime}_{k}\rightarrow X$ . Then this k-part partition of B’ of can be exchanged with the B partition, part by part.