Assignment 2

It is easy to show that in any graphic matroid, the symmetric difference of any two circuits is a disjoint union of circuits. Show that the same property holds for any binary matroid, that is, a vector matroid representable over Z_2. (Is the converse true? This is not for submission, just to think over.)

Prove that if in a matroid any two circuits have at most one element in common, then the matroid is graphic, as well as co-graphic.

Consider a weighted undirected graph whose edges are assigned integer weights. Consider the following collection of subsets of edges.

(i) A subset of edges that form a simple cycle such that the sum of weights of edges is even.

(ii) A subset of edges that form two simple cycles with at most one vertex in common such that the sum of weights of edges in each cycle is odd.

Show that these collections of subsets form the circuits of a matroid on the edges of the graph. Give an example to show that the matroid obtained need not be graphic. Is such a matroid always a vector matroid over Z_2? Can be it always be represented over any field?

A hyperplane in a matroid is a maximal subset of the ground set that does not contain a basis. Suppose a matroid contains a circuit C that is also a hyperplane. Show that if we add C to the collection of independent sets of the matroid, keeping all other dependent sets the same, we get a new matroid.

Consider the affine matroid over reals represented by the following points in 3-dimensional space: (0,0,0), (3,0,0), (0,2,0), (3,2,0), (1,1,1), (2,1,1), (1,1,-1), (2,1,-1). What are the circuits and independent sets of this matroid? The set of points {(1,1,1), (2,1,1), (1,1,-1) (2,1,-1)} is a dependent set in this matroid. Suppose we now call this set also as independent, keeping all other dependent sets the same. Show that this gives a new matroid called the Vamos matroid V_8. Show that V_8 cannot be represented over reals, and in fact it cannot be represented over any field.