CS 604 Assignment 4: my solutions

Transversal Matroids and Gammoids.

Problem 1

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.

Let X be a cyclic flat or rank r. Then there is a subset S of N(X) with $|S|=r$ such that every independent set in X can be matched to a subest of S. Consider an element $e\in N(X)-S$ . e is a neighbor of some element $x\in X$ . Also, x must be contained in some circuit $C\subseteq X$ . Now, C-x is an independent set and can be matched to some subset W of S. But then C can be matched to $S\cup e$ , which would mean C is independent. This would be a contradiction and hence, $N(X)-S$ should be empty.

Problem 2

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?

Suppose for all $b\in B$ , G contains a matching $m_{1}$ of $A\backslash N(b)$ to $B\backslash b$ of rank r(M)-1. Then we cannot delete any edge $a b$ for $a\in N(b)$ as $m_{1}\oplus ab$ is a matching of rank r and since no other vertex from $m_{1}$ is a neighbor of b, we cannot get a matching of same rank from the same vertex subset upon deletion of that edge and hence we cannot get the same independent set in the reduced graph. Since this is true for all b, the representative graph is minimal.

Problem 3

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.

$U_{k,n}$ is a transversal matroid of rank k. Let the smallest bipartite graph representation be G(A,B). Now for every $b\in B$ , $G\backslash N(b)$ must have a rank k-1 matching. But since every k size subset in $U_{k,n}$ is independent, there cannot be more than k-1 elements in $A\backslash N(b)$ . Therefore, n-(k-1) elements must be neighbors of b, corresponding to n-(k-1) edges incident on b. Since this is true for all b, there are $k(n-(k-1))$ edges in the graph G(A,B).

The graph representation of the strict gammoid is as follows. Take G to be a graph with n vertices. Select k out of the n points and connect every other vertex to these vertices by directed edges. In this graph, every subset of size less than k is linked to some subset of the chosen k vertices.

Problem 4

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

Problem 5

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.

We construct the directed graph representation of the gammoid as follows. On a subspace which is an intersection of m hyperplanes, we know that a subset is independent only if its size is less than or equal to $d+1-m$ . Moreover, if it holds for all hyperplane intersections then the subset is independent. For each such subspace, construct $d+1-m$ representative vertices. Also take one vertex for each element of the ground set of the matroid, and make this set the start set of the graph. Construct the edges as follows. Join $v_{i}\rightarrow v_{j}$ if $v_{i}$ represents a subspace (here the matroid elements are also taken to be point subspaces) which is contained in the subspace represented by $v_{j}$ but there is no $S(v_{k})$ such that $S(v_{i})\subset S(v_{k})\subset S(v_{j})$ where S(v) is the subspace point v represents. Connect all points representing the hyperplanes to d+1 copies of point representing the polytope. The target set is the set of d+1 points which represent the polytope. We see that a subset of start set can be linked to a subset of target set only if it obeys the bound on the maximum number of independent points in a subspace.