The section introduces matroids, an abstract combinatorial structure which sort of generalises the greedy approach. It is interesting that if we can cast a problem as a matroid, we can apply the exact same greedy method which yields optimal solutions. In fact - it is true that greedy is optimal on a problem if and only if the problem can be represented as a matroid!

A matroid is an ordered pair \(M=(S,\mathcal{I})\) satisfying the following conditions:

  1. \(S\) is a finite set.
  2. \(\mathcal{I}\) is a nonempty family of subsets of \(S\), called the independent subsets of \(S\), such that if \(B\in \mathcal{I}\) and \(A\subseteq B\), then \(A\in \mathcal{I}\). We say that \(\mathcal{I}\) is hereditary if it satisfies this property. Note that \(\emptyset\) is neccessarily a member of \(\mathcal{I}\).
  3. If \(A\in \mathcal{I}, B\in \mathcal{I}\), and \(\lvert A\rvert < \lvert B\rvert\), then there exists some element \(x\in B - A\) such that \(A\cup \{x\} \in \mathcal{I}\). We say that \(M\) satisfies the exchange property.

A natural example given is the graphic matroid \(M_G = (S_G, \mathcal{I}_G)\), defined in terms of an undirected graph \(G=(V,E)\) as follows:

  • The set \(S_G\) is defined to be \(E\)
  • A set of edges \(A\) is independent if and only if the subgraph \(G_A = (V,A)\) forms a forest (i.e. \(A\) is acyclic).

\(M_G\), defined as such, is proven to be a matroid.

Here is a summary of the other important definitions/theorems covered:

  • Given a matroid \(M=(S,\mathcal{I})\), we call an element \(x\notin A\) an extension of \(A\in\mathcal{I}\) if \(A\cup \{x\} \in \mathcal{I}\). With reference to the graphic matroid, an edge \(e\) is an extension to a forest \(A\) if and only if the addition of \(e\) does not create a cycle.
  • If \(A\) is an independent subset in a matroid \(M\), we say that \(A\) is maximal if it has no extensions.
  • (Theorem 16.6) All maximal independent subsets in a matroid have the same size. (e.g. all spanning trees are maximal independent subsets and have the same number of edges)
  • A matroid \(M=(S,\mathcal{I})\) is weighted if it is associated with a weight function \(w\) that assigns a striclty positive weight \(w(x)\) to each element \(x\in S\). The function \(w\) extends to subsets of \(S\) by summation, i.e. \(w(A) = \sum_{x\in A} w(x)\) for any \(A\subseteq S\). E.g. if we let \(w(e)\) denote the weight of an edge \(e\), then \(w(A)\) is the total weight of the edges in edge set \(A\).
  • Given a weighted matroid \(M=(S,\mathcal{I})\), suppose we sih to find an independent set \(A\in\mathcal{I}\) such that \(w(A)\) is maximised. We call such a subset an optimal subset of the matroid. Note that since \(w(x)\) is always positive, an optimal subset is always a maximal independent subset.

On maximal independent sets

A maximal independent set is called a basis for the matroid - as per linear algebra!. Matroids also serve to abstract the notion of independence in vector space, however I don’t feel qualified to expand on that here :(

Interesting reference

In other words, the maximum-spanning-tree problem on a connected undirected graph \(G=(V,E)\) boils down to finding an optimal subset of the weighted matroid \(M_G\), where weight function \(w(e)\) is the weight of the edge \(e\). This also corresponds easily to the minimum-spanning-tree problem, by tweaking \(w(e)\) slightly.

The following is the “characteristic” greedy algorithm given which works for any weighted matroid. The algorithm takes as input a weighted matroid \(M=(S,\mathcal{I})\) with an associated positive weight function \(w\), and returns an optimal subset \(A\):

  1. A = \(\emptyset\)
  2. sort \(S\) into decreasing order by weight \(w\)
  3. for each \(x\) in \(S\) taken in decreasing order:
  4.  if \(A \cup \{x\}\in \mathcal{I}\)
  5.   \(A=A\cup \{x\}\)
  6. return \(A\)

If the check for independence on set \(A\cup\{x\}\) takes \(O(f(n))\), the entire algorithm runs in time \(O(n\,log\,n + nf(n))\).

Problem 16.4-1 Show that \((S,\mathcal{I_k})\) is a matroid, where \(S\) is any finite set and \(\mathcal{I_k}\) is the set of all subsets of size at most \(k\), where \(k\leq \lvert S \rvert\).

Proof:

Since \(S\) is finite, it suffices to show the hereditary and exchange properties.

For any \(A\in\mathcal{I_k}\,\), if \(B \subseteq A\), then \(\lvert B\rvert \leq \lvert A\rvert \leq k\). Thus \(B \in \mathcal{I_k}\) and \(\mathcal{I_k}\) is hereditary.

If \(A\in\mathcal{I_k}, B\in\mathcal{I_k}\) and \(\lvert A\rvert < \lvert B\rvert\), then pick an element \(x \in B - A\). We have \(\lvert A\cup \{x\}\rvert = \lvert A\rvert + 1 \leq \lvert B\rvert \leq k\), thus \(A\cup\{x\} \in \mathcal{I_k}\). Hence \((S,\mathcal{I_k})\) satisfies the exchange property.

Problem 16.4-2 Given an \(m \times n\) matrix \(T\) over some field, show that \((S,\mathcal{I})\) is a matroid, where \(S\) is the set of columns of \(T\) and \(A\in\mathcal{I}\) if and only if the columns in \(A\) are linearly independent. ()

Proof:

Linear algebra.

Problem 16.4-3 Show that if \((S,\mathcal{I})\) is a matroid, then \((S,\mathcal{I}')\) is a matroid, where \(\mathcal{I}' = \{A':S-A' \,\text{contains some maximal}\, A\in \mathcal{I}\}\), that is, the maximal independent sets of \((S,\mathcal{I}')\) are just the complements of the maximal independent sets of \((S,\mathcal{I})\).

Proof:

It suffices to show the hereditary and exchange properties hold on \(\mathcal{I'}\).

Suppose \(A\in\mathcal{I'}\), that is there is some maximal \(X\subseteq\mathcal{I}\) contained within \(S-A\). Let any \(B\subseteq A\), then \(X\subseteq S - A \subseteq S-B\), thus \(B\in \mathcal{I'}\), and \(\mathcal{I'}\) is hereditary.

Consider any \(A,B \in \mathcal{I}'\) such that \(\lvert A\rvert < \lvert B\rvert\). We split into two cases.

Case 1: If \(\lvert B-A\rvert = 1\), then in this case \(A\subset B\), and we can simply extend \(A\) to \(B\) for the exchange property to hold.

Case 2: Let \(m\) be the size of any maximal independent set in \(\mathcal{I}\), and let \(Q\) be some maximal independent set contained in \(S-B\). Note \(\lvert T\rvert = m\). Then let \(P\) be some size \(m-1\)-subset of some maximal independent set in \(S-A\). By the exchange property on \(\mathcal{I}\), there exists some \(x\) in \(Q-P\) such that \(P\cup\{x\}\) is a maximal independent set. Since \(\lvert B-A\rvert > 1\), there must be an element \(y\in B-A\), \(y\neq x\) such that \(S-(A\cup\{y\})\) contains \(P\cup\{x\}\), i.e. we have extended \(A\) to another independent set in \(\mathcal{I}'\).

Note: I think this is known as the dual of a matroid \(M\).

Problem 16.4-4 Let \(S\) be a finite set and let \(S_1, S_2, \ldots ,S_k\) be a partition of \(S\) into nonempty disjoint subsets. Define the structure \((S,\mathcal{I})\) by the condition that \(\mathcal{I} = \{A:\lvert A\cap S_i\rvert \leq 1\,\text{for}\, i=1,2,\ldots,k\}\). Show that \((S,\mathcal{I})\) is a matroid. That is, the set of all sets \(A\) that contain at most one member of each subset in the partition determines the independent sets of a matroid.

Proof:

Hereditary property - Let \(A\in\mathcal{I}\), and suppose \(B\subseteq A\). Then clearly \(\lvert B\cap S_i\rvert \leq \lvert A\cap S_i\rvert \leq 1\) for any disjoint subset \(S_i\). Thus \(B\in \mathcal{I}\).

Exchange property - Let \(A,B \in \mathcal{I}\) such that \(\lvert A\rvert < \lvert B\rvert\). Each element in \(B\) must be in distinct subsets of the partition, and similarly for \(A\). Since \(\lvert A\rvert < \lvert B\rvert\), there must be some \(x \in B\) such that \(x \in S_i\) and \(\lvert A\cap S_i\rvert = 0\), for some subset of the partition \(S_i\). Then we can extend \(A\) to \(A\cup\{x\}\), satisfying the exchange property.