Matroïde uniforme

Cet article ne cite pas suffisamment ses sources (septembre 2014).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

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

On considère un ensemble ${\displaystyle E}$ = {1, 2, 3, 4} à quatre éléments. En prenant ${\displaystyle 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}.

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

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

• Portail des mathématiques