Matroide del rango

In combinatorica si dice matroide del rango una struttura della forma (E,r), dove E è un insieme ed r una funzione che ha come dominio l'insieme delle parti P(E), come codominio un insieme della forma {0,1,2,...,k} e gode delle seguenti proprietà

1. r(A) ≤ |A| per tutti i sottoinsiemi A di E.
2. Se A e B sono sottoinsiemi di E con A ⊆ B, allora r(A) ≤ r(B) (proprietà di isotonia).
3. Per ogni coppia di sottoinsiemi di E A e B, abbiamo r(A ∪ B) + r(A ∩ B) ≤ r(A) + r(B).

Diciamo insieme indipendente di una matroide del rango (E,r) ogni J sottoinsieme di E tale che sia r(J) = |J|. Se I denota la collezione di tali insiemi, si dimostra che (E,I) è una matroide degli indipendenti.