elements in common with each $E_i$.
$I \equiv \{ F \subseteq E : \forall i = 1, \dots N, \vert F \cap E_i \vert \leq k_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:
$r: 2^X \rightarrow \mathbb N : r(S) = \max \{ \vert T \vert : T \subseteq S \land T \in I \}$
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:
$I_A \equiv \{ F \subseteq E : \vert F \cap \delta(a) \vert \leq 1 \forall a \in A \}$
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)$:
$I_B \equiv \{ F \subseteq E : \vert F \cap \delta(b) \vert \leq 1 \forall b \in 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: