Combinatoire algébrique
Cet article est une ébauche concernant l’algèbre.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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
[modifier | modifier le code]Le notion de « combinatoire algébrique » est apparue à la fin des années 1970[1]. 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[2].
Principe
[modifier | modifier le code]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
[modifier | modifier le code]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[3].
Sujets importants
[modifier | modifier le code]Schémas d'association
[modifier | modifier le code]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[4],[5],[6].
Graphes fortement réguliers
[modifier | modifier le code]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[7],[8], et leurs compléments, les graphes de Turán.
Tableaux de Young
[modifier | modifier le code]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
[modifier | modifier le code]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[9],[10].
Géométries finies
[modifier | modifier le code]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
[modifier | modifier le code]Groupes définis par générateurs et relations
[modifier | modifier le code]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
[modifier | modifier le code]Des questions de combinatoire se posent en manipulant des groupes finis : compter le nombre d'éléments d'un ordre donné, d'une orbite…
Références
[modifier | modifier le code]- (en) « Algebraic Combinatorics » [PDF], sur School of Mathematical Sciences Shanghai Jiao Tong University
- « Classification Search Result - zbMATH Open », sur zbmath.org (consulté le )
- (en) Ian G. Macdonald, Symmetric Functions and Hall Polynomials, (ISBN 0-19-853489-2, lire en ligne)
- (en) Rosemary A. Bailey, Association schemes: designed experiments, algebra and combinatorics, (ISBN 9780521824460, lire en ligne)
- (en) Paul-Hermann Zieschang, Theory of association schemes, (ISBN 3540261362)
- (en) Paul-Hermann Zieschang, « Association Schemes: Designed Experiments, Algebra and Combinatorics by Rosemary A. Bailey, Review » [PDF], sur Bulletin of the American Mathematical Society,
- (en) Andries E. Brouwer et Willem H. Haemers, Spectra of Graphs, (ISBN 1489994335)
- (en) Chris Godsil et Gordon Royle, Algebraic graph theory, (ISBN 9780387952413)
- (en) David L. Neel et Nancy Ann Neudauer, « Matroids You Have Known »
