Dominik Farhan

Rank function

We define rank function $r: 2^X \rightarrow \mathbb{N}$ as follows $r(A) = \max_{B \subseteq A \land B \in S} |B|$

Theorem (Equivalent definition of $r$ ). Function

r: 2^X \rightarrow \mathbb{N}

is the rank of a matroid iff it satisfies the following properties

$r(\emptyset) = 0$
$r(Y)\leq r(Y \cup \{ y\}) \leq r(Y) + 1$
$r(Y \cup \{y\}) = r(Y \cup \{z\}) = r(Y) \implies r(Y \cup \{ y, z\}) = r(Y)$

Solution ( $\implies$ )

Proof.

emptyset is by definition part of $S$ and its size is $0$ .
Adding an element to $Y$ cannot decrease size of the maximum independent subset but it can increase it by at most $1$ element.
Idea: both $y, z$ are dependent with the rest, so adding both is also dependent. Suppose that maximal independent sets of $Y$ and $Y \cup \{y, z\}$ have different size. Then surely the second is greater than the first. But only elements that can be in the second but not in the first are $y, z$ . If however any of those elements was included we get a contradiction with the assumption $r(Y \cup \{y\}) = r(Y \cup \{z\}) = r(Y)$ .

Solution ( $\Longleftarrow$ )

Proof.

Let $r$ be a function from the theorem satisfying $1,2,3$ . We are going to show that it is a rank of the matroid $(X, S)$ where $A \in S \iff r(A) = |A|$ .

Surely $\emptyset \in S$ , first matroid property holds.
Let $A \in S$ and $B\subset A$ . Assume that $r(B) \neq |B|$ and also that $|A \setminus B| = 1|$ (we can get all other cases by iterating the following arguments) and show how to obtain a contradiction.
- $r(B) < |B|$ : $r(B) \leq r(A) \leq r(B) + 1$ $|B| - 1 \leq |B + 1| \leq |B|$ which is contradiction.
- $r(B) > |B|$ : From the assumption we get $r(B) \geq r(A) + 1$ . By the second property: $r(B) \leq r(A) \leq r(B) + 1$ combining it together we get a contradiction: $r(A) + 1 \leq r(B) \leq r(A).$
Assume that there is $A, B \in S$ s.t. $|A| > |B|$ and we cannot enlrage $B$ by an element of $A$ . Then by iterating the third property we can show that $|A| = |B|$ , contradiction.

Submodularity

Theorem (Submodularity).

r: 2^X \rightarrow \mathbb{N}

is the rank of a matroid iff the following holds

$\forall Y \subseteq X: 0 \leq r(Y) \leq |Y|$
$Z \subseteq Y \implies r(Z) \leq r(Y)$
$r(Y \cup Z) + r(Y \cap Z) \leq r(Y) + r(Z)$ .

Solution ( $\implies$ )

Proof.

triv.
triv.
Let $A$ be the maximal independent subset of $Z \cap Y$ . $A_Y$ the maximal independent subset of $Y$ that satysfies $A \subset A_Y$ (such subset must exist). $A_Z$ the maximal independent subset of $Z$ that satysfies $A \subset A_Z$ (such subset must exist). Now observe that $r(Y) + r(Z) = |A_Y \cap A_Z| + |A_Y \cup A_Z| = r( Y \cap Z) + |A_Y \cup A_Z|$ To prove the third property we just need to show that $|A_Y \cup A_Z| \geq r(A_Y \cup A_Z)$ . This holds if observe that $A_Y$ cannot be enlraged by more than $|A_Z \setminus Y|$ elements to be independent in $Y \cup Z$ . Why? Assume the contrary: Let $W \subset Z \setminus Y$ that is $|W| > |A_Z \cup A_Y|$ for which $W \cup A_Y$ is stil independent in the union. Then $|W \cup A| > \geq |A_Z|$ which contradict the maximality of $A_Z$ .

Solution ( $\Longleftarrow$ )

Proof. We will show that the properties from Equivalent definition of $r$ are satisfied.

Surely for empty set we get that $r(\emptyset) = 0$ .
This we get by combining monotony and submodularity.
Let's use submodularity on $A = Y \cup \{y\}$ and $B = Y \cup \{z\}$ : $r(A \cup B) + r(Y) \leq r(A) + r(B)$ because $r(A) = r(B) = r(A)$ : $r(A \cup B) \leq r(Y)$ By monotonicity $r(A \cup B) \geq r(Y).$

The previous theorem tells us that matroids are the systems where rank is monotone and submodular.

Submodular functions !

They are good for modeling value in combinatorial auctions. Let there be $X$ and $f: 2^X \rightarrow \mathbb{N}$ . Then for all $x\in X$ we define $\Delta f_x : 2^X \rightarrow \mathbb{Z}: \forall T \subseteq X: \Delta f_x (T) = f(T \cup \{x\}) - f(T).$ In essence how much we value adding $x$ to $T$ .

Theorem (Marginal value and submodularity).

$f: 2^X \rightarrow \mathbb{N}$ is submodular iff $\forall x \in X: \Delta f_x$ is non-increasing, meaning that if $A\subseteq B, x\notin B$ then $\Delta f_x(B) \leq \Delta f_x(A)$ .

Solution ( $\implies$ )

Easy part. Let's use just

x

for

\{x\}

for convinience. What we want is

f(T \cup x) - f(T) \leq f(T' \cup x) - f(T')

which is the same as

f(T \cup x) + f(T') \leq f(T \cup x) + f(T)

whis is exactly what submodularity gives us.

Solution ( $\Longleftarrow$ )

Hard part. What we want:

f(Y) + f(z) \geq f(Y \cap Z) + f(Y \cup Z).

We do it by induction on

Y \Delta Z

. Noone knows how

Matroids: Rank function and submodularity

Rank function

Submodularity

Submodular functions !