Partition Matroid

discrete-mathematics combinatorics

Definition

Partition Matroid

A partition matroid is a matroid $M=(E,\mathcal{I})$ defined by a partition of the ground set $E$ into $t$ disjoint subsets $E_1,\dots ,E_t$ and by $t$ non-negative integers $k_1,\dots ,k_t$.

A subset $X\subseteq E$ is independent if and only if, for every $i\in [t]$,

$$|X\cap E_i|\le k_i.$$

That is,

$$\mathcal{I}=\{X\subseteq E\mid |X\cap E_i|\le k_i\text{ for all }i\in [t]\}.$$

Each block $E_i$ contributes its own local capacity $k_i$, and independence only constrains how much of each block is used.

Examples

Two blocks with capacity $1$

Let $E=\{a,b,c,d\}$ be partitioned into $E_1=\{a,b\}$ and $E_2=\{c,d\}$, with $k_1=k_2=1$.

A set is independent if it contains at most one element from $\{a,b\}$ and at most one from $\{c,d\}$. So

$$\{a,c\},\{a,d\},\{b,c\},\{b,d\}$$

are all independent, while $\{a,b\}$ and $\{c,d\}$ are dependent. The bases are the four sets that take exactly one element from each block, and the rank is $k_1+k_2=2$.