Combinatoire et algèbre

Source: Zumthie at de.wikipedia [Public domain], via Wikimedia Commons

Description du programme

On constate de plus en plus de liens entre l'étude des structures discrètes, d'une part, et les mathématiques classiques, algèbre, analyse, géométrie, théorie des nombres, d'autre part. Il s'agit donc d'exploiter les interactions toujours profondes entre ces domaines en vue d'un enrichissement mutuel de ces spécialités ou, encore, de retombées significatives dans des domaines d'applications variés comme l'informatique, la physique, la géométrie algorithmique, la bioinformatique, la recherche opérationnelle ou la cryptographie.

Les outils modernes de l'informatique font évidemment partie intégrante du programme. En particulier, les logiciels et algorithmes de calcul formel algébrique seront d'utilisation courante et feront même l'objet de développements substantiels au sein du programme.

Les recherches poursuivies par les membres du groupe incluent : la combinatoire énumérative et la combinatoire algébrique, l'algèbre commutative et non commutative, l'informatique théorique, la combinatoire des mots, la bioinformatique.

Les chercheurs du groupe sont affiliés à deux groupes de recherches :

Membres du programme

Formation

Ce programme s'adresse aux étudiants gradués ayant une solide formation mathématique et voulant se spécialiser en mathématiques discrètes et/ou dans certains aspects de l'informatique théorique. À part les règlements des départements, aucun cours de base n'est obligatoire mais les premiers cours de base en combinatoire, en théorie des graphes et en algorithmique sont fortement recommandés.

Cours 2023-24

Automne

Combinatoire I

Revue des outils élémentaires de dénombrement, ensembles pondérés, démonstrations bijectives et involutives, q-analogues. Séries génératrices, partages d'entiers, q-séries, séries rationnelles, récurrences linéaires. Séries génératrices exponentielles, théorie des espèces de structures, formule d'inversion de Lagrange, espèces pondérées, applications. Théorie de Polya-Joyal, séries indicatrices, théorèmes de composition et pléthysme, application au dénombrement de types de graphes et d'arbres. Espèces tensorielles et foncteurs polynomiaux. Liens entre représentations de groupes symétriques et représentations de groupes généraux linéaires.

Prof. François Bergeron

MAT 7352

Institution: Université du Québec à Montréal

Algèbre

Lemme de Zorn. Catégories et foncteurs: notions et exemples de base: catégories de structures mathématiques, monoïde, catégorie des ensembles; section, rétraction, exemples géométriques et algébriques. Foncteurs et transformations naturelles: exemples de base, catégories de foncteurs. Équivalence de catégories: exemples de base. Modules. Théorèmes d'homomorphisme et d'isomorphisme. Sommes et produits directs, modules libres. Modules de type fini sur un anneau principal et applications aux formes canoniques des matrices. Modules noethériens et artiniens: exemples et propriétés de base. Modules indécomposables, théorème de Krull-Schmidt. Anneaux et polynômes: nilradical et localisation; élimination classique, ensembles algébriques, théorème des zéros de Hilbert. Théorie des corps: groupe de Galois, résolution par radicaux; indépendance algébrique, degré de transcendance, dimension des ensembles algébriques irréductibles; corps ordonnables, 17<+>e<+> problème de Hilbert.

Prof. Christophe Reutenauer

MAT 7600

Institution: Université du Québec à Montréal

Hiver

Combinatorics

Enumerative combinatorics: inclusion-exclusion, generating functions, partitions, lattices and Moebius inversion. Extremal combinatorics: Ramsey theory, Turan's theorem, Dilworth's theorem and extremal set theory. Graph theory: planarity and colouring. Applications of combinatorics.

Prof. Sergey Norin

MATH 550

Institution: Université McGill

Géométrie et combinatoire

Géométries finies: treillis géométriques. Ensembles partiellement ordonnés, extensions linéaires; complexes simpliciaux associés. Propriétés de Sperner; théorèmes de Dilworth et de Greene. Aspects combinatoires de la topologie algébrique. Configurations combinatoires; applications aux statistiques.


Prof. François Bergeron

MAT 7431

Institution: Université du Québec à Montréal

Séminaire de combinatoire et algèbre: Théorie algébrique des automates

Prof. Christophe Reutenauer

MAT 995

Institution: Université du Québec à Montréal

Sujets en optimisation

Le contenu du cours sera en partie précisé suivant les intérêts des étudiants. Les grandes lignes sont les suivantes:

  • Définitions et résultats de base.
  • Arbres, arborescences.
  • Connexité : théorèmes de Menger et les équivalences entre les résultats de Menger, Dilworth, König, Hall, Ford-Fulkerson (flots).
  • Homomorphismes, colorations.
  • Graphes de Cayley.
  • Théorie extrémale : théorèmes de Turan, de Ramsey.
  • Graphes infinis : lemme de König, théorème de Ramsey, compacité.

Prof. Gena Hahn

IFT 6580

Institution: Université de Montréal