Matroïde

On considère un ensemble E quelconque. En prenant I l'ensemble de tous les sous-ensembles de E, on vérifie les propriétés d'hérédité et d'échange : (E, I) est un matroïde. Il s'appelle le matroïde libre.

Soient deux entiers non nuls n et k, on obtient un matroïde en prenant pour E un ensemble de n éléments quelconques et pour indépendants les sous-ensembles de cardinalité inférieure à k.

Considérons une matrice A sur un certain corps, par exemple ${\displaystyle A={\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\\\end{pmatrix}}}$. A partir de cette matrice, on définit le matroïde (E, I) où E est l'ensemble des indices de colonnes de la matrice A, et où I est la collection des sous-ensembles d'indices correspondants aux vecteurs-colonnes linéairement indépendants. De tels matroïdes sont dits représentables ou linéaires[3].

Il existe des matroïdes qui ne sont pas représentables. Les matroïdes représentables en n'utilisant que le corps à deux éléments sont dits binaires. Tutte et Whitney ont donné des caractérisations de ces matroïdes. Les matroïdes représentables sur n'importe quel corps sont dits réguliers. Tutte les a aussi caractérisés.

Une autre source d'inspiration de la théorie des matroïdes est la théorie des graphes.

Considérons un graphe fini non orienté G. On définit son matroïde associé M(G) de la façon suivante. L'ensemble E est l'ensemble des arêtes[4] de G. Puis les ensembles indépendants sont les forêts de G (c'est-à-dire les sous-ensembles d'arêtes acycliques). Les circuits (au sens de la théorie des matroïdes) correspondent alors aux circuits de G (au sens de la théorie des graphes).

Il existe des matroïdes non graphiques, c'est-à-dire que l'on ne peut pas voir ses éléments comme des arêtes d'un graphe, de façon que les ensembles indépendants soient les forêts. Par contre, tous les matroïdes de tailles 3 sont graphiques[5].

Les matroïdes graphiques sont binaires (il suffit de prendre la matrice d'incidence de G). Ils sont aussi réguliers (il suffit d'orienter arbitrairement G et de prendre la matrice d'incidence).

L'ensemble des coupes d'un graphe constitue l'ensemble des cycles d'un matroïde, que l'on appelle le matroïde cographique.

Un circuit est un ensemble dépendant minimal, c'est-à-dire un ensemble dont tous les sous-ensembles stricts sont indépendants. Pour un matroïde graphique, il s'agit d'un cycle au sens usuel. Les circuits ont la propriété suivante : si ${\displaystyle S\in I}$ et ${\displaystyle e\in E}$ tel que ${\displaystyle S\cup {e}\notin I}$, alors il existe un unique circuit inclus dans ${\displaystyle S\cup {e}}$[3].

Comme en algèbre linéaire, on peut définir une notion de rang sur les parties de E dans un matroïde M[3]. ${\displaystyle r_{M}:2^{E}\mapsto \mathbb {N}$ :\max\{|Y|:Y\subseteq X,Y\in I\}} . Le rang d'un matroïde est une fonction sous-modulaire.

À tout matroïde on peut associer son polytope des indépendants dans l'espace à ${\displaystyle |E|}$ dimensions comme suit. Un vecteur caractéristique d'un ensemble indépendant S est le vecteur de {0, 1}^E, où on met un 1 sur la coordonnée d'un élément e de E si e est dans S, et 0 sinon. Le polytope des indépendants est l'enveloppe convexe des vecteurs caractéristiques de ses indépendants. Edmonds a montré que ce polytope peut être décrit par les inégalités linéaires de positivité et de rang. Plus précisément le polytope est :

${\displaystyle \{x\in \mathbb {R} ^{|E|}:\sum _{e\in S}x_{e}\leq r_{M}(S),x_{e}\geq 0~\forall S\subseteq E,\forall e\in E\}.}$

Il existe plusieurs preuves de ce résultat[3]. On appelle polymatroïde tout polytope des indépendants d'un matroïde.

• Hassler Whitney, « On the abstract properties of linear dependence », American Journal of Mathematics, The Johns Hopkins University Press, vol. 57, n^o 3,‎ 1935, p. 509–533 (DOI 10.2307/2371182)

• Michel Goemans, « Lecture notes on matroid optimization », sur Massachusetts Institute of Technology, 2009

• Cryptomorphisme
• Antimatroïde (en)
• Matroïde orienté (en)