Combinatoire et algèbre

Source: Zumthie at de.wikipedia [Public domain], via Wikimedia Commons

Description du programme

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 :

Membres du programme

Formation

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.

Cours 2017-18

Automne

Géométrie et combinatoire

Ensembles partiellement ordonnés (« posets »); complexes simpliciaux associés aux posets; posets associés aux polytopes; treillis (distributifs, modulaires, semimodulaires, géométriques). Propriétés de Sperner; théorèmes de Dilworth et de Greene. Aspects combinatoires de la topologie algébrique (« la  topologie des posets »). Polytopes et la théorie de Ehrhart.

Prof. Franco Saliola

MAT7431-20

Institution: Université du Québec à Montréal

Algèbre

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.

Prof. François Bergeron

MAT 7600-10

Institution: Université du Québec à Montréal

Séminaire en combinatoire: Théorie des séries rationnelles non commutatives

Cette théorie est au carrefour de l'algèbre non commutative et de la théroie des automates finis. 

Séries rationnelles et séries reconnaissables. Théorème de Schützenberger. Représentations linéaires minimales des séries rationneles à coefficients dans un corps. Liens avec la théorie des automates et des langages, théorème de Kleene. Théorie des expressions rationnelles. Liens avec les suites k-régulières et les suites automatiques. Séries rationnelles d'une variable et suites satisfaisant une récurrence linéaire. Extension du semi-anneau de coefficients. Séries rationnelles à coefficients positifs. Algèbres syntaxiques semi-simples. Liens avec le problème de Burnside des matrices et semi-anneau tropical.

Prof. Christophe Reutenauer

995X-10

Institution: Université du Québec à Montréal

Combinatoire

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. 

Prof. Alain Goupil

Institution: Université du Québec à Trois-Rivières

Spectral Graph Theory

Trailer: Graph Theory meets Linear Algebra on the street. Graph Theory says: Let X be a graph. Linear Algebra replies: Great. I’ll associate some matrices to it, and I’ll tell you something about their eigenvalues, maybe I’ll even be able to compute them in lots of cases. Graph Theory squints, and asks: OK, but can you also tell me something about X? Can you help me in difficult problems such as colouring or measuring X? Linear Algebra smiles: I can do that, too. Finite Field Theory and Group Theory, overhearing the exchange, join in: You know what? We’ve got some really interesting X’s lying around, you should take a look.

Description: The aim of this course is to take this silly dialogue seriously. Spectral graph theory is concerned with eigenvalues of matrices associated to graphs, more specifically, with the interplay between spectral properties and graph-theoretic properties. It often feeds on graphs built from groups or finite fields, and this is the direction we will emphasize. In a somewhat larger sense, this course aims to be an introduction to algebraic graph theory. In an even larger sense, this course aims to braid together several strands of interesting mathematics.

The plan is to cover the following topics:

• GRAPHS: notions and invariants (chromatic and independence numbers, diameter and girth, isoperimetric constant); regular graphs (Cayley and bi-Cayley graphs, strongly regular graphs and design graphs).

• FINITE FIELDS: basics (extensions, trace and norm); squares (with quadratic reciprocity as a bonus); character sums (from Gauss to Weil); graphs from finite fields (incidence graphs and Paley graphs).

• EIGENVALUES OF GRAPHS: adjacency and laplacian eigenvalues (basic properties and examples); computations (strongly regular graphs and combinatorial applications; Cayley graphs of abelian groups and character sums); eigenvalues of symmetric matrices (Courant - Fischer variational formulas, Cauchy interlacing, Weyl’s inequality); subgraphs; largest eigenvalues.

• BOUNDS: largest eigenvalues (trees, a spectral Tura ́n theorem); growth of laplacian eigenvalues (and the Alon - Boppana asymptotic threshhold); spectral bounds (for isoperimetric constant, chromatic number, independence number); edge-counting and combinatorial applications.

Prerequisites: A basic familiarity with linear algebra, finite fields, and groups, but not necessarily with graph theory. The course is, however, fairly self-contained and very much accessible to senior undergraduate students.

Grading scheme: 15% attendance and participation + 35% homework + 50 % final exam or written project

Prof. Bogdan Nica

MATH 596

Institution: Université McGill

Hiver

Algèbre homologique

Modules; suites exactes; complexes de chaînes; homologie d'un complexe de chaînes; homologie simpliciale et singulière; cohomologie; formule des coefficients universels; foncteurs Tor et Ext; formule de Künneth; anneau de cohomologie singulière.

Modules; exact sequences; chain complexes; homology of a chain complex; simplicial and singular homology; cohomology; universal coefficient theorems; Tor and Ext functors; the Künneth formula; the ring structure on singular cohomology. 

Prof. Hugh Thomas

MAT7200-10

Institution: Université du Québec à Montréal

Représentation des groupes

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.

Prof. François Bergeron

MAT 7400-10

Institution: Université du Québec à Montréal

Théorie des graphes

Le contenu du cours sera en partie précisé suivant les intérêts des étudiants. Les grandes lignes sont les suivantes :

  • Définitions et résultats de base.
  • Arbres, arborescences.
  • Connexité : théorèmes de Menger et les équivalences entre les résultats de Menger, Dilworth, König, Hall, Ford-Fulkerson (flots).
  • Homomorphismes, colorations.
  • Graphes de Cayley.
  • Théorie extrémale : théorèmes de Turan, de Ramsey.
  • Graphes infinis : théorème de Ramsey, compacité.

Prof. Gena Hahn

MAT 6490

Institution: Université de Montréal