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.

2024-25 Course Listings

Fall

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. Alejandro Morales

MAT 9351

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

Sujets choisis en algèbre

Représentations de carquois, algèbres de dimension finie, systèmes de racines, théorème de Gabriel sur les carquois de représentation finie.

Prof. Thomas Brüstle

MAT728

Institution: Université de Sherbrooke

Winter

Algorithmes en combinatoire

In this course, we will examine a number of important algorithms arising in combinatorics. The two main themes will be tableau combinatorics and combinatorics of graphs. In the setting of tableau combinatorics, we will look at jeu de taquin and some of its variants, and the Robinson--Schensted--Knuth correspondence. In our study of graph theory, we will look at problems around matchings and flows in graphs.

Prof. Hugh Thomas

MAT7441

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

Combinatorics Seminar: Geometry and combinatorics of Coxeter groups

Coxeter groups play a fundamental role in several areas of mathematics: they occur as Weyl groups in Lie theory, Kazhdan-Lusztig theory, for Cluster algebras or in algebraic geometry; they are the discrete reflection groups acting on spaces of constant curvature in geometry and they are fundamental to define buildings in geometric group theory. Properties of these groups are often key to a deep understanding of the main relevant structures for these areas.

We will start by covering the basics of Coxeter group theory: exchange/deletion conditions, Matsumoto theorem, geometric representations and root systems. We will apply the theory to show that any discrete group generated by reflections in spherical, Euclidean or hyperbolic geometry is a Coxeter group.

Then we will be discussing the interplay between root systems, the weak order, the Bruhat order and the Cayley graph with its word-metric. We will end this part by showing that Coxeter groups are automatic (Brink-Howlett theorem).

The final part of this class will be dedicated to current research developments. In particular, we will be focusing our attention on Garside shadows, Shi arrangements and their relationship with the (still open) word problem in Artin-Tits (braid) groups and the bi-automaticity of Coxeter groups.

Bibliography (selected)

Books

  • A. Björner and F. Brenti, Combinatorics of Coxeter groups, Graduate texts in Mathematics 231, Springer (2005)
  • P. Abramenko and K. S. Brown, Buildings: Theory and Applications. Graduate Texts in Mathematics, Vol. 248. Springer, New York, (2008).
  • J. E. Humphreys, Reflection groups and Coxeter groups, Cambridge studies in advances mathematics 29, Cambridge University press (1990)

Articles

  • M. Dyer, C. Hohlweg, Small roots, low elements, and the weak order in Coxeter groups, Advances in Math. 301 (2016), 739-784.
  • M. Dyer, S. Fishel, C. Hohlweg, A. Mark, Shi arrangements and low elements in Coxeter groups, arXiv:2303.16569 (2023).

 

Bibliography (Extended)

  • J. G. Ratcliffe, Foundations of Hyperbolic Manifolds, 2nd edition, Graduat text in math. 149 (2006) – Chapters 6 & 7
  • E. B. Vinberg, O. V. Shvartsman, Discrete groups of Motions of Spaces of Constant Curvature, in Geometry II: Spaces of Constant Curvature, 139-248, (1993).
  • P. Dehornoy, M. Dyer and C. Hohlweg, Garside families in Artin-Tits monoids and low elements in Coxeter groups, Comptes Rendus Mathematique, 353, 403-408 (2015).
  • C. Hohlweg, P. Nadeau, N. Williams, Automata, reduced words, and Garside shadows in Coxeter groups, Journal of algebra, vol. 457 (2016), 431-456.
  • D. Osajda, P. Przytyki, Coxeter groups are bi-automatic, arXiv:2206.07804 (2022)

Prof. Christophe Hohlweg

MAT995

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

Combinatoire (UQTR)

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