A Universe of Sorts

§ 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:

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)

be a graph. Then collections of edges of the form:

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 \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

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