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.

2019-20 Course Listings

Fall

Honours Linear Optimization

Honours level introduction to linear optimization and its applications: duality theory, fundamental theorem, sensitivity analysis, convexity, simplex algorithm, interior point methods, quadratic optimization, applications in game theory.

Prof. Tim Hoheisel

MATH 517

Institution: McGill University

Algorithmic Game Theory

Foundations of game theory. Computation aspects of equilibria. Theory of auctions and modern auction design. General equilibrium theory and welfare economics. Algorithmic mechanism design. Dynamic games.

Prof. Adrian Vetta

MATH 553

Institution: McGill University

Combinatoire 2

Étude approfondie des séries génératrices en combinatoire. Caractérisation des séries rationnelles algébriques. D-finies. Séries associées aux espèces de structures: séries génératrices et séries indicatrices, théorèmes de substitution. Application au dénombrement de types de structures et de structures asymétriques. Théorème de dissymétrie pour les arbres. Décompositions moléculaire et atomique d'une espèce. Foncteurs analytiques. Liens avec les fonctions symétriques et les représentations linéaires du groupe symétrique.

Prof. François Bergeron

MAT 9351

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

Séminaire de combinatoire: Plane Partitions

This course is intended as an introduction to the theory of plane partitions and related combinatorial objects. It will cover an historical introduction to this topic, connections to other combinatorial objects, symmetric functions and representation theory as well as the "mysterious connection" to alternating sign matrices (ASMs). Further relevant topics are perfect matchings, Kuo's condensation, lozenge tilings, nonintersecting lattice paths, the Lindström-Gessel-Viennot Theorem, the condensation method for determinant evaluation and RSK-like bijections. More advanced topics could include poset partitions, connections to statistical physics including vertex models, shifted plane partitions, and a detailed elaboration of symmetry classes of plane partitions and their relation to ASMs.

Prof. Hugh Thomas

MAT 995C

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

Winter

Combinatoire additive

Théorème de Freiman-Ruzsa, transformation de Dyson, théorèmes de Van der Waerden et de Roth-Szemeredi-Gowers.

Prof. Andrew Granville

MAT 6657

Institution: Université de Montréal

Optimization

Prof.

MATH 560

Institution: McGill University

Introduction à la théorie des graphes

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 : théorème de Ramsey, compacité.

Prof. Gena Hahn

MAT 6490

Institution: Université de Montréal

Représentation des groupes

La théorie de la représentation des groupes et une théorie algébrique dont les ramifications s’étendent à de très nombreux domaines des mathématiques ainsi qu’à la Physique te à la Chimie. L’apprentissage de cette théorie permettra entre autre à l’étudiant d’appréhender d’autres théories algébriques de la représentation.

Descripteur : Représentations linéraires des groupes finis. Sous-représentations, théorème de Mashke; représentations irréductibles. Théorie des caractères. Décomposition en composantes isotypiques. Produits tensoriels; représentation induites. Représentations linéaires des groupes compacts. Exemples: groupes cycliques, diédraux, symétriques: tores, groupes de rotations.

Prof. François Bergeron

MAT 7400

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

Algorithmes en combinatoire

- Groupes de permutations: orbite et stabilisateur d'un élément; théorème de Schreier; certaines applications: ordre d'un groupe de permutations; test d'appartenance; forme normale pour les éléments du groupe. Algorithme de Todd-Coxeter pour l'énumération des classes à gauches d'un sous-groupe.

- Bases de Gröbner: bases de Gröbner d'un idéal d'un anneau de polynômes; unicité de la base de Gröbner réduite; applications: égalités d'idéaux; calcul d'intersection d'idéaux; correspondance entre idéaux et ensembles algébrique.

- Permutations et Tableaux: l'algorithme de Robinson-Schensted-Knuth (RSK); ombres de Viennot; jeu de taquin de Schützenberger; évacuation.

- Algorithme X de Knuth: algorithme récursif de parcours en profondeur et à retour sur trace; applications: problème de couverture exacte; Sudoku.

- Algorithmes sur les graphes: arbres étiquetés (code de Prüfer, bijections de Foata et de Joyal, formule de Cayley); arbres couvrants de poids minimal (théorème de Kirchhoff, algorithmes de Prim et de Kruskal); problème du plus court chemin (algorithme de Dijkstra); problème des mariages stables (théorème de Hall, algorithme de Gale-Shapley).

Prof. Franco Saliola

MAT7441

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