Uniform Matroid

discrete-mathematics combinatorics

Definition

Uniform Matroid

A matroid $M=(E,\mathcal{I})$ over an $n$-element ground set $E$ is a uniform matroid $U_{k,n}$ if the family of independent sets is

$$\mathcal{I}=\{X\subseteq E\mid |X|\le k\}$$

for some constant $k\in \{0,1,\dots ,n\}$. A subset is independent exactly when its size is at most $k$.

Example

$U_{2,4}$

Let $E=\{1,2,3,4\}$ and $k=2$. Then

$$\mathcal{I}=\{\varnothing ,\{1\},\{2\},\{3\},\{4\},\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\}.$$

Every subset of size at most $2$ is independent; the subsets of size $3$ and $4$ are dependent. The bases are exactly the six $2$-element subsets, so the rank is $2$.