Assignment 3

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(empty-set) = 0.

(b) If X is a subset of E and x an element in E, then r(X) <= r(X \cup x) <= 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 r* denote the rank function of the dual matroid M* of a matroid M. Prove that for any subset X of E, r*(X) = |X| - r(E) + r(E-X).

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.

Let M be a graphic matroid of rank r. Prove that for all 1 <= i <= 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?).

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', B_2',...,B_k') of B' such that for all 1 <= i <= k, (B-B_i) \cup B_i' is a basis.