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$.