Assignment 1

Prove that an element e in a matroid is contained in all bases if and only if it is not contained in any circuit.

Let B be a collection of subsets of a finite set E, satisfying the following properties:

a) B is not empty.

b) For any two sets B1, B2 in B, and any element e in B1, there exists an element f in B2 such that (B1-e)+f is in B. (+ denotes union)

Give an example to show that B need not be the set of bases of a matroid. Suppose, we add another condition:

c) No subset in B is a proper subset of another subset in B.

Now show that B must be the set of bases of some matroid.

Give an example of two matroids M1 and M2 on the same set E, such that a subset X of E is a circuit of M1 iff X is a basis of M2. Characterize all possible such pairs of matroids.

Let M be a matroid and X and Y be subsets of E(M), each of which contains a basis. Prove that if |X| > |Y| then for some element x in X-Y, X-x also contains a basis.

Show that if B1, B2 are any two distinct bases of a matroid, then for every element e in B2-B1, there exists an element f in B1-B2, such that B1+e-f is also a basis. Show that any non-empty collection of subsets satisfying the property must be the set of bases of a matroid.