Source: Zumthie at de.wikipedia [Public domain], via Wikimedia Commons
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 affiliated with two research groups:
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.
É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.
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 Shi arrangements and their relation to the proof of the bi-automaticity of Coxeter groups (Osajda-Przytycki theorem).
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.
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.
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 :