On constate de plus en plus de liens entre l'étude des structures discrètes, d'une part, et les mathématiques classiques, algèbre, analyse, géométrie, théorie des nombres, d'autre part. Il s'agit donc d'exploiter les interactions toujours profondes entre ces domaines en vue d'un enrichissement mutuel de ces spécialités ou, encore, de retombées significatives dans des domaines d'applications variés comme l'informatique, la physique, la géométrie algorithmique, la bioinformatique, la recherche opérationnelle ou la cryptographie.
Les outils modernes de l'informatique font évidemment partie intégrante du programme. En particulier, les logiciels et algorithmes de calcul formel algébrique seront d'utilisation courante et feront même l'objet de développements substantiels au sein du programme.
Les recherches poursuivies par les membres du groupe incluent : la combinatoire énumérative et la combinatoire algébrique, l'algèbre commutative et non commutative, l'informatique théorique, la combinatoire des mots, la bioinformatique.
Les chercheurs du groupe sont affiliés à deux groupes de recherches :
Ce programme s'adresse aux étudiants gradués ayant une solide formation mathématique et voulant se spécialiser en mathématiques discrètes et/ou dans certains aspects de l'informatique théorique. À part les règlements des départements, aucun cours de base n'est obligatoire mais les premiers cours de base en combinatoire, en théorie des graphes et en algorithmique sont fortement recommandés.
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.
Dans ce cours, nous allons examiner plusieurs algorithmes importants dans la combinatoire. Les deux thèmes principaux seront la combinatoire des tableaux de Young et la combinatoire des graphes. Dans la combinatoire des tableaux, nous allons regarder le jeu de taquin et certaines de ses variantes, ainsi que la correspondance de Robinson--Schensted--Knuth. Dans la théorie des graphes, nous allons traiter des problèmes autour des couplages et des flux.
Les groupes de Coxeter joue un rôle fondamental dans plusieurs domaines des mathématiques : ils apparaissent comme groupes de Weyl en théorie de Lie, en théorie de Kazhdan-Lusztig, pour les algèbres amassées ou en géométrie algébrique; ils sont les groupes discrets de réflexions agissant sur les espaces à courbure constante en géométrie et sont primordiales dans la définition des immeubles. L’étude des groupes de Coxeter sont souvent la clef afin de comprendre les structures qui leurs sont associés.
Nous commencerons par couvrir les propriétés de base de ces groupes : conditions d’échange/réduction, théorème de Matsumoto, représentations géométriques et systèmes de racines. Nous utiliserons alors cette théorie pour montrer que tout groupe discret engendré par des réflexions dans un espace euclidien ou hyperbolique est un groupe de Coxeter.
Nous discuterons ensuite les liens entre les systèmes de racines, l’ordre faible, l’ordre de Bruhat et le graphe de Cayley munit de sa métrique géodésique. On conclura cette partie par montrer que tout groupe de Coxeter est automatique.
La dernière partie du cours sera dédié à des développements récents de la recherche sur le sujet. En particulier, on mettra en lumière les structures d’ombres de Garside, d’arrangements de Shi et leurs liens avec la récente preuve de la biautomaticité des groupes de Coxeter et le problème des mots dans les groupes d’Artin-Tits.
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.