Matroïde uniforme

En mathématiques, un matroïde uniforme est un matroïde où les ensembles indépendants sont les sous-ensembles contenant au plus $r$ éléments, pour $r$ fixé. Une définition équivalente est que chaque permutation des éléments est une symétrie.

Exemple

On considère un ensemble $E$ = {1, 2, 3, 4} à quatre éléments. En prenant $r$=2, on obtient un matroïde uniforme si on déclare que les ensembles indépendants sont les sous-ensembles à au plus 2 éléments, à savoir : l'ensemble vide, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}.

Définition

Le matroïde uniforme $U_n^r$ est défini comme un ensemble $E$ à $n$ éléments. Un sous-ensemble de $E$ est indépendant si et seulement si il contient au plus $r$ éléments. $r$ est appelé le rang du matroïde.

Propriétés

Un sous-ensemble de $E$ est une base s'il a exactement $r$ éléments. Un sous-ensemble de $E$ est un circuit s'il a exactement $r+1$ éléments. Le rang d'un sous-ensemble $X$ est $\min (\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(X),r)$.