Matroid Theory

Definition 1.1 (Walk)

Given a graph $G$, a walk in $G$ is a finite sequence of edges of the form $v_0,v_1,...,v_m$ where $v_i$ is a vertex of $G$.

If the edges in the walk is distinct, then it is a trail.

If the vertices in the walk is distinct, then the trail is a path. (except $v_0 = v_m$)

Definition 1.2 (Closed Path)

If $v_0=v_m$ in a path, then it is a closed path which is know as a cycle

Definition 1.3 (Matroid)

Matroid : ordered pair $M=(S,I)$ following three conditions

1. $S$ is finite set
2. $I$ is non-empty family of subsets of $S$, called the independent subsets of $S$ such that if $B\in I$ and $A\subseteq B$, then $A\in I$. (Hereditary property)
3. If $A\in I, B \in I$ and $|A|<|B|$, then there exists some element $x\in B-A$ such that $A\cup\{x\} \in I$. (Exchange Property)

Example 1.4 ($m\times n$ matrix T)

Given matrix T, $(S,I)$ is matroid, where $S$ is the set of independent columns of $T$ and $A\in I$ if and only if columns in $A$ are linearly independent

Examples 1.5 (graphic matroid)

$G=(V,E)$ and graphic matroid $M_G=(S_G,I_G)$ defined as below

• $S_G$ is defined to be $E$, the set of edges of $G$
• If $A$ is subset of $E$, then $A\in I_G$ if and only if $A$ is acyclic. That is a set of edges $A$ is independent if and only if the subgraph $G_A=(V,A)$ forms a forest.

Theorem 1.6 (Forest)

If $G=(V,E)$ is an undirected graph, then $M_G=(S_G,I_G)$ is a matroid

Proof)

1. $S_G$ is finite
2. Heredity
   • subset of forest is forest
3. Exchange Property
   • $G_A=(V,A)$, $G_B=(V,B)$ are forests of $G$ and $|B|>|A|$ . That is, $A$ and $B$ are acyclic sets of edges and $B$ contains more edges than $A$ does. (They have same number of vertices but diffenent number of edges. Some vertex may be isolated)
   • forest $F=(V_F,E_F)$ contains $|V_F|-|E_F|$ trees.
     • $|E_F|=\sum\limits^t_1e_t=\sum\limits^t_1(v_t-1)=|V_F|-t$
   • $B$ has less tress than $A$
   • Therefore, $B$ has some tree that connects trees in $A$

Definition 1.7 ( Extension )

Given a matroid $M=(S,I)$, $x \notin A$ is an extension of $A\in I$ , if we can add $x$ to $A$ while preserving independence.

Definition 1.8 ( Maximal )

If $A$ is an independent subset in a matroid $M$, $A$ is maximal if it has no extensions.

Theorem 1.9 (Maximal independent sets)

All maximal independent subsets in a matroid have the same size

Proof)

Proof By Contradiction

Example 1.10 (Spanning Tree)

For a connected, undirected graph, every maximal independent subset of $M_G$ has $|V|-1$ edges which is called a spanning tree

Definition 1.6 ( Weighted Matroid )

$w(x)$ for each element $x\in S$.

Then, an edge has weight $w(e)$ and the edge set $A$ has a weight $w(A)=\sum\limits_{x\in A} w(x)$

$A$ is optimal subset of matroid if $A\in I$ and $w(A)$ is maximized.

Example 1.7 ( Minimum Spanning Tree)

• mst problem is minimizing the length function $w(e)$ given a connected graph $G=(V,E)$.
• To view this as finding an optimal subset of matroid, consider a weighting fucntion $w'(e)=w_0-w(e)$ where $w_0$ is a constant
• Then, $w'(A)=\Sigma_{e\in A}w'(e)=(|V|-1)w_0-w(A)$
• Therefore, for any maximal independent subset $A$ which is the spanning tree, finding the optimal subset is the solution of the mst problem

Example 1.8 ( Greedy Algorithm )

• $M=(S,I)$ ⇒ $M.S\;and\;M.I$
• weight function $w$

GREEDY (M,w)

A= {}
sort M.S into monotonically decreasing order by w
for each x in M.S:
	if A U {x} in M.I:
		A = A U {x}
return A

 

Lemma 1.9 ( Matroid exhibit the greedy choice property)

$M=(S,I)$ with weighted function $w$ and $S$ is sorted monotonically decreasing by $w$

$x$ is the first element of $S$ such that $\{x\}$ is independent. Then $x$ is in the optimal set $A$.

Proof ) Proof by Heredity and Exchange Property

$x$가 포함되어 있지 않은 다른 maximal subset $B$와 $A={x}$ 라고 생각해보자.

Exchange Property에 의해 |A|=|B|가 될 때까지 $B$에서 $A$로 어떤 원소를 추가할 수 있고, 따라서 $w(A)>w(B)$가 된다.

Lemma 1.10 (Extension)

If $x$ is an extension of $A\in I$ , then $x$ is extension of $\empty$ set. 대우에 대해서도 생각해보세요!

Lemma 1.11 (Matroids exhibit the optimal-substructure property)

Let $x$ be the first element of $S$ chosen my greedy algorithm for the weighted matroid $M=(S,I)$. The remianing problem of finding a maximum weight independent subset containing $x$ reduces to finding a maximum weight independent subset of weighted matroid $M'=(S',I')$. where

$S'=\{y\in S:{x,y}\in I\}$

$I'=\{B\subseteq S-\{x\} :B\cup \{x\}\in I\}$

Proof)

If $A$ is any maximum weight independent subset of $M$ containing $x$, then $A'=A-\{x\}$ is an independent subset of $M'$. Conversely any independent subset of $A'$ of $M$ yields an independent subset $A=A'\cup\{x\}$ of $M$. Since we have both $w(A)=w(A')+w(x)$, a maximum weight solution of $M$ containing $x$ yields a maximum weight solution of $M'$. 즉 , M'의 optimal set은 M의 Optimal set의 부분집합이 된다.