Let
\(X\) be a finite set and
\(\mathcal{I}\subseteq 2^X\) be a non-empty downset (i.e.
Property 1 and
Property 2 hold). Prove that, if
\((X,\mathcal{I})\) has the following property, then
\((X,\mathcal{I})\) is a matroid (i.e.
Property 3 holds):
For any set \(Y\subseteq X\text{,}\) and any two subsets \(B_1,B_2\subseteq Y\) which are elements of \(\mathcal{I}\) and inclusionwise maximal subject to these properties, we have \(|B_1|=|B_2|.\)
Describe a modification of the greedy algorithm described in
Section 8.1 for finding a maximum weight independent set for weight functions
\(w:X\to\mathbb{R}\) which can have negative values and prove that your algorithm always solves the problem optimally.
Prove that if \(M=(X,\mathcal{I})\) is a matroid and \(w:X\to[0,\infty)\) is an injective weight function, then there is a unique basis of maximum weight.
Prove that transversal matroids are matroids. Hint: It helps to visualize transversal matroids in terms of matchings in the following bipartite graph. The vertices on one side are labelled with the sets \(X_1,\dots,X_m\) and the vertices on the other side are labelled with the elements of \(X\text{.}\) A set \(Y\subseteq X\) is independent in the transversal matroid if and only if there exists a matching in this graph that saturates the vertices in \(Y\text{.}\)
Use Kőnig’s Theorem to prove that, if \(M\) is the transversal matroid corresponding to sets \(X_1,\dots,X_m\text{,}\) then
\begin{equation*}
r(M)=\min_{A\subseteq \{1,\dots,m\}}\left(\left|\bigcup_{i\in A}X_i\right|+m-|A|\right).
\end{equation*}
Let \(G\) be a graph and let \(\mathcal{I}\) be the collection of all subsets \(Y\) of \(E(G)\) such that the graph \((V(G),Y)\) has at most one cycle. Prove that \((E(G),\mathcal{I})\) is a matroid.
Prove that every partition matroid is a graphic and cographic. (i.e. It can be equivalently represented as a graphic matroid and it can also be represented as a cographic matroid)
Let \(G\) be a graph. Prove that a set \(Y\subseteq E(G)\) is independent in the cographic matroid corresponding to \(G\) if and only if \(G\setminus Y\) has the same number of components at \(G\text{.}\)
Prove that \(U_4^2\) is not graphic
-
Let \(G\) be a graph. Suppose that I give you the cycle matroid \(M=(X,\mathcal{I})\) of \(G\text{,}\) but I do not tell you the graph \(G\) that it came from (also, the elements of \(X\) have been re-labelled; they are no longer pairs of vertices). Determine whether it is possible for you to determine the following properties of \(G\) from just knowing \(M\text{:}\)
The number of edges of \(G\text{.}\)
The number of vertices of \(G\text{.}\)
Whether or not \(G\) is connected.
Whether or not \(G\) contains a perfect matching.
Whether or not \(G\) contains a triangle.
Whether or not \(G\) contains a clique on twenty vertices.
Let \((X,\mathcal{I})\) be a matroid. Two elements \(x,y\in X\) are said to be parallel if \(\{x,y\}\) is circuit (this terminology makes sense if you think about linear matroids). Prove that, if \(x\) and \(y\) are parallel and \(Y\) is an independent set containing \(x\text{,}\) then \(\left(Y\setminus\{x\}\right)\cup\{y\}\) is independent.
Let \((X,\mathcal{I})\) be a matroid and label the elements of \(X\) by \(x_1,\dots,x_m\text{.}\) Define
\begin{equation*}
Y:=\{x_i: r_M(\{x_1,\dots,x_i\}) > r_M(\{x_1,\dots,x_{i-1}\})\}.
\end{equation*}
Prove that \(Y\) is independent.
Let \(M=(X,\mathcal{I})\) be a matroid, let \(k\) be a positive integer and define \(\mathcal{I}_k:=\{Y\in\mathcal{I}: |Y|\leq k\}\text{.}\) Prove that \((X,\mathcal{I}_k)\) is a matroid. This is called the \(k\)-truncation of \(M\text{.}\)
Let \((X,\mathcal{I})\) be a matroid, let \(U\) be a set disjoint from \(X\) and let \(k\) be a positive integer. Define
\begin{equation*}
\mathcal{I}_{U,k}:=\{A\cup Y: A\subseteq U, |A|\leq k, Y\in\mathcal{I}\}.
\end{equation*}
Prove that \((X\cup U, \mathcal{I}_{U,k})\) is a matroid.
Let \(k\geq1\) and let \(G\) be a graph with at least \(k\) vertices. Let \(\mathcal{I}\) be the collection of all subsets of \(E(G)\) which form a forest with at least \(k\) components. Prove that \((E(G),\mathcal{I})\) is a matroid.
Let \(G\) be a bipartite graph with bipartition \((X,Y)\text{.}\) Let \((X,\mathcal{I})\) be a matroid and define
\begin{equation*}
\mathcal{J}:=\{T\subseteq Y: \text{either }T=\emptyset\text{ or }\exists S\in\mathcal{I}\text{ such that }\exists\text{ a perfect matching in }G[S\cup T]\}.
\end{equation*}
Prove that \((Y,\mathcal{J})\) is a matroid.
Let \(G\) be a graph and, for a matching \(M\text{,}\) let \(V(M)\) be the set of vertices saturated by \(M\text{.}\) Define
\begin{equation*}
\mathcal{I}:=\{S: S\subseteq V(M)\text{ for some matching }M\text{ of maximum cardinality}\}.
\end{equation*}
Prove that \((V(G),\mathcal{I})\) is a matroid.
Let \(M=(X,\mathcal{I})\) be a matroid. A flat in \(M\) is a set \(F\subseteq X\) such that \(r_M(F\cup \{x\})>r_M(F)\) for all \(x\in X\setminus F\text{.}\) Using graph theory terms, explain what a flat in a graphic matroid is.
Let \((X,\mathcal{I})\) be a matroid and let \(w:X\to \mathbb{R}\) be a weight function. Prove that a basis \(B\) is a basis of maximum weight if and only if \(w(B)\geq w(B')\) for any basis with \(|B\setminus B'|=1\text{.}\)
Prove that the dual of a linear matroid is also a linear matroid.
Prove that every graphic matroid is a linear matroid. Hint: Take the vertex-edge incidence matrix and, in each column, change one of the \(1\)s to a \(-1\text{.}\)
Let \(M=(X,\mathcal{I})\) be a matroid and let \(M^*=(X,\mathcal{I}^*)\) be its dual. Prove that for any \(Y\subseteq X\text{,}\)
\begin{equation*}
r_{M^*}(Y) = |Y| + r_M(X\setminus Y) - r_M(X).
\end{equation*}
Let \(M=(X,\mathcal{I})\) be a matroid and \(M^*=(X,\mathcal{I}^*)\) be its dual. Prove that if there is a polynomial time algorithm to determine whether a set \(Y\subseteq X\) is in \(\mathcal{I}\text{,}\) then there is a polynomial time algorithm to determine whether a set \(Y\subseteq X\) is in \(\mathcal{I}^*\text{.}\)
Schrijver 10.7, 10.8, 10.9.
Given an example of two matroids \((X,\mathcal{I}_1)\) and \((X,\mathcal{I}_2)\) such that \((X,\mathcal{I}_1\cap\mathcal{I}_2)\) is not a matroid.
Use Edmonds’ Matroid Intersection Theorem to prove Kőnig’s Theorem.
Prove that the problem of finding a Hamiltonian cycle in a graph reduces to the problem of finding the maximum cardinality of a set in the intersection of three matroids.
Let \(G\) be a graph whose edges are coloured with any number of colours. A spanning forest in \(G\) is said to be rainbow if all of its edges have different colours. Show that the problem of finding the largest rainbow spanning forest in \(G\) can be expressed as finding the maximum cardinality of a set in the intersection of two matroids.
Use Edmonds’ Matroid Intersection Theorem to obtain a “dual problem” to the problem of finding a rainbow spanning tree in an edge coloured graph.
-
Prove Rado’s Theorem:
Rado’s Theorem: If \(M=(X,\mathcal{I})\) is a matroid and \(Y_1,\dots,Y_k\subseteq X\text{,}\) then there exists a transversal for \(Y_1,\dots,Y_k\) that is independent in \(M\) if and only if for every \(I\subseteq\{1,\dots,k\}\text{,}\)
\begin{equation*}
r_{M}\left(\bigcup_{i\in I}X\right) \geq |I|.
\end{equation*}
A rooted tree in a digraph \(D\) is a subdigraph \(T\) of \(D\) such that the underlying graph of \(T\) is a tree and all vertices of \(T\) have at most one incoming arc. Show that the problem of finding the largest rooted tree in a digraph can be expressed as finding the maximum cardinality of a set in the intersection of two matroids.
Prove that a graph \(G\) contains two disjoint spanning trees if and only if the cycle and cocycle matroids of \(G\) have a common independent set of cardinality \(|V(G)|-1\text{.}\)
Construct matroids \(M_1=(X,\mathcal{I}_1)\) and \(M_2=(X,\mathcal{I}_2)\) and a weight function \(w:X\to[0,\infty)\) such that none of the maximum weight common independent sets are also maximum cardinality common independent sets.
Show that the set
\(Y_i\) in the proof of
Lemma 8.4.2 satisfies
\(Y_i\in\mathcal{I}_1\text{.}\)
MATROID UNION (by applying matroid intersection where we take the dual of one of them). Question 10.27 in Schrijver. 10.28 is really nice too. And 10.29. And 10.31.
