Combinatoire algébrique

En mathématiques, la combinatoire algébrique est une discipline qui traite de l'étude des structures algébriques par des techniques algorithmiques et combinatoires, comme notamment illustré par les travaux de Marcel-Paul Schützenberger, Alain Lascoux, Dominique Foata, Richard Peter Stanley…

Histoire

Le notion de « combinatoire algébrique » est apparue à la fin des années 1970. Au début des années 1990, la combinatoire algébrique s'intéressait principalement à des objets possédant de nombreuses symétries (schémas d'association, graphes fortement réguliers, posets avec une action de groupe) ou à des objets possédant une structure algébrique riche, émanant généralement de la théorie des représentations (fonctions symétriques, tableaux de Young). Cette période se reflète dans la rubrique 05E, Algebraic combinatorics, de la classification des matières mathématiques de l'AMS, introduite en 1991.

Principe

L'intérêt de la combinatoire algébrique vient du fait que la plupart des structures en algèbre abstraite sont soit finies, soit engendrées par un ensemble fini d'éléments, ce qui rend possible leur manipulation de manière algorithmique.

Fonctions symétriques

L'anneau des fonctions symétriques est une limite spécifique des anneaux de polynômes symétriques à n indéterminées, lorsque n tend vers l'infini. Cet anneau sert de structure universelle dans laquelle les relations entre polynômes symétriques peuvent être exprimées de manière indépendante du nombre n d'indéterminées (mais ses éléments ne sont ni des polynômes ni des fonctions). Cet anneau joue entre autres un rôle important dans la théorie des représentations des groupes symétriques.

Sujets importants

Schémas d'association

Un schéma d'association est un ensemble de relations binaires satisfaisant certaines conditions de compatibilité. Les schémas d'association fournissent une approche unifiée de nombreux sujets, par exemple le design combinatoire et la théorie des codes. En algèbre, les schémas d'association généralisent les groupes, et la théorie des schémas d'association généralise la théorie des caractères des représentations linéaires des groupes.

Graphes fortement réguliers

Un graphe fortement régulier est défini comme suit : Soit G = (V , E) un graphe régulier à v sommets et de degré k. G est dit fortement régulier s'il existe également des entiers λ et μ tels que :

• Toute paire de sommets adjacents a exactement λ voisins communs.
• Toute paire de sommets non-adjacents a exactement μ voisins communs.

Un graphe respectant ces conditions est dit fortement régulier de type (v,k,λ,μ).

Certains auteurs excluent les graphes qui satisfont trivialement à la définition, à savoir les graphes qui sont l'union disjointe d'un ou plusieurs graphes complets de taille égale, et leurs compléments, les graphes de Turán.

Tableaux de Young

Un tableau de Young est un objet combinatoire utile en théorie des représentations et en calcul de Schubert. Il fournit un moyen pratique de décrire les représentations de groupe des groupes symétriques et linéaires généraux et d'étudier leurs propriétés. Les tableaux de Young ont été introduits par Alfred Young, mathématicien à l'université de Cambridge, en 1900. Ils ont ensuite été appliqués à l'étude du groupe symétrique par Georg Frobenius en 1903. Leur théorie a été développée par de nombreux mathématiciens, dont Percy MacMahon, WVD Hodge, G. de B. Robinson, Gian-Carlo Rota, Alain Lascoux, Marcel-Paul Schützenberger et Richard P. Stanley.

Matroïdes

Un matroïde est une structure qui capture et généralise la notion d'indépendance linéaire dans les espaces vectoriels. Il existe de nombreuses manières équivalentes de définir un matroïde, les plus importantes étant en termes d'ensembles indépendants, de bases, de circuits, d'ensembles fermés, d'opérateurs de fermeture et de fonctions de rang.

La théorie des matroïdes emprunte largement à la terminologie de l'algèbre linéaire et de la théorie des graphes, en grande partie parce qu'elle est l'abstraction de diverses notions d'importance centrale dans ces domaines. Les matroïdes ont trouvé des applications en géométrie, en topologie, en optimisation combinatoire, en théorie des réseaux et en théorie des codes.

Géométries finies

Une géométrie finie est un système géométrique qui ne possède qu'un nombre fini de points. La géométrie euclidienne familière n'est pas finie, car une ligne euclidienne contient une infinité de points. Une géométrie basée sur les graphiques affichés sur un écran d'ordinateur, où les pixels sont considérés comme les points, serait une géométrie finie. Bien qu'il existe de nombreux systèmes qui pourraient être qualifiés de géométries finies, l'attention est principalement portée sur les espaces projectifs et affines finis en raison de leur régularité et de leur simplicité. D'autres types importants de géométrie finie sont les plans de Möbius (en) finis et les plans de Laguerre (en), qui sont des exemples d'un type général appelé plans de Benz (en), et leurs analogues de dimension supérieure tels que les géométries inversives finies supérieures.

Les géométries finies peuvent être construites par algèbre linéaire, à partir d'espaces vectoriels sur un corps fini; les plans affines et projectifs ainsi construits sont appelés géométries de Galois. Les géométries finies peuvent également être définies de manière purement axiomatique. Les géométries finies les plus courantes sont des géométries de Galois, car tout espace projectif fini de dimension trois ou plus est isomorphe à un espace projectif sur un corps fini (c'est-à-dire la projection d'un espace vectoriel sur un corps fini). Cependant, la dimension deux a des plans affine et projectif qui ne sont pas isomorphes aux géométries de Galois, à savoir les plans non-arguésiens. Des résultats similaires s'appliquent à d'autres types de géométries finies.

Théorie des groupes

Groupes définis par générateurs et relations

Dans un groupe défini par générateurs et relations, les éléments sont représentés par des mots écrits avec l'alphabet des générateurs, et les relations peuvent naturellement s'interpréter comme un ensemble de règles de réécriture.

Groupes finis

Des questions de combinatoire se posent en manipulant des groupes finis : compter le nombre d'éléments d'un ordre donné, d'une orbite…