Assignment 0

Suppose I is an independent set in a matroid, and e an element such that I \cup e is not independent. Prove that I \cup e contains exactly one circuit.

The third property of independent sets says that if X, Y are independent sets such that |X| < |Y|, then there exists an element y in Y-X such that X \cup y is also independent.

a) Suppose the condition "y in Y-X" is replaced by "y in Y". Give an example to show that a collection satisfying this property may not be a matroid. (Note that in this case the y may already be in X).

b) Suppose that instead of all pairs X, Y of independent sets such that |X| < |Y|, we consider only those pairs X, Y such that |X-Y| = 1 and |Y-X| = 2. Suppose the third property holds only for such pairs of subsets. Show that the collection is still a matroid. In other words, if the property holds for such X,Y it holds for all X,Y with |X| < |Y|.

Consider n points in the plane, not necessarily distinct. Define a collection of subsets of points as follows. The empty set belongs to the collection. A single point is in the collection if it is not the origin. A subset of 2 points is in the collection if there is no line that includes the origin and both the points. No subset of 3 or more points is in the collection. Show that this collection of subsets is a matroid. Suppose M is an arbitrary matroid in which any independent set has size at most 2. Can M always be obtained in this way?

Let E be a set and C1 a collection of subsets of E, such that each subset in C1 has size exactly 3, and any two subsets in C1 intersect in at most one element. Let C be the collection of subsets X of E, such that X is either in C1, or is a 4-element subset of E that does not contain any subset in C1. Show that the collection C forms a matroid. Can you characterize the matroids that can be obtained this way?