# 16.4 Matroids and greedy methods

## 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 $S$ of size at most $k$, where $k \le |S|$.

The first condition that $S$ is a finite set is a given. To prove the second condition we assume that $k \ge 0$, this gets us that $\mathcal I_k$ is nonempty. Also, to prove the hereditary property, suppose $A \in \mathcal I_k$ this means that $|A| \le k$. Then, if $B \subseteq A$, this means that $|B| \le |A| \le k$, so $B \in \mathcal I_k$. Lastly, we prove the exchange property by letting $A, B \in \mathcal I_k$ be such that $|A| < |B|$. Then, we can pick any element $x \in B \backslash A$, then,

$$|A \cup {x}| = |A| + 1 \le |B| \le k,$$

so, we can extend $A$ to $A \cup \{x\} \in \mathcal I_k$.

## 16.4-2 $\star$

Given an $m \times n$ matrix $T$ over some field (such as the reals), 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.

Let $c_1, \dots, c_m$ be the columns of $T$. Suppose $C = \{c_{i1}, \dots, c_{ik}\}$ is dependent. Then there exist scalars $d_1, \dots, d_k$ not all zero such that $\sum_{j = 1}^k d_jc_{ij} = 0$. By adding columns to $C$ and assigning them to have coefficient $0$ in the sum, we see that any superset of $C$ is also dependent. By contrapositive, any subset of an independent set must be independent.

Now suppose that $A$ and $B$ are two independent sets of columns with $|A| > |B|$. If we couldn't add any column of $A$ to be whilst preserving independence then it must be the case that every element of $A$ is a linear combination of elements of $B$. But this implies that $B$ spans a $|A|$-dimensional space, which is impossible. Therefore, our independence system must satisfy the exchange property, so it is in fact a matroid.

## 16.4-3 $\star$

Show that if $(S, \mathcal I)$ is a matroid, then $(S, \mathcal I')$ is a matroid, where

$\mathcal I' = \{A': S - A'$ 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)$.

Condition one of being a matroid is still satisfied because the base set hasn't changed. Next we show that $\mathcal I'$ is nonempty. Let $A$ be any maximal element of $\mathcal I$, then we have that $S - A \in \mathcal I'$ because $S - (S - A) = A \subseteq A$ which is maximal in $\mathcal I$.

Next we show the hereditary property, suppose that $B \subseteq A \in \mathcal I'$, then, there exists some $A' \in \mathcal I$ so that $S − A \subseteq A'$, however, $S − B \supseteq S − A \subseteq A$ so $B \in \mathcal I'$.

Last, we prove the exchange property. That is, if we have $B, A \in \mathcal I'$ and $|B| < |A|$, we can find an element $x$ in $A − B$ to add to $B$ so that it stays independent. We will split into two cases:

• The first case is that $|A - B| = 1$. Let $x \in A-B$ be the only element in $A - B$. Since $|A| > |B|$ and $|A - B| = 1$, it follows in this case $B \subset A$. We extend $B$ by $x$ and we have $B \cup \{x\} = A \in \mathcal I'$.
• The second case is if the first case does not hold. Let $C$ be a maximal independent set of $\mathcal I$ contained in $S − A$. Pick an aribitrary set of size $|C| − 1$ from some maximal independent set contained in $S - B$, call it $$. Since D is a subset of a maximal independent set, it is also independent, and so, by the exchange property, there is some y \in C − D so that D \cup \{y\} is a maximal independent set in \mathcal I. Then, we select x to be any element other than y in A − B. Then, S − (B \cup \{x\}) will still contain D \cup \{y\}. This means that B \cup \{x\} is independent in \mathcal I'. ## 16.4-4 \star 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: \mid A \cap S_i \mid \le 1 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. Suppose X \subset Y and Y \in \mathcal I. Then (X \cap S_i) \subset (Y \cap S_i) for all i, so$$|X \cap S_i| \le |Y \cap S_i| \le 1$$for all 1 \le i \le k. Therefore \mathcal M is closed under inclusion. Now Let A, B \in \mathcal I with |A| > |B|. Then there must exist some j such that |A \cap S_j| = 1 but |B \cap S_j| = 0. Let a \in A \cap S_j. Then a \notin B and |(B \cup \{a\}) \cap S_j| = 1. Since$$|(B \cup \{a\}) \cap S_i| = |B \cap S_i| \le 1$$for all i \ne j, we must have B \cup \{a\} \in \mathcal I. Therefore \mathcal M is a matroid. ## 16.4-5 Show how to transform the weight function of a weighted matroid problem, where the desired optimal solution is a minimum-weight maximal independent subset, to make it a standard weighted-matroid problem. Argue carefully that your transformation is correct. Suppose that W is the largest weight that any one element takes. Then, define the new weight function w_2(x) = 1 + W - w(x). This then assigns a strictly positive weight, and we will show that any independent set that that has maximum weight with respect to w_2 will have minimum weight with respect to w. Recall Theorem 16.6 since we will be using it, suppose that for our matriod, all maximal independent sets have size S. Then, suppose M_1 and M_2 are maximal independent sets so that M_1 is maximal with respect to w_2 and M_2 is minimal with respect to w. Then, we need to show that w(M_1) = w(M_2). Suppose not to achieve a contradiction, then, by minimality of M_2, w(M_1) > w(M_2). Rewriting both sides in terms of w_2, we have$$w_2(M_2) - (1 + W)S > w_2(M_1) - (1 + W)S,$$so,$$w_2(M_2) > w_2(M_1).

This however contradicts maximality of $M_1$ with respect to $w_2$. So, we must have that $w(M_1) = w(M_2)$. So, a maximal independent set that has the largest weight with respect to $w_2$ also has the smallest weight with respect to $w$.