discrete-mathematics combinatorics
Definition
Partition Matroid
A partition matroid is a matroid
defined by a partition of the ground set into disjoint subsets and by non-negative integers . A subset
is independent if and only if, for every , That is,
Each block
contributes its own local capacity , and independence only constrains how much of each block is used.
Examples
Two blocks with capacity
Let
be partitioned into and , with . A set is independent if it contains at most one element from
and at most one from . So are all independent, while
and are dependent. The bases are the four sets that take exactly one element from each block, and the rank is .