§ Matroids for greedy algorithms (WIP)

§ Definitions of matroids

A matrioid MM is a set XX equipped with an independence set I2XI \subseteq 2^X.

§ Example 1: Linearly independent sets

Let VV be a vector space. The independent sets II are of the form:
I{SV : vectors in S are lineary independent} I \equiv \{ S \subseteq V ~:~ \text{vectors in $S$ are lineary independent} \}
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)G = (V, E) be a graph. Then collections of edges of the form:
I{FE:F contains no cycles} I \equiv \{ F \subseteq E : \text{$F$ contains no cycles} \}
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(E,I)M \equiv (E, I), where we have a partitioning of EE known as EiE_i, and numbers kik_i the independence set consists of subsets FF which have at most kik_i elements in common with each EiE_i.
I{FE:i=1,N,FEiki} 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 FEiki\vert F \cap E_i \vert \leq k_i, which will continue to hold as FF becomes smaller. For the exchange axiom, let Y>X\vert Y \vert > \vert X \vert. Then, we can assert that for some index ii, it must be the case that YEi>XEi\vert Y \cap E_i \vert > \vert X \cap E_i \vert. Hence, we can add an element in Ei(Y/X)E_i \cap (Y / X) into XX whilst still maintaining independence.

§ Bases and Circuits

  • Bases are the maximal independent sets of II (ordered by inclusion). On adding an element into a basis element, theywill become dependent. They are called bases by analogy with linear algebra.
  • Circuits are minimal dependent sets of II. This comes from analogy with trees: if we remove an elementfrom 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(E,I)M \equiv (E, I) be a matroid, and let SI,eES \in I, e \in E such that S{e}∉IS \cup \{e \} \not \in I.
Then, there exists a unique circuit CS{e}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 C1,C2C_1, C_2 be circuits created when ee was added into SS, where C1C_1 is the largest circuit of SS, and C2C_2 is the smallest circuit of SS. Notice that C1,C2C_1, C_2 must contain ee --- if they did not, then C1,C2C_1, C_2 would be circuits in SS, contradicting the assumption that SS is independent. Recall that C1,C2C_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 CC1C2C \equiv C_1 \cup C_2. Either C=C1C = C_1 in which case we are done. Otherwise, C>C1\vert C \vert > \vert C_1 \vert, C>C2\vert C \vert > \vert C_2 \vert. Otherwise, consider CC {e}=(C1C2) {e}=(C1 {e})(C2 {e})C' \equiv C \ \{ e \} = (C_1 \cup C_2) \ \{e\} = (C_1 \ \{e\}) \cup (C_2 \ \{ e \}).
  • CSC' \subseteq S, since C1 {e},C2 {e}SC_1 \ \{e\}, C_2 \ \{e\} \subseteq S.
  • SS is an independent set, all of whose subsets are independent bydefinition. So CC' is an independent set.
  • CC1\vert C' \vert \geq \vert C_1 \vert, CC2\vert C' \vert \geq \vert C_2 \vert.
Now, we consider CC. Clearly, this is a dependent set, since C1CC_1 \subsetneq C, and C1C_1 is a dependent set. Since, C=C{e}C = C' \cup \{e \}, this means that CC' is a maximally independent set. Since CC' does not contain ee, C=SC' = S.

§ Rank functions

A rank function of a matroid MX,IM \equiv \langle X, I \rangle is a function:
r:2XN:r(S)=max{T:TSTI} r: 2^X \rightarrow \mathbb N : r(S) = \max \{ \vert T \vert : T \subseteq S \land T \in I \}
That is, for any subset SXS \subseteq X, r(S)r(S) is the cardinality of the largest independent subset of SS.
  • In the matroid of linearly independent sets of vectors, the rank ofa 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)G = (V, E) with partition (A,B)(A, B) arise as the intersection of the independent sets of two matroids. We will denote by δ:V2E\delta: V \rightarrow 2^E the function which takes a vertex to the set of edges incident on that vertex. Let MAM_A be a partition matroid: MA(E,IA)M_A \equiv (E, I_A) where IAI_A is:
IA{FE:Fδ(a)1aA} I_A \equiv \{ F \subseteq E : \vert F \cap \delta(a) \vert \leq 1 \forall a \in A \}
That is, in IAI_A, every independent set has for each vertex of AA, 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 MB(E,IB)M_B \equiv (E, I_B):
IB{FE:Fδ(b)1bB} 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 FIAIBF \in I_A \cap I_B is a legal matching, since the edges cover all vertices of AA and BB at most once. The largest element of IAIBI_A \cap I_B is the maximum matching that we are looking for.

§ Largest common independent set

Given two matroids M1(E,I1)M_1 \equiv (E, I_1), M2(E,I2)M_2 \equiv (E, I_2), with rank functions r1r_1 and r2r_2. Let SI1capI2S \in I_1 cap I_2 and let FEF \subseteq E.
  • S=SF+S(E/F)\vert S \vert = \vert S \cap F \vert + \vert S \cap (E / F) \vert.

§ References: