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.
Représentations et module d'un groupe G, représentations équivalentes, sous-module. Représentations indécomposable, réductible, irréductible. Théorème de Maschke. Morphisme, lemme de Schur.
Algèbre de groupe, fonctions sur cette algèbre, fonction de classe. Caractères, relations d'orthogonalité, tables de caractères. Représentation régulière. Analyse de Fourier sur les groupes finis, identité de Parseval, théorème de Wedderburn.
Nombres algébriques, théorème de la dimension, théorème de Burnside. Action de groupe, lemme de Burnside, paires de Gelfand.
Représentations induites, théorème de réciprocité de Frobenius, critère d'irréductibilité de Mackey.
Marche aléatoire sur les groupes finis. Modèles de Gilbert–Shannon–Reeds, théorèmes de Diaconis.
Ce cours sert comme introduction au niveau des cycles supérieurs à la combinatoire algébrique et énumérative, avec une emphase sur les méthodes efficaces. Les sujets de base comprendront les séries formelles ordinaires et exponentielles, les objets classiques de la combinatoire (partages, chemins dans un réseau, graphes, permutations), méthodes asymptotiques, suites vérifiant des récurrences linéaires, et l'occurrence et le comportement des séries rationnelles, algébriques, et D-finies. Dépendant des intérêts des étudiants, on pourrait aussi regarder les séries formelles à plusieurs variables, l'application des logiciels pour la combinatoire, démonstrations algorithmique de transcendence des constants, questions de calculabilité et complexité dans l'énumération, et les liens avec les langues formelles
This course serves as a graduate introduction to enumerative and algebraic combinatorics, with a focus on effective methods. Our core topics include ordinary and exponential generating functions, classical combinatorics objects (partitions, lattice paths, graphs, permutations), asymptotic methods, sequences satisfying linear recurrence relations, and the occurrence and behaviour of rational, algebraic, and D-finite functions. Depending on student interest, more advanced topics could include multivariate generating functions, computer algebra tools for combinatorics, algorithmic transcendence of constants vs generating functions, computability and complexity questions in enumeration, and connections to formal languages.
Compléments sur la théorie des groupes:
- actions de groupes ; orbites ; stabilisateurs
- calcul dans les groupes de permutations:
- orbite et stabilisateur d'un élément;
- système de représentants du stabilisateur d'un élément;
- ordre d'un groupe de permutations;
- test d'appartenance à groupe de permutations;
- forme normale des éléments;
- algorithme de Todd-Coxeter.
Théorie des catégories:
- définition et exemples des catégories;
- foncteurs;
- transformations naturelles;
- propriétés universelles;
- (co)produits, produit fibré et somme amalgamée;
- équivalence des catégories.
Théorie des modules:
- modules artiniens et noethériens;
- modules simples, semisimples, indécomposables;
- théorèmes de Jordan-Holder, Krull-Schmidt et Artin-Wedderburn;
- notion de dimension d'un module;
- produit tensoriel de modules.
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.
Ergodic theory studies actions of countable (semi)groups on a measure space (typically, probability space), while measured group theory studies countable groups by studying their actions on probability spaces, so the two subjects are closely tied but their paradigms are different. The course will introduce these subjects and cover select topics from them. Besides the topics themselves, the main goal of the course is to instill the vision and methods that descriptive set theory offers to the study of measurable actions of countable groups by reducing statements about them to graph combinatorics. The interaction of descriptive set theory and various other subjects has been a fruitful and rapidly expanding area of research in the past 30 years and this course will give a glimpse of it. As an example, in half a lecture, we will learn a new combinatorial proof of the classical pointwise ergodic theorem using nothing but definitions.
A tentative list of topics from ergodic theory includes ergodicity and pointwise ergodic theorems, various notions of mixing, entropy and the classification of dynamical systems up to isomorphism; while in measured group theory, we will learn the orbit equivalence (OE) of group actions and classification of actions up to OE, the notion of cost, and we will prove D. Gaboriau's fundamental theorem of cost, which allows to distinguish actions up to OE.
Partially ordered sets, linear extensions, lattices, and associated simplicial complexes. Sperner properties; theorems of Dilworth and Greene. Combinatorial aspects of algebraic topology. Hyperplane arrangements.
Le séminaire portera provisoirement sur le "pléthysme", ce qui peut être défini comme une opération sur les fonctions symétriques ; comme une opération sur les représentations des groupes linéaires GL(n) ; ou comme une opération sur les représentations des groupes symétriques. En plus de comprendre ces trois constructions, l'objectif du séminaire est de faire une étude approfondie des certains résultats récents.
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 :