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 afficilated 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.
Algorithmic and structural approaches in combinatorial optimization with a focus upon theory and applications. Topics include: polyhedral methods, network optimization, the ellipsoid method, graph algorithms, matroid theory and submodular functions.
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.
É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.
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.
Convex sets and functions, subdifferential calculus, conjugate functions, Fenchel duality, proximal calculus. Subgradient methods, proximal-based methods. Conditional gradient method, ADMM. Applications including data classification, network-flow problems, image processing, convex feasibility problems, DC optimization, sparse optimization, and compressed sensing.
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.
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.
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
Articles
Bibliography (Extended)
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.