§ Matroids for greedy algorithms (TODO)

§ Definitions of matroids

A matrioid $M$ is a set $X$ equipped with an independence set $I \subseteq 2^X$.

• The empty set is independent: $\emptyset \in I$.
• The independence set is downward-closed/closed under subsets: $\forall i \in I, \forall i' \subseteq i, i' \in I$.
• For any independent sets $A, B \in I$, if $\vert A \vert$ is larger than $\vert B \vert$, then we must be able to add an element from $a \in A$ into $B' \equiv B \cup {a}$ such that $B'$ is both independent and larger than $B$: $B' \in I \land \vert B' \vert > \vert B \vert$. ( The exchange property )

§ Example 1: Linearly independent sets

Let $V$ be a vector space. The independent sets $I$ are of the form:

This is an independence system because the empty set is linearly independent, and subsets of a linearly independent collection of vectors will be linearly independent.
The exchange property is satisfied because of linear algebraic reasons.

§ Example 2: The graphic/cyclic Matroid: Matroid of Forests

Let $G = (V, E)$ be a graph. Then collections of edges of the form:

is an independence system because the empty forest is a forest, and a subset of edges of a forest continues to be a forest.
To check the exchange property, TODO

§ Example 3: The partition matroid

Consider the partition matroid $M \equiv (E, I)$, where we have a partitioning of $E$ known as $E_i$, and numbers $k_i$ the independence set consists of subsets $F$ which have at most $k_i$ elements in common with each $E_i$.
The independence axioms are intuitively satisfied, since our constraints on picking edges are of the form $\vert F \cap E_i \vert \leq k_i$, which will continue to hold as $F$ becomes smaller.
For the exchange axiom, let $\vert Y \vert > \vert X \vert$. Then, we can assert that for some index $i$, it must be the case that $\vert Y \cap E_i \vert > \vert X \cap E_i \vert$. Hence, we can add an element in $E_i \cap (Y / X)$ into $X$ whilst still maintaining independence.

§ Bases and Circuits

• Bases are the maximal independent sets of $I$ (ordered by inclusion). On adding an element into a basis element, they will become dependent. They are called bases by analogy with linear algebra.

• Circuits are minimal dependent sets of $I$. This comes from analogy with trees: if we remove an element from any circuit (loop) in a graph, what we are left with is a tree.

A matroid can be completely categorized by knowing either the bases or the circuits of that matroid.

§ Unique Circuit property

• Theorem : Let $M \equiv (E, I)$ be a matroid, and let $S \in I, e \in E$ such that $S \cup \{e \} \not \in I$.

Then, there exists a unique circuit $C \subseteq S \cup \{ e \}$.
That is, when we go from independent to dependent by adding an element, we will have a single, unique circuit . For example, when we add an edge into a forest to create a cycle, this cycle will be unique!

§ Proof

Let $C_1, C_2$ be circuits created when $e$ was added into $S$, where $C_1$ is the largest circuit of $S$, and $C_2$ is the smallest circuit of $S$.
Notice that $C_1, C_2$ must contain $e$ --- if they did not, then $C_1, C_2$ would be circuits in $S$, contradicting the assumption that $S$ is independent.
Recall that $C_1, C_2$ are both circuits, which means that removing even a single element from them will cause them to become independent sets.
Let us contemplate $C \equiv C_1 \cup C_2$. Either $C = C_1$ in which case we are done.
Otherwise, $\vert C \vert > \vert C_1 \vert$, $\vert C \vert > \vert C_2 \vert$.
Otherwise, consider $C' \equiv C \ \{ e \} = (C_1 \cup C_2) \ \{e\} = (C_1 \ \{e\}) \cup (C_2 \ \{ e \})$.

• $C' \subseteq S$, since $C_1 \ \{e\}, C_2 \ \{e\} \subseteq S$.
• $S$ is an independent set, all of whose subsets are independent by definition. So $C'$ is an independent set.
• $\vert C' \vert \geq \vert C_1 \vert$, $\vert C' \vert \geq \vert C_2 \vert$.

Now, we consider $C$. Clearly, this is a dependent set, since $C_1 \subsetneq C$, and $C_1$ is a dependent set.
Since, $C = C' \cup \{e \}$, this means that $C'$ is a maximally independent set. Since $C'$ does not contain $e$, $C' = S$.

§ Rank functions

A rank function of a matroid $M \equiv \langle X, I \rangle$ is a function:

That is, for any subset $S \subseteq X$, $r(S)$ is the cardinality of the largest independent subset of $S$.

• In the matroid of linearly independent sets of vectors, the rank of a set of vectors is the dimension of their spanning set.

In this matroid, the
TODO: picture

§ Intersection of matroids is not necessarily a matroid:

M1 = < d {[(a) (b)] c}>

M2 = < {d [(a) (b)]} c>

The intersection of these two matroids will be:

M1 cap M2 = < d [(a) (b)] c>

This is not a matroid because the exchange property fails. There's no way to go from [a, b] to < d a b c > by exchanging one element.

§ Bipartite matching as matroid intersection

Matchings in a bipartite graph $G = (V, E)$ with partition $(A, B)$ arise as the intersection of the independent sets of two matroids. We will denote by $\delta: V \rightarrow 2^E$ the function which takes a vertex to the set of edges incident on that vertex.
Let $M_A$ be a partition matroid : $M_A \equiv (E, I_A)$ where $I_A$ is: That is, in $I_A$, every independent set has for each vertex of $A$, at most one edge incident. We need to check that this is an independent set. The empty set of no edges is independent. If some collection of edges are such that they have at most one edge incident, then removing edges can only decrease incidence. Hence, it's also downward closed.
TODO: add picture
Similarly, we define $M_B \equiv (E, I_B)$:
Now, notice that any collection of edges $F \in I_A \cap I_B$ is a legal matching, since the edges cover all vertices of $A$ and $B$ at most once. The largest element of $I_A \cap I_B$ is the maximum matching that we are looking for.

§ Largest common independent set

Given two matroids $M_1 \equiv (E, I_1)$, $M_2 \equiv (E, I_2)$, with rank functions $r_1$ and $r_2$. Let $S \in I_1 cap I_2$ and let $F \subseteq E$.

• $\vert S \vert = \vert S \cap F \vert + \vert S \cap (E / F) \vert$.

§ References:

• Michel Goeman's standalone notes on matroids
• Michel Goeman's standalone notes on matroid intersection
• Lecture 11 of Michel Goeman's lecture on Advanced Combinatorial Optimisation
• Video lecture on fixed-parameter tractability and matroid interesction
• FTP Lecture 25: introduction to matroids
• FTP lecture 26: Faster matroid intersection