Une structure combinatoire (E, I) sur un ensemble fini E avec une famille I de sous-ensembles indépendants satisfaisant des axiomes (hérédité et échange) qui généralisent l'indépendance linéaire dans les espaces vectoriels et l'absence de cycles dans les graphes.

Principe

L'indépendance est stable par passage à des sous-ensembles (hérédité) et vérifie la propriété d'échange : si A et B sont indépendants avec |A|>|B|, alors un élément de A\B peut être ajouté à B en conservant l'indépendance ; formulations équivalentes utilisent bases, fonction rang ou circuits et permettent la dualité des matroïdes.

Démonstration

Matroïde vectoriel : les colonnes d'une matrice sur un corps forment un matroïde dont les ensembles indépendants sont les sous-ensembles de colonnes linéairement indépendantes. Matroïde graphique : les arêtes d'un graphe forment un matroïde dont les ensembles indépendants sont les forêts et les circuits sont les cycles simples.

Mauvaise application

Supposer que tout matroïde est représentable sur un corps donné (beaucoup de matroïdes ne le sont pas), ou considérer des systèmes d'ensembles arbitraires avec des ensembles maximaux indépendants comme des matroïdes sans vérifier l'axiome d'échange.

Conséquence

La structure de matroïde garantit que l'algorithme glouton trouve des solutions optimales pour la maximisation pondérée d'ensembles indépendants, fournit des opérateurs rang et clôture pour l'optimisation combinatoire et supporte la dualité et les opérations de mineur imitant les mineurs de graphes et la restriction/contration en algèbre linéaire.

Inversion

Inverser le concept revient à considérer des systèmes d'indépendance arbitraires dépourvus de la propriété d'échange : ces systèmes peuvent avoir plusieurs ensembles maximaux indépendants incomparables et faire échouer l'optimalité gloutonne, perdant les théorèmes structuraux forts de la théorie des matroïdes.

Limite

La théorie classique traite d'ensembles finis bien que des matroïdes infinis existent avec des axiomes supplémentaires ; les matroïdes excluent les systèmes d'ensembles violant l'échange, et la représentabilité dépend du corps choisi, de sorte que les correspondances algébriques ne sont pas universelles.

Tension sémantique

Tension entre matroïdes abstraits et matroïdes représentables (linéaires) : beaucoup de résultats combinatoires n'exigent que les axiomes de matroïde, mais les méthodes algébriques et l'intuition géométrique s'appliquent seulement aux matroïdes représentables ; les matroïdes graphiques et cographes illustrent des perspectives duales.

Synthèse

Un matroïde abstrait le noyau combinatoire de l'indépendance en codant quels sous-ensembles d'un ensemble fini se comportent comme des ensembles linéairement indépendants via hérédité et échange, fournissant un cadre unifié pour l'optimisation, la dualité, les mineurs et les liens entre théorie des graphes et algèbre linéaire.