Assignment 4

Let G(A,B) be a bipartite graph representing a transversal matroid M. For any vertex v, let N(v) denote the set of neighbours of v in the graph. For any subset X of vertices, let N(X) be the union of neighbours of vertices in X. Show that a subset X of A is a closed set (flat) in the matroid M iff A-X = N(Y) for some subset Y of B. A flat is said to be cyclic if it is the union of circuits, in other words, every element in the flat is contained in a circuit that lies inside the flat. Prove that for any cyclic flat X of rank r, |N(X)| = r. Give an example to show that this may not be true for all flats.

In this problem, we will try to find the smallest bipartite graph G(A,B) that represents a given transversal matroid M. As we have seen |B| may be chosen to be r(M). Suppose G(A,B) is a representation of M with minimum number of edges and vertices. Let b be any vertex in B. Show that $G$ contains a matching of size $r(M)-1$ in which no vertex in $N(b)$ is matched. Is the converse true? That is, does this property imply the number of edges in the representation is minimum?

What is the minimum number of edges in a representation of the uniform matroid U_{k,n}? Prove your answer. Show that U_{k,n} is a strict gammoid by describing a directed graph G with n vertices, containing a subset B of k vertices such that every subset of k vertices is linked to B.

Find an example of a graphic matroid that is not a gammoid.

Let P be any convex polytope in d-dimensional space, that is, P is the intersection of some set of d-dimensional half-spaces. Let E be a subset of points in P. A subset X of E is defined to be independent iff there is no subset Y of X that is contained in the intersection of P with d+2-|Y| of the hyperplanes that bound the polytope P. Prove that this defines a matroid on E and prove that this matroid is a gammoid.