Combinatorics and Algebra

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

Program Description

There are increasingly important links between the study of discrete structures on the one hand and classical mathematics such as algebra, analysis, geometry and number theory on the other. The exploration of these deeper interactions is mutually beneficial to both areas as new problems and insights are developed. This work will have important applications in areas such as computer science, physics, computational geometry, computational biology, operations research and cryptography.

Modern computational tools play an important role in this program. In particular, the use and development of algorithms and software for algebraic computation are an important aspect of the program.

Research interests of the members of the group include: enumerative and algebraic combinatorics, commutative and non-commutative algebra, theoretic computer science, the combinatorics of words, and computational biology.

Researchers in this group are afficilated with two research groups:

Program Members

Academic Program

This program is designed for strong graduate students with an interest in discrete mathematics and/or some theoretical aspects of computer science. There are no formal programme requirements beyond the departmental requirements. However basic courses in combinatorics, graph theory and algorithms are highly recommended.

2023-24 Course Listings

Fall

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

Winter

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: McGill University

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 995N

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