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.

2021-22 Course Listings

Fall

Théorie de la représentation des groupes finis

Représentations et module d'un groupe G, représentations équivalentes, sous-module. Représentations indécomposable, réductible, irréductible. Théorème de Maschke. Morphisme, lemme de Schur.

Algèbre de groupe, fonctions sur cette algèbre, fonction de classe. Caractères, relations d'orthogonalité, tables de caractères. Représentation régulière. Analyse de Fourier sur les groupes finis, identité de Parseval, théorème de Wedderburn.

Nombres algébriques, théorème de la dimension, théorème de Burnside. Action de groupe, lemme de Burnside, paires de Gelfand.

Représentations induites, théorème de réciprocité de Frobenius, critère d'irréductibilité de Mackey.

Marche aléatoire sur les groupes finis. Modèles de Gilbert–Shannon–Reeds, théorèmes de Diaconis.

Prof. Yvan Saint-Aubin

MAT 6621

Institution: Université de Montréal

Combinatoire 1

Ce cours sert comme introduction au niveau des cycles supérieurs à la combinatoire algébrique et énumérative, avec une emphase sur les méthodes efficaces. Les sujets de base comprendront les séries formelles ordinaires et exponentielles, les objets classiques de la combinatoire (partages, chemins dans un réseau, graphes, permutations), méthodes asymptotiques, suites vérifiant des récurrences linéaires, et l'occurrence et le comportement des séries rationnelles, algébriques, et D-finies. Dépendant des intérêts des étudiants, on pourrait aussi regarder les séries formelles à plusieurs variables, l'application des logiciels pour la combinatoire, démonstrations algorithmique de transcendence des constants, questions de calculabilité et complexité dans l'énumération, et les liens avec les langues formelles 

This course serves as a graduate introduction to enumerative and algebraic combinatorics, with a focus on effective methods. Our core topics include ordinary and exponential generating functions, classical combinatorics objects (partitions, lattice paths, graphs, permutations), asymptotic methods, sequences satisfying linear recurrence relations, and the occurrence and behaviour of rational, algebraic, and D-finite functions. Depending on student interest, more advanced topics could include multivariate generating functions, computer algebra tools for combinatorics,  algorithmic transcendence of constants vs generating functions, computability and complexity questions in enumeration, and connections to formal languages.

Prof. François Bergeron

MAT 7352

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

Algèbre

Compléments sur la théorie des groupes: 

- actions de groupes ; orbites ; stabilisateurs

- calcul dans les groupes de permutations:

- orbite et stabilisateur d'un élément;

- système de représentants du stabilisateur d'un élément;

- ordre d'un groupe de permutations;

- test d'appartenance à groupe de permutations;

- forme normale des éléments;

- algorithme de Todd-Coxeter.

Théorie des catégories:

- définition et exemples des catégories;

- foncteurs;

- transformations naturelles;

- propriétés universelles;

- (co)produits, produit fibré et somme amalgamée;

- équivalence des catégories.

Théorie des modules:

- modules artiniens et noethériens;

- modules simples, semisimples, indécomposables;

- théorèmes de Jordan-Holder, Krull-Schmidt et Artin-Wedderburn;

- notion de dimension d'un module;

- produit tensoriel de modules.

Prof. Franco Saliola

MAT 7600

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

Combinatoire algébrique et géométrique

Prof. Christophe Hohlweg

MAT995D

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

Partially ordered sets, linear extensions, lattices, and associated simplicial complexes. Sperner properties; theorems of Dilworth and Greene. Combinatorial aspects of algebraic topology. Hyperplane arrangements.

Prof. Hugh Thomas

MAT7431

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

Séminaire de combinatoire : Pléthysme

Le séminaire portera provisoirement sur le "pléthysme", ce qui peut être défini comme une opération sur les fonctions symétriques ; comme une opération sur les représentations des groupes linéaires GL(n) ; ou comme une opération sur les représentations des groupes symétriques. En plus de comprendre ces trois constructions, l'objectif du séminaire est de faire une étude approfondie des certains résultats récents.

Prof. Franco Saliola

MAT995X

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

Combinatoire

L'objectif du cours est de présenter les structures discrètes standards et les principales méthodes d'énumération. Les sujets suivants seront présentés : 

  • Structures discrètes : permutations, dérangements, nombres de Sterling, graphes, partages, diagrammes de Ferrers et tableaux de Young, mots de Dyck, nombres de Catalan, partitions d'ensembles et nombres de Bell, polyominos;
  • Méthodes d'énumération : principe de bijection et d'inclusion-exclusion, récurrences, séries génératrices ordinaires et exponentielles, théorie de Polya, action de groupe, lemme de Burnside, polynômes indicateurs de cycles.

Prof. Alain Goupil

MAP6017

Institution: Université du Québec à Trois-Rivières