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.
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.
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.
É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.
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.
Théorème de Freiman-Ruzsa, transformation de Dyson, théorèmes de Van der Waerden et de Roth-Szemeredi-Gowers.
Le contenu du cours sera en partie précisé suivant les intérêts des étudiants. Les grandes lignes sont les suivantes:
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.
- 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).