Combinatorics (Fall 2010)/Duality, Matroid

Duality

Consider the following LP:

[math]\displaystyle{ \begin{align} \text{maximize} && 7x_1+x_2+5x_3\\ \text{subject to} && x_1-x_2+3x_3 &\ge 10\\ && 5x_1-2x_2-x_3 &\ge 6\\ && x_1,x_2,x_3 &\ge 0 \end{align} }[/math]

Let [math]\displaystyle{ OPT }[/math] be the value of the optimal solution.

Matroid

Matroids

Let [math]\displaystyle{ X }[/math] be a finite set and [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] be a family of subsets of [math]\displaystyle{ X }[/math]. A member set [math]\displaystyle{ S\in\mathcal{F} }[/math] is called maximal if [math]\displaystyle{ S\cup\{x\}\not\in\mathcal{F} }[/math] for any [math]\displaystyle{ x\in X\setminus S }[/math].

For [math]\displaystyle{ Y\subseteq X }[/math], denote [math]\displaystyle{ \mathcal{F}_Y=\{S\in\mathcal{F}\mid S\subseteq Y\} }[/math]. Clearly [math]\displaystyle{ \mathcal{F}_Y }[/math] is the restriction of [math]\displaystyle{ \mathcal{F} }[/math] over [math]\displaystyle{ 2^Y\, }[/math].

Definition

A set system [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] is a matroid if it satisfies: (hereditary) if [math]\displaystyle{ T\subseteq S\in\mathcal{F} }[/math] then [math]\displaystyle{ T\in\mathcal{F} }[/math]; (matroid property) for every [math]\displaystyle{ Y\subseteq X }[/math], all maximal [math]\displaystyle{ S\in\mathcal{F}_Y }[/math] have the same [math]\displaystyle{ |S| }[/math].

Suppose [math]\displaystyle{ \mathcal{F} }[/math] is a matroid. Some matroid terminologies:

• Each member set [math]\displaystyle{ S\in\mathcal{F} }[/math] is called an independent set.
• A maximal independent subset of a set [math]\displaystyle{ Y\subset X }[/math], i.e., a maximal [math]\displaystyle{ S\in\mathcal{F}_Y }[/math], is called a basis of [math]\displaystyle{ Y }[/math].
• The size of the maximal [math]\displaystyle{ S\in\mathcal{F}_Y }[/math] is called the rank of [math]\displaystyle{ Y }[/math], denoted [math]\displaystyle{ r(Y) }[/math].