2. The Definition

Acknowledgements

The part of the write up that introduces terminology and examples is borrowed from Chapter E of Jeff Erickson’s textbook on Algorithms.

Recall that from last time, we were dealing with:

• a finite universe of elements $\cal U = \{e_1, e_2, \cdots, e_n\}$
• a weight function $w: \cal U \longrightarrow \mathbb{Q}^{\geqslant 0}$ that assigns a non-negative weight with every universe element
• oracle access to a family $\cal F = \{S_1, \ldots, S_m\}$ of subsets of $\cal U$

and we wanted to determine the maximum weight attained by any set in $\cal F$, where the weight of a set is defined as the sum of the weights of the elements that belong to it. To this end, we proposed the following greedy algorithm:

A Greedy Algorithm

1. Sort the elements of $U$ in descending order of weight; i.e, WLOG $w(e_1) \geqslant \cdots \geqslant w(e_n)$.
2. Initialize a solution: specifically, let $X = \emptyset$.
3. For $i \in [n]$: if $X \cup \{e_i\} \in \cal F$, $X \longleftarrow X \cup \{e_i\}$.

and concluded that it does not quite work, but might if the family came with the following promise:

If $S$ and $T$ are two subsets of $\cal U$ with $T \in \cal F$ and $|S| > |T|$, then $\exists e \in S \setminus T$ such that $T \cup \{e\} \in \cal F$.

This is exactly what we need to make our proof work out: recall that $T$ corresponds to the greedy choices, which always correspond to a set in $\cal F$, while $S$ corresponds to a subset of the optimal solution, which has no obligation to be in $\cal F$. Let us call a family fantastic if it satisfies the property above. It is not difficult to show that the greedy algorithm produces the correct output when the input is a fantastic family: we leave this as an exercise.

However, notice that this is not a very interesting defintion. Consider any family $\cal F$ that is non-trivial, i.e, has at least one non-empty subset of $U$ in it: call this $X$. Then, by triggering this property on $X \cup \{e\}$ for any $e \notin X$, we see that all “immediate supersets” of $X$ are forced to also belong to $\cal F$. Carrying this argument forward, we see that all supersets of $X$ are forced to belong to $\cal F$. In particular, if $\emptyset \in \cal F$ — which will be the case for most applications of this framework — then the only family $\cal F$ that qualifies as fantastic is the family of all possible subsets of $U$. So… while our notion of a fantastic family is perfectly well-defined and even useful, it is also rather restrictive and therefore uninteresting.

Our next step is to see if we can still get to our desired outcome (i.e, the correctness of the greedy algorithm), while not being so demanding with our definition. How about we modify our constraint to the following:

If $S$ and $T$ are two sets with $S \in \cal F$ and $T \in \cal F$, and $|S| > |T|$, then $\exists e \in S \setminus T$ such that $T \cup \{e\} \in \cal F$.

So let us say that a family is nice if it satisfies the property above. Can we now push our proof of correctness for the greedy algorithm above? Unfortunately, the answer is a negative. Can you come up with a counterexample before reading on?

A Counterexample

Let:

• $\cal U = \{p,q\}$
• $w(p) = 40, w(q) = 30$
• $\cal F = \{\{q\},\{pq\}\}$

The greedy output will be $\{q\}$, while the optimal output is $\{pq\}$. Notice that the family is nice!

So well, it is back to the drawing board. Let us recall how our proof was supposed to go. Let:

• $T$ be the set of greedy choices up to the $(i-1)^{th}$ iteration, and
• $S$ be the set of optimal choices up to the $i^{th}$ iteration,

then the hope was that the property above would rescue us and contradict the greedy choices, since $|S| > |T|$. However, in the counterexample above, we are unable to take advantage of the fact that $\cal F$ is a nice family because $S \notin \cal F$. Note that the optimal solution is obliged to only output a set in $\cal F$, but the intermediate choices as we are viewing them now have no obligation to necessarily belong to $\cal F$.

One way to force this is to insist that our family be heriditary, that is, the inclusion of a set $S \in \cal F$ implies the inclusion of all subsets of $S$ in $\cal F$ as well. If this were true, then $S \in \cal F$ since $S$ is a subset of the optimal solution, which we know to be in $\cal F$. Note that the counterexample above did not involve a heriditary family. It turns out that this combination of properties is both: (a) permissive, in that a non-trivial number of families enjoy the property; and (b) useful, in that it gives us enough leverage to prove the correctness of the greedy algorithm.

With all this, we are now ready to bring up the official definition of a matroid.

Matroids

A matroid $(\cal U, \cal F)$ consists of a finite ground set $\cal U$ and a collection $\mathcal{F}$ of subsets of $\cal U$ that satisfies three axioms:

• Non-emptiness. The empty set is in $\mathcal{F}$. (Thus, $\mathcal{F}$ is not itself empty.)

• Heredity. If $\mathcal{F}$ contains a subset $S \subseteq \cal U$, then $\mathcal{F}$ contains every subset of $S$.

• Exchange. If $S$ and $T$ are two sets in $\cal F$ where $|S|>|T|$, then $T \cup\{e\} \in \mathcal{F}$ for some element $e \in S \backslash T$.

You can think of the first property as a formality that excludes the empty family from being a matorid. The other two have independent historical motivations, but we have also just seen a good reason to find these properties particularly desirable: which is the way it plays into the proof of correctness of our greedy algorithm.

Speaking of history, let us introduce some terms commonly associated with matroids. Some of these words may ring familiar if you have encountered linear algebra before: and indeed, the crossover is not unintented — a fundamental type of matroid is one that is naturally associated with a matrix, and a lot of the terms are inspired from this setting.

First, the sets of $\cal F$ are called independent sets, and all subsets of $\cal U$ that did not make it to $\cal F$ are called — you guessed it — dependent sets. Note that the exchange axiom ensures that all maximal sets of a matroid $\cal F$ have the same size. The maximal sets are called a basis, and their common size is called the rank of a matroid. A minimal dependent set is called a circuit.

Before moving on, we enlist some examples of matroids, to reaffirm the idea that the definition indeed allows for a variety of interesting set systems. We do not elaborate on the details of how these families satisfy the matroid axioms: the motivated reader is welcome to pursue this further as an exercise.

• Uniform matroid $U_{k, n}$. A subset $X \subseteq\{1,2, \ldots, n\}$ is independent if and only if $|X| \leq k$. Any subset of $\{1,2, \ldots, n\}$ of size $k$ is a basis; any subset of size $k+1$ is a circuit.

• Graphic/cycle matroid $\mathcal{M}(G)$. Let $G=(V, E)$ be an arbitrary undirected graph. A subset of $E$ is independent if it defines an acyclic subgraph of $G$. A basis in the graphic matroid is a spanning tree of $G$; a circuit in this matroid is a cycle in $G$.

• Cographic/cocycle matroid $\mathcal{M}^*(G)$. Let $G=(V, E)$ be an arbitrary undirected graph. A subset $I \subseteq E$ is independent if the complementary subgraph $(V, E \backslash I)$ of $G$ is connected. A basis in this matroid is the complement of a spanning tree; a circuit in this matroid is a cocycle-a minimal set of edges that disconnects the graph.

• Matching matroid. Let $G=(V, E)$ be an arbitrary undirected graph. A subset $I \subseteq V$ is independent if there is a matching in $G$ that covers $I$.

• Disjoint path matroid. Let $G=(V, E)$ be an arbitrary directed graph, and let $s$ be a fixed vertex of $G$. A subset $I \subseteq V$ is independent if and only if there are edge-disjoint paths from $s$ to each vertex in $I$.

Up next, we consolidate our learnings, and present a proof that should strike the reader as at least slightly boring, given that it is completely predictable in the light of our discussion so far.