Laboratoire
d'Algèbre
, deCombinatoire
et d’Informatique
Mathématique
Le Séminaire du LACIM, créé au début des années 80, a lieu chaque semaine de septembre à juin (et parfois l’été) les vendredis de 11h à midi au Pavillon Président-Kennedy de l’UQAM (PK-4323).
Organisateurs
We will generalize many facts about the weak order on a finite Coxeter group to the extended weak order on an affine Weyl group. Whereas the weak order is the poset of regions in the Coxeter arrangement, the extended weak order is the poset of quasiregions. Quasiregions include regions, but for infinite Coxeter group they also include more exotic objects (equivalent to biclosed sets of positive roots).
For instance, in type $\widetilde{A}$, quasiregions are equivalent to translation-invariant total orderings of the integers (TITOs). In type $\widetilde{A}$, the extended weak order is a lattice, while the weak order is not. We show that, in this case, the extended weak order is a lattice quotient of the lattice of torsion classes for a type $\widetilde{A}$ preprojective algebra. We also introduce the affine Tamari lattice, which is the poset of $312$-avoiding TITOs, and show how it describes a cluster algebra for the oriented cycle quiver.
TBA
TBA
The Temperley—Lieb algebra is a classical mathematical object studied in algebra, combinatorics, statistical mechanics and mathematical physics, introduced by Temperley and Lieb in 1971.
For any Coxeter system, it is possible to define the so-called generalized Temperley—Lieb algebras as quotients of the associated Hecke algebras. Moreover, beginning with the work of Kauffman and Penrose, it was shown that most Temperley—Lieb algebras can be realized as diagram algebras, which are associative algebras with a basis given by certain diagrams on the plane.
In this talk, I will introduce a diagrammatic representation for the Temperley—Lieb algebra of type affine D, obtained using particular decorated diagrams. I will also describe some of the combinatorial strategies used to prove the faithfulness of this representation.
Configuration graphs are "meta-graphs" where vertices are solutions of a problem and two solutions are linked by an edge if one can be transformed into the other into a "canonical" step. These questions naturally arise in many fields from discrete geometry to combinatorial optimization.
The goal of this introductory talk is to present (some of) these problems and their motivations, discuss some recent results on the topic and mention some open problems in the area.
As classes of GFs go, we tend to know more about smaller classes than larger ones, think of the progression from rational to algebraic to D-finite to D-algebraic GFs. The positivity adds another twist on these classes, bringing a host of new problems. In this talk, I will review some classes of GFs that are of interest in Enumerative Combinatorics but remain understudied, emphasising both larger classes and positivity properties.
Quivers and their mutations play a fundamental role in the theory of cluster algebras. We focus on the problem of deciding whether two given quivers are mutation equivalent to each other. Our approach is based on introducing an additional structure of a cyclic ordering on the set of vertices of a quiver. This leads to new powerful invariants of quiver mutation. These invariants can be used to show that various quivers are not mutation acyclic, i.e., they are not mutation equivalent to an acyclic quiver. This talk is partially based on joint work with Sergey Fomin [arXiv:2406.03604]
Persistence theory was born from the observation that the critical values of a Morse function admit a canonical pairing, which induces a direct sum decomposition of the sublevel set homology of the function into interval poset representations. What makes persistence theory distinct from Morse theory - besides the fact that it is usually framed using the language of representation theory - is its focus on perturbation-stability, providing answers to questions such as: How can the critical values of a Morse function change when the function is perturbed? The initial motivation for the study of perturbation-stability came from problems in geometric data science, but has since found applications in symplectic geometry as well as in complex and functional analysis. I will give an overview of the representation theoretic and combinatorial aspects of persistence theory, including motivation and applications.
Crepant resolutions have inspired connections between birational geometry, derived categories, representation theory, and motivic integration. In this talk, we prove that every variety with log-terminal singularities admits a crepant resolution by a smooth stack. We additionally prove a motivic McKay correspondence for stack-theoretic resolutions. Finally, we show how our work naturally leads to a generalization of twisted mapping spaces. This is joint work with Jeremy Usatine.
Dans cet exposé, on s'attaque à un sous-problème de l'énumeration des polyominos qui est un problème étudié depuis son introduction par Goulomb. On énumère les polyominos qui sont inscrits dans un rectangle d'une certaine taille. Si on fixe la base $b$ et varie la hauteur, le nombre de polyominos inscrits dans ces rectangles suit une récurrence linéaire. L'objectif est de construire des automates qui reconnaissent ces polyominos pour obtenir les séries génératrice. En adaptant des méthodes décrites dans des travaux de Zeilberger et de Bousquet-Mélou et Brak, on développe une construction systématique de ces automates pour chaque valeur de $b$.
For a field \(k\), algebraic \(k\)-tori are algebraic \(k\)-groups which become isomorphic to a split \(k\)-torus, after base change to the separable closure of \(k\). The possible algebraic \(k\)-tori of dimension n are classified up to isomorphism by finite subgroups of \(GL(n,Z)\) up to conjugacy and hence by integral representations of finite groups. Work of Demazure, Voskresenskii and Klyachko, among others, established, in principle, the existence of a smooth projective model of an algebraic \(k\)-torus which was used to determine its birational properties. Kunyavskii’s birational classification of algebraic \(k\)-tori in dimension \(3\) involved constructions of smooth projective toric models of the algebraic tori corresponding to maximal finite subgroups of \(GL(3,Z)\). We discuss some explicit constructions of toric models of algebraic tori, making connections with the defining integral representations of their splitting groups. The constructions determine smooth projective toric models of the algebraic tori corresponding to maximal finite subgroups of \(GL(4,Z)\). Since projective toric varieties are determined by lattice polytopes, our constructions focus on some highly symmetric families of polytopes, such as root polytopes and duals of central transportation polytopes.
The faces of the braid arrangement form a monoid. The associated monoid algebra -- the face algebra -- is well-studied, especially in relation to Markov chains. In this talk, we explore the action of the symmetric group on the face algebra from the perspective of invariant theory. Bidigare proved the invariant subalgebra of the face algebra is (anti)isomorphic to Solomon's descent algebra. We answer the more general question: what is the structure of the face algebra as a simultaneous representation of the symmetric group and Solomon's descent algebra? A key tool in answering this question is the poset topology of the partition lattice. We will say a bit about how poset topology can be applied to a more general setting: groups acting on left regular band algebras.
The Schur algebra is a finite dimensional algebra that connects the representation theory of symmetric and general linear groups. In joint work with Tom Braden we introduce new algebra that enhances the Schur algebra and provides a new window into the representation theory of symmetric groups. I will give a conceptual and a diagrammatic description of this new “Hilbert Schur algebra" and discuss some of its combinatorial structure.
Dans le cadre de l’étude des mots trapézoïdaux, dont la séquence de la cardinalité des facteurs est symétrique, on introduit une variance bivariée qui reflète cette symétrie dans l’image commutative des facteurs, caractérisant ainsi, sous certaines hypothèses, les mots de Christoffel. Bien que le cas primitif soit contraint aux mots sturmiens, le cas non-primitif se départie de cette hypothèse et, ce faisant, caractérise parfaitement les mots de Christoffel.
We show a skewing relation holds between the symmetric functions involved in the Rational Shuffle Conjecture and those of the Delta Conjecture, and use it to derive a geometric interpretation for the Delta polynomials in terms of the Borel-Moore homology of certain affine Springer fibers. Our geometric work simultaneously generalizes that of Hikita and Borho--Macpherson from two special cases, and our algebraic proof of the skewing relation relies on the new work of Blasiak, Haiman, Morse, Pun, and Seelinger that resolved the "Rise" half of the Delta Conjecture. We also note some progress towards a purely combinatorial proof of the relation. This is joint work with Sean Griffin and Eugene Gorsky.
Cet exposé revisite, une fois encore, le problème du calcul d'un automate fini à partir d'une expression rationnelle (régulière), un sujet qui est l'objet de nombreux travaux, et depuis longtemps.
Le point de départ est ce que j'appelle l'automate des termes dérivés, connu aussi comme l'automate des dérivées partielles, ou automate d'Antimirov, obtenu par une modification, simple mais essentielle, due à Antimirov, de la dérivation définie par Brzozowski et qui donne l'automate des 'derivatives'.
En prenant un point de vue légèrement décalé, on présente une construction de cet automate fondée sur une induction sur la profondeur de l'expression, sans référence aucune à une opération de dérivation de l'expression ni au quotient des langages.
Ce changement de perspective a été motivé par la généralisation de la construction aux expressions avec multiplicités, et permet d'élargir son champ d'application aux expressions sur des monoïdes non libres, comme les produits directs de monoïdes libres et donc aux relations rationnelles.
Travail commun avec Sylvain Lombardy (Labri, U. Bordeaux)
Unicellular LLT polynomials are closely related to the chromatic quasi-symmetric functions of incomparability graphs of unit interval orders via a plethystic substitution. Coefficients arising in various expansions of these chromatic quasi-symmetric functions are known to be evaluations of Hecke algebra traces of Kazhdan–Lusztig elements. We view coefficients of the same expansions of unicellular LLT polynomials as evaluations of different plethystically defined traces at Kazhdan–Lusztig basis elements, and express these in terms of traditional trace bases. We also describe these new traces in terms of induction and Kazhdan–Lusztig R-polynomials. Based on joint work with Mark Skandera and Alejandro Morales.
Lorentzian polynomials were developed about 5 years ago by Brändén-Huh and Anari-Liu-Oveis Gharan-Vinzant to provide a unifying approach to various log-concavity statements (in particular, Mason’s conjectures). A line of research which has utilized this and related polynomial classes is that of the polynomial capacity method, which was developed by Gurvits about 20 years ago to bound and approximate the permanent of a matrix (among many other things). In this talk, we will describe this method and discuss a few of its applications; in particular, counting/approximating bipartite perfect matchings and counting/approximating lattice points of transportation and flow polytopes. If time permits, we will also briefly mention the most recent application to the analysis of the traveling salesperson problem. Joint work with various subsets of Petter Brändén, Leonid Gurvits, Nathan Klein, Alejandro Morales, and Igor Pak.
In this talk, I will discuss connections between configuration spaces, an important class of topological space, and combinatorial algebras arising from the theory of reflection groups. In particular, I will present work relating the cohomology rings of some classical configuration spaces—such as the space of n ordered points in Euclidean space—with Solomon’s descent algebra and the peak algebra.
The talk will be centered around two questions. First, how are these objects related? Second, how can studying one inform the other? This is joint, on-going work with Marcelo Aguiar and Vic Reiner.
La théorie algorithmique des graphes emploie fréquemment le paradigme de Diviser-pour-Régner, remplaçant un graphe donné par des graphes plus petits afin de construire une solution à un problème spécifique. Pour cette présentation on s’intéresse au problème des transversaux de circuits (en anglais feedback vertex set). En particulier, on explore des réductions de graphes en temps polynomial, qui maintiennent certaines propriétés du problème des transversaux de circuits de cardinalité minimale. On se concentre sur la propriété de Church-Rosser, également appelée confluence. Si la propriété de Church-Rosser est vérifiée, l’ordre d’application des réductions dans une collection de réductions n’a pas d’importance et le graphe résultant est unique à isomorphisme près. On propose une clarification et une généralisation de certaines réductions trouvées dans la littérature. Notre étude a des implications algorithmiques, car elle peut conduire à la parallélisation des algorithmes et à la réduction des temps d’exécution des algorithmes séquentiels.
For fixed n, consider the symmetric group S_n on the symbols 1,…,n and the set of *star* transpositions, the transpositions that contain the symbol n. A *star factorization* of a permutation b in S_n of length k is the writing of b as the product of k star transpositions. Goulden and Jackson (2009) showed that the number of such factorizations only depends on the conjugacy class of b and not on b itself, a remarkable fact given the special role the symbol n plays amongst star transpositions. We supply the first fully combinatorial proof of this fact that works for all lengths k, and our methods connect star factorizations to monotone factorizations. Star transpositions are connected to Jucys-Murphy elements, and we explain how our result can give expressions for the *transitive* image of certain symmetric functions evaluated at Jucys-Murphy elements. This is joint work with Jesse Campion Loth (Heilbronn Institute and the University of Bristol).
La correspondance de Robinson-Schensted-Knuth est une bijection partant des matrices d’entiers naturels vers les paires de tableaux de Young semi-standards. Une version généralisée donne une bijection entre des remplissages d’un tableau d’une certaine forme, et les partitions planes renversés de la même forme. D’un point de vue « représentation de carquois », la correspondance RSK donne une bijection entre deux invariants particuliers d’un module X (dans une certaine catégorie). Les entrées d’un remplissage arbitraire correspondent aux multiplicités des facteurs indécomposables de X, tandis que les entrées de la partition plane renversée enregistrent la donnée générique de Jordan de X, un invariant introduit par Alexander Garver, Rebecca Patrias et Hugh Thomas. Mon exposé a pour but de présenter une version un peu plus générale de cette correspondance, en y incluant une interaction avec un choix arbitraire d’une orientation d’un carquois de type A, correspondant à un choix d’un élément de Coxeter dans Sn. Pour cet exposé, aucune grande connaissance de la théorie des représentations de carquois ne sera nécessaire. Si le temps le permet, je discuterai un peu plus du résultat algébrique dont est tiré ce travail. C’est une extraction combinatoire (en cours) de mes travaux de thèse, encadré par Hugh Thomas.
Gaetz and Gao recently proved the strong Sperner property for weak order by extending a rank-lowering operator N (Nabla), first introduced by Stanley, to an sl(2) poset representation. This was done by explicitly constructing the corresponding raising operator D (Delta). Hamaker, Pechenik, Speyer, and Weigandt later showed that N (and hence D) can be realized certain differential operators acting on Schubert polynomials. We outline new bijective proofs of these derivative identities for Schubert polynomials using the combinatorics of pipe dreams. These proofs extend to give related identities for beta-Grothendieck polynomials.
Ce travail est motivé par l'étude d'un anneau de coinvariants du groupe symétrique, avec un jeu de variables commutatives et deux jeux de variables anticommutatives. Sa caractéristique de Frobenius, une fonction symétrique encodant le type d'isomorphisme de la représentation, est conjecturée être donnée par l'expression $SF(n,k,l)=\left.\Theta_{e_k}\Theta_{e_l}\nabla e_{n-k-l}\right|_{t=0}$ pour des degrés anticommutatifs k,l.Dans cet exposé, je vais décrire une expression combinatoire de cette fonction symétrique $SF(n,k,l)$ en termes de mots de Smirnov, qui sont les mots sur les entiers dont les lettres consécutives sont distinctes. J'expliquerai aussi en quoi ce résultat constitue un pas vers une version unifiée des "conjectures Delta". C'est un travail commun avec Alessandro Iraci et Anna Vanden Wyngaerd.
Dans les années 80, Hansel et Perrin, poursuivant les travaux de Schützenberger, se penchent sur la notion de densité naturelle des langages. Dans leur étude, la densité est calculée relativement à une mesure de Bernoulli, mesure définie sur le monoïde libre par morphisme. Les travaux que je présenterai portent sur les densités naturelles calculées relativement aux mesures ergodiques d'espaces symboliques. Dans ce contexte, la densité permet de mesurer la présence (ou absence) d'une propriété rationnelle à l'intérieur d'un espace symbolique donné. J'expliquerai quand est comment il est possible de calculer ces densités, plus particulièrement pour les langages à groupes, langages ayant pour monoïdes syntaxiques des groupes finis. Sous des conditions qui dépendent à la fois de l'espace symbolique, du langage et de son groupe syntaxique, la densité est réduite à une formule simple. Cette réduction fait intervenir des notions de théorie ergodique, de combinatoire des mots et de dynamique symbolique.En collaboration avec : Valérie Berthé, Carl-Fredrik Nyberg Brodda, Dominique Perrin et Karl Petersen.
en collaboration avec Jeanne Scott
Il est bien connu que le treillis de Young peut s'interpréter comme le diagramme de Bratelli des groupes symétriques, décrivant, par exemple, comment les représentations irréductibles se restreignent de Sn à S_n-1. En 1975, Stanley a découvert un treillis similaire appelé treillis de Young-Fibonacci qui a été interprété comme le diagramme de Bratelli d'une famille d'algèbres par Okada en 1994.
Dans cet exposé, nous réalisons l'algèbre d'Okada et son monoïde associé grâce à une version étiquetée des diagrammes d'arcs du monoïde de Jones et de l'algèbre de Tempeley-Lieb. Ceux-ci nous permettent de prouver en toute généralité que l'algèbre d'Okada est de dimension n! — la preuve d'Okada n'étant valide que dans le cas semi-simple. En particulier, nous interprétons la bijection naturelle entre les permutations et les diagrammes d'arcs comme une instance de la correspondance de Robinson-Schensted-Fomin associée au treillis de Young-Fibonacci. Disposant maintenant d'un moyen de calculer dans les monoïdes et algèbres d'Okada, nous pouvons étudier en détail leurs structures et par exemple prouver que le monoïde est apériodique et décrire ses relations de Green. En relevant, ces dernières à l'algèbre nous en construisant une base cellulaire.
Algebraic Combinatorics studies objects and quantities originating in Algebra, Representation Theory and Algebraic Geometry via combinatorial methods, finding formulas and neat interpretations. Some of its feats include the hook-length formula for the dimension of an irreducible symmetric group (S_n) module, or the Littlewood-Richardson rule to determine multiplicities of GL irreducibles in tensor products. Yet some natural multiplicities elude us, among them the Kronecker coefficients for the decomposition of tensor products of S_n irreducibles, and the plethysm coefficients for compositions of GL modules. Answering those questions could help Geometric Complexity Theory establish lower bounds for the far reaching goal to show that P \neq NP. We will discuss how Computational Complexity Theory provides a theoretical framework for understanding what kind of formulas or rules we could actually have. We will use this to show that the square of a symmetric group character could not have a combinatorial interpretation. Based on joint works with Christian Ikenmeyer and Igor Pak.
Schubert polynomials are distinguished representatives of Schubert cells in the cohomology of the flag variety. Pipedreams (PD) and bumpless pipedreams (BPD) are two combinatorial models of Schubert polynomials. There are many classical perspectives to view PDs: Fomin and Stanley represented each PD as an element in the NilCoexter algebra; Lenart and Sottile converted each PD into a labeled chain in the Bruhat order. In this talk, we unravel the BPD analogues of both viewpoints. One application of our results is a simple bijection between PDs and BPDs via Lenart’s growth diagram.
We present a generalization of the toggle group, when thought of as a proper edge coloring of the Hasse diagram of the associated poset that we call the coloring group. Beyond general structure results, we focus on the case where the associated graph is a tree. This talk is based on joint work with Jonathan Bloom and Alexander Wilson.
The SL(3) web basis is a special basis of certain spaces of tensor invariants developed in the late 90’s by Kuperberg as a tool for computing quantum link invariants. Since then this basis has found connections and applications to cluster algebras, dimer models, quantum topology, and tableau combinatorics. A main open problem has remained: how to find a basis replicating the desirable properties of this basis for SL(4) and beyond? I will describe joint work with Oliver Pechenik, Stephan Pfannerer, Jessica Striker, and Josh Swanson in which we construct such a basis for SL(4). Modified versions of plabic graphs and the six-vertex model and new tableau combinatorics will appear along the way.
Les cartes sont de formes très variables : arbres, triangulations ou encore cartes avec beaucoup plus d'arêtes. De nombreuses classes de cartes ont été énumérées (cartes $2$-connexes, arbres, quadrangulations...), notamment par Tutte, et un phénomène d'universalité a été démontré : pour la majorité d'entre elles, le nombre d'éléments de taille $n$ dans la classe a une asymptotique de la forme $\kappa \rho^{-n} n^{-5/2}$, pour un certain $\kappa$ et un certain $\rho$. Néanmoins, il existe des classes de cartes "dégénérées" dont le comportement est similaire à celui des arbres, et dont le nombre d'éléments de taille $n$ a une asymptote de la forme $\kappa \rho^{-n} n^{-3/2}$, comme par exemple les cartes “outerplanar". Cette dichotomie de comportement est observée non seulement pour le dénombrement, mais aussi d’un point de vue métrique. En effet, dans le cas "arbre", la distance entre deux sommets aléatoires est de $\sqrt{n}$, contre $n^{1/4}$ pour les cartes planaires uniformes de taille $n$. Ce travail se concentre sur ce qui se passe entre ces deux régimes très différents. Nous étudions un modèle dépendant d'un paramètre $u>0$ qui présente les comportements précédents, et une transition entre les deux : selon la position de $u$ par rapport à $u_C$, le comportement est celui de l'une ou l'autre classe d'universalité. Plus précisément, nous observons un régime "sous-critique" où la limite d'échelle des cartes est la carte brownienne, un régime "supercritique" où c'est l'arbre brownien et enfin un régime critique où c'est l'arbre $3/2$-stable. Les résultats sont obtenus à l'aide d'une méthode robuste, qui peut être utilisée pour étudier une variété de modèles similaires.
The chromatic symmetric function, introduced by Stanley, is a well-studied generalization of the chromatic polynomial of a graph. Chromatic symmetric functions of (3+1)-free incomparability graphs (in particular, incomparability graphs of unit interval orders) are of particular interest. Motivated by the Stanley-Stembridge conjecture that such chromatic functions are e-positive, we show that the allowable coloring weights for such a graph are the lattice points of a permutahedron, and give a formula for the dominant coloring weight. We also give conjectures about convexity properties of these symmetric functions, and prove that they are Lorentzian in the abelian case.
The Pitman-Stanley polytope is a polytope whose integer lattice points biject onto the set of plane partitions of a certain shape with entries in $\{ 0 , 1 \}$. In their original paper, Pitman and Stanley further suggest a generalization of their construction depending on m in N whose integer lattice points biject onto the set of plane partitions of the same shape having entries in $\{ 0 , 1, \dots , m \}$. In this talk, we give further details of this generalized Pitman-Stanley polytope, $PS_n^m(a)$, demonstrating that it can be realized as the flow polytope of a certain graph. We then use the theory of flow polytopes to describe the faces of these polytopes and produce a recurrence for their f-vectors. This is joint work with Maura Hegarty, Alejandro H. Morales, and Annie Raymond.
Au cours des dernières décennies, les configurations de Catalan et les fonctionnements de stationnement ont vu une succession de généralisations de plus en plus englobantes. Cette évolution est en lien direct avec un nombre grandissant d’interactions avec d’autres domaines comme: la théorie de la représentation, la géométrie algébrique, la théorie des nœuds, ou la physique théorique. Nous allons décrire comment on peut classer les généralisations en question en termes de familles de partages. L’une des plus riches de ces familles est celle de partages triangulaires. Nous allons en discuter quelques propriétés, et montrer en quoi certaines questions deviennent plus naturelles dans ce contexte.
We introduce projective schemes that are analogues of the James reduced product construction from homotopy theory and begin to develop a Schubert calculus for such spaces. This machinery yields K-theoretic and T-equivariant analogues of classic quasisymmetric function theory. Based on joint works with Matt Satriano.
Ceballos et Pons ont introduit l'ordre s-faible sur les arbres s-décroissants, pour toute composition s faible. Ils ont prouvé qu'il avait une structure en treillis et ont conjecturé qu'il pouvait être réalisé comme le 1-squelette d'une subdivision polyédrique d'un polytope. Nous répondons à leur conjecture dans le cas où s est une composition stricte en fournissant trois réalisations géométriques du s-permutoèdre. La première est comme le graphe dual d'une triangulation d'un polytope de flot de grande dimension. La seconde, obtenue grâce à l'astuce de Cayley, est le graphe dual d'une fine subdivision mixte d'une somme d'hypercubes qui a la dimension conjecturée. La troisième, obtenue par géométrie tropicale, est le 1-squelette d'un complexe polyédrique pour lequel on peut fournir des coordonnées explicites des sommets et dont le support est un permutoèdre comme conjecturé.Cet exposé est basé sur un travail conjoint avec Rafael González D’León, Eva Philippe, Daniel Tamayo Jiménez et Martha Yip.
Une algèbre de Hopf combinatoire est une bigèbre graduée qui formalise les opérations d’assemblage et de désassemblage d’objets combinatoires. Nous verrons différents exemples simples. Certaines de ces algèbres peuvent être définies de façon équivalente comme les invariants sous une action du groupe symétrique. C’est le cas par exemple de Sym, QSym, WSym, WQSym, NCSF.
Généralisant l’action quasi-symétrisante, Hivert a obtenu en 2004 une interpolation infinie d’algèbres de Hopf entre les fonctions symétriques Sym et les fonctions quasi-symétriques QSym. Ce résultat a permis à Garsia et Wallach en 2006 de grandement simplifier leur preuve du fait que QSym est un Sym-module libre de rang fini.
Dans cet exposé, nous définissons des nouvelles actions du groupe symétrique permettant de redéfinir les algèbres de Hopf FQSym de Malvenuto-Reutenaeur et PQSym sur les fonctions de parking comme invariant sous ces actions. De façon analogue à Hivert, en généralisant notre action pour PQSym on obtient une infinité de sous-algèbres de Hopf, que l’on est capable de caractériser. L’étude des dimensions de ces algèbres permet de faire un lien avec des résultats énumératifs sur des arbres décroissants.
Les molécules d'ARN consistent en des chaînes de blocs appelés nucléotides (A, U, G, C), et sont surtout connues comme étant de simples intermédiaires dans la synthèse des protéines (ARN messager). Pourtant, elles assurent aussi une grande variété d'autres fonctions au sein des systèmes biologiques, allant de la régulation de l'expression de gènes jusqu'à la catalyse de réactions chimiques. Pour ces ARNs dits "fonctionnels" ou "non-codants", la structure de repliement 3D adoptée est cruciale, et constitue en général la caractéristique conservée par l'évolution, plutôt que simplement la séquence.
De manière peu surprenante, plusieurs problèmes computationnels impliquant cette structure doivent être résolus quotidiennement par les bioinformaticiens lors de l'étude de ces ARNs. On peut citer par exemple le problème du repliement (quelle est la structure préférentielle d'une séquence donnée ?), de la transition entre différents repliements (calcul de barrières d'énergie) ou de l'alignement entre ARNs repliés. Ces problèmes sont typiquement NP-difficiles, surtout lorsque l'on va vers des modèles d'énergie réalistes d'un point de vue biologique.
Cette présentation se focalisera sur des résultats récents d'application de l'algorithmie paramétrée exacte à ces problèmes. Les structures d'ARNs y sont typiquement modélisées en tant que graphes, et un accent particulier est mis sur les approches à base de largeurs de graphes. Le problème de la suppression minimale d'arêtes pour atteindre une valeur de largeur arborescente (treewidth) cible [1], ou celui du calcul de version dirigée de largeurs de graphes [2], seront par exemple mentionnés.
A Demazure polytope is the convex hull of the weight spaces of a Demazure module. The dual fan of a polytope is a useful tool to study the structure of a polytope. For example, the maximal cones of the fan correspond to vertices, while the defining rays of the maximal cones correspond to the codimension 1 hyperplanes of the polytope.
By the work of Besson, Jeralds and Kiers, Demazure polytopes are extremal MV polytopes. The dual fan of an MV polytope was proved by Kamnitzer to be a coarsening of a standard fan known as the Weyl fan. Using an appropriate subclass of MV polytopes called MV polytopes of highest vertex w, we will discuss the problem of describing these dual fans from the coarsening of the Weyl fan.
Dans un article de grande influence, Bidigare, Hanlon et Rockmore (1999) ont établi un lien entre certaines chaines de Markov importantes et la structure de monoïdes sur les faces d'un arrangement d'hyperplan. Ensuite, la théorie a été étendue par Brown à une plus grande classe de monoïdes appelée Bandes Régulières à Gauche (BRG).
Cette conférence explorera une généralisation appelée Bandes Régulières à Gauche de Groupes (BRGG) qui réunit agréablement les BRGs avec la théorie des groupes finis. L'exemple principal sera une BRGG introduite par Hsiao qui relie l'arrangement de tresses avec les algèbres introduites par Mantaci-Reutenauer.
Travail commun avec Jose Bastidas (LACIM) et Sarah Brauner (U Minnesota).
An arithmetical structure on a finite, connected graph without loops is given by an assignment of positive integers to the vertices such that, at each vertex, the integer there is a divisor of the sum of the integers at adjacent vertices, counted with multiplicity if the graph is not simple. Associated to each arithmetical structure is a finite abelian group known as its critical group, which may be regarded as a generalization of the sandpile group of a graph. We present results about the groups that occur as critical groups of arithmetical structures on star graphs, complete graphs, and trees. We also present results about how critical groups are transformed under a generalized star-clique operation. These results are joint work with subsets of Kassie Archer, Abigail Bishop, Alexander Diaz-Lopez, Luis Garcia Puente, and Darren Glass.
Soit Q un carquois (= graphe orienté) à n sommets et K un corps algébriquement clos. Fixons X un KQ-module. Rappelons qu'un KQ-module peut être vu (via une équivalence de catégorie) comme une substitution de chaque sommet par un K-espace vectoriel, et une substitution de chaque flèche par une transformation linéaire . Avec cette traduction, un endormorphisme de X peut se voir comme une collection d'endomorphismes, un pour chaque sommet.
Pour cet exposé, nous allons nous intéresser aux endomorphismes nilpotents de X. Dans l'ensemble de tels endomorphismes, il existe un ensemble ouvert dense O tel que, si M et N appartiennent à O, alors pour chaque sommet q de Q, les formes de Jordan de Nq et Mq sont les mêmes. Ainsi, nous appelons la forme générique de Jordan de X la collection de partages encodant les formes de Jordan de Nq obtenues pour N dans O. Une sous-catégorie C de KQ-modules est dite retrouvable de Jordan si nous pouvons retrouver X, à isomorphisme près, dans C, connaissant sa forme générique de Jordan.
Le but de cet exposé, qui est avant tout une initiation à la théorie de la représentation de carquois, est d'introduire cette notion plus en détails en exhibant son lien avec la correspondance de Robinson-Schensted-Knuth, et en se restreignant à des carquois de type A. Après avoir mis en lumière les difficultés que nous pouvons rencontrer pour montrer qu'une catégorie est retrouvable de Jordan, je présenterai un raffinement de cette notion, appelée retrouvabilité de Jordan canonique, et en donnerai une caractérisation combinatoire. Enfin, si le temps le permet, j'évoquerai quelques points clés d'une preuve de cette caractérisation.
Il s'agit d'une partie de mes travaux de doctorat, encadré par Hugh Thomas.
Crystals for highest weight representations of reductive algebraic groups admit many models. Some involve quantum groups, and some do not. Many factors through actual vector space bases of representations which are “good” or better. We recall definitions with the help of examples and discuss (what is known and what is suspected as to) how such bases compare.
A square is a word of the form $uu$, where $u$ is a finite word. The problem of determining the number of distinct squares in a finite word was initially explored by Fraenkel and Simpson in 1998. They proved that the number of distinct squares, denoted as $\mathrm{Sq}(w)$, in a finite word $w$ of length $n$ is upper bounded by $2n$ and conjectured that $\mathrm{Sq}(w)$ is no larger than $n$. In this talk, we review some old and new findings concerning the square-counting problem and prove that $\mathrm{Sq}(w) \leq n-\Theta(\log_2(n))$.
Dans cet exposé nous allons discuter de la généralisation des m-arrangements de Shi à tout groupe de Coxeter; ici m est un entier naturel. En particulier, nous allons expliquer pourquoi les éléments bas qui apparaissent dans le contexte des ombres de Garside sont en fait les éléments minimaux des régions dans un arrangements de Shi et nous allons discuter le généralisation de la propriété de convexité des inverses de ces éléments. La preuve fait apparaître une structure fine d’ensemble ordonné sur l’ensemble des petites inversions d’un élément w de W en lien avec les descentes à droite et à gauche de w.
Cet exposé est basé sur un travail conjoint avec Dyer, Fishel et Mark.
In this talk we will discuss estimates for the minimal Euler characteristic of even dimensional manifolds with a given finite fundamental group and a highly connected universal cover. In particular we strengthen the Hausmann-Weinberger invariants and extend them to higher dimensions. As an application we obtain new restrictions for non-abelian finite groups arising as fundamental groups of rational homology 4–spheres. This is joint work with Ian Hambleton.
In [Hubert Kogan JSC 2007] we proposed a general algorithm to compute a generating set of rational invariants for the action of algebraic group; what is more, these generators are endowed with rewrite rules.
The use of a section, inspired by the Fels & Olver (1999) take on moving frame, is a key element to effectivity.
The general construction gave the intuition to refined constructions for specific group actions, relevant in applications and offering further connections. Such is the case of scalings [Hubert Labahn FoCM 2013], with a new take on the Buckingham-Pi theorem, finite abelian groups [Hubert Labahn Math. Comp. 2016], and the action of the orthogonal group on homogeneous polynomials in 3D [Görlach Hubert Papadopoulo FoCM 2019] with a computational take on the slices of Seshadri (1962).
Macdonald polynomials are a family of symmetric functions that are known to have remarkable connections to a well-studied particle model called the asymmetric simple exclusion process (ASEP). The modified Macdonald polynomials are obtained from the classical Macdonald polynomials using an operation called plethysm. It is natural to ask whether the modified Macdonald polynomials are related to some other particle system.
We answer this question in the affirmative with a certain multispecies totally asymmetric zero-range process (TAZRP). This link motivated a new tableaux formula for modified Macdonald polynomials. We present a Markov process on those tableaux that projects to the TAZRP and derive formulas for stationary probabilities and certain correlations, proving a remarkable symmetry property. We also discuss some specializations of the tableaux formulas coming from ASEP and TAZRP to obtain some classical results. This talk is based on joint work with Arvind Ayyer and James Martin.
This talk surveys some recent advances, and software, in the field of analytic combinatorics. First, we examine how rigorous numeric analytic continuation of D-finite functions can be combined with a singularity analysis of generating functions to automatically give asymptotics -- with explicit error bounds – for P-recursive sequences (satisfying linear recurrence relations with polynomial coefficients). This work, joint with Marc Mezzarobba and Ruiwen Dong, was recently used by Melczer and Mezzarobba to automatically prove solution uniqueness of the genus one "Canham model" predicting the shape of biomembranes like blood cells. Next, we exhibit the first rigorous software for the asymptotics of multivariate sequences with rational generating functions, using tools from the theory of analytic combinatorics in several variables. Such multivariate tools provide a promising approach to answering certain open problems about the decidability of P-recursive sequences. All software and source code is freely available on public repositories -- and can even be run in the browser with no installation -- and many examples will be given.
Stirling numbers of the first (resp. second) kind count permutations (resp. partitions) of {1,2,...,n} with a fixed number of cycles (resp. blocks). Those of the first kind also give the Hilbert function for two graded algebras coming from type A reflection arrangements, or cohomology of configuration spaces: the Orlik-Solmon (OS) algebra and the graded Varchenko-Gelfand (VG) algebra. The representations of the symmetric group on these algebras are very interesting and well-studied.
Since type A reflection arrangements are supersolvable, their OS and VG algebras have quadratic initial ideals and are Koszul algebras, as observed by Peeva (for OS) and by Dorpalen-Barry (for VG). We study here their Koszul dual algebras, whose Hilbert functions are given by Stirling numbers of the second kind. These dual algebras also have quadratic initial ideals, with pleasant standard monomial bases, and carry interesting representations of the symmetric group. We give descriptions of some of these representations, and branching rules, along with some intriguing conjectures.
This is a preliminary report on joint work with Sheila Sundaram and Vic Reiner.
On présentera les groupes de Garside, qui sont des groupes ayant localement une structure de treillis. Des exemples simples seront donnés en commençant par les groupes de tresses et on montrera en quoi l'on peut dire que les groupes de Garside sont à courbure négative. Présentation d'un travail récent concernant des structures de Garside dans d'autres groupes d'Artin.
This talk is about finding a quasisymmetric variety (QSV): a subset of permutations which (i) is a basis for the Temperley–Lieb algebra TL_n(2), and (ii) has a vanishing ideal (as points in n-space) that behaves similarly to the ideal generated by quasisymmetric polynomials. While this problem is primarily motivated by classical (co-)invariant theory and generalizations thereof, the course of our investigation uncovered a number of remarkable combinatorial properties of our QSV, and I will survey these as well. Of particular interest is a new equivalence relation on permutations defined using their excedance sets. This relation has many nice properties: each equivalence class is naturally indexed by a noncrossing partition and also forms an interval in the (strong) Bruhat order. This allows us to define a quotient Bruhat order and gives a simple method for constructing many new bases of TL_n(2), generalizing known results of Williams–Gobet and Zinno. Surprisingly, the combinatorics of this equivalence relation turn out to be key in solving the QSV problem: collecting the maximal element of each excedance class produces a QSV, and the ensuing noncrossing partition combinatorics are essential to prove this fact. Based on joint work with Nantel Bergeron; arXiv:2302.10814.
Free probability theory, introduced by Voiculescu, is a non-commutative probability theory where the classical notion of independence is replaced by a non-commutative analogue ("freeness"). Originally introduced in an operator-algebraic context to solve problems related to von Neumann algebras, several aspects of free probability are combinatorial in nature. For instance, it has been shown by Speicher that the relations between moments and cumulants related to non-commutative independences involve the study of non-crossing partitions. More recently, the work of Ebrahimi-Fard and Patras has provided a way to usethe group of characters on a Hopf algebra of "words on words", and its corresponding Lie algebra of infinitesimal characters, to study cumulants corresponding to different types of independences (free, boolean and monotone). In this talk we will give a survey of this last construction, and present an alternative description using the notion of series of a species.
Quivers (aka directed graphs) have many interesting ties to combinatorics, algebra, and geometry. We'll begin this talk by overviewing the basics of quiver representations, including Gabriel's Theorem, leading towards a theorem of Kac which counts quiver representations in terms of Kac polynomials. A remarkable theorem of Hua provides an explicit generating function for these Kac polynomials. We'll discuss how Hua's result can be interpreted interms of certain interesting algebraic varieties called Zastava spaces, via recent developments in mathematical physics (the theory of Coulomb branches). This talk is based on joint work with Dinakar Muthiah.
Several linear algebra problems are very interesting in the ring of symmetric polynomials. One of them is understanding combinatorially how to multiply polynomials from different bases and expand the resulting symmetric polynomial in one of the bases. The classical Murnaghan–Nakayama rule is a formula for the product of a Schur symmetric polynomial and a Newton power sum. It is as fundamental as the Pieri rule, and the resulting formulas from the Murnaghan-Nakayama rule are significantly more compact. The Schubert polynomials are a very interesting generalization of Schur polynomials due to their connection with the cohomology of the flag variety in algebraic geometry. In this talk, I will present a general rule for multiplying a quantum Schubert polynomial by a quantum power sum polynomial, achieved by relating the structure constants to the classical case. We will review the classical and quantum stories and discover the combinatorics behind each version. This project is joint work with Carolina Benedetti, Nantel Bergeron, Franco Saliola, and Frank Sottile.
La formule classique des équerres compte le nombre de tableaux standards de formes droites, mais il n’existe aucune formule de produit pour le nombre de tableaux de formes gauches. Okounkov-Olshanski (1996) et Naruse (2014) ont découvert des formules positives d’origine géométrique pour ce nombre de tableaux. Nous discuterons de tableaux standards et de la combinatoire de ces formules. Nous discuterons également des applications sur des tableaux semi-standards, sur des partitions inversées, ainsi que de l’asymptotique du nombre de tableaux. Si le temps nous le permet, nous discuterons enfin des généralisations pour les tableaux croissants, en utilisant les polynômes de Grothendieck. Il s’agit d’un travail réalisé avec Igor Pak, Greta Panova, GaYee Park et Daniel Zhu.
Depuis de nombreuses années, l’opérateur nabla joue un rôle important dans la théorie des polynômes symétriques de Macdonald et leurs applications à de nombreux domaines. Plusieurs autres familles d’opérateurs semblables ont vu le jour au cours du temps. L’opérateur super-nabla unifie et clarifie l’étude des propriétés de tous ces opérateurs. Nous allons expliquer comment, en illustrant le tout de manière très accessible.
The First Fundamental Theorem (FFT) is one of the highlights of invariant theory of reductive groups and goes back to the works of Schur, Weyl, Brauer, etc. For the group $GL(V)$, the FFT describes generators for polynomial invariants on direct sums of several copies of the standard module $V$ and its dual $V*$. Then R. Howe pointed out that the FFT is closely related to a double centralizer statement inside a Weyl algebra (a.k.a. the algebra of polynomial-coefficient differential operators).
In this talk we first construct a quantum Weyl algebra and then present a quantum analogue of the FFT. As a special case of this FFT we obtain a double centralizer statement inside our quantum Weyl algebra. We remark that the FFT that we obtain is different from the one proved by G. Lehrer, H. Zhang, and R.B. Zhang for $U_q(gl(n))$. Time permitting, I will explain the connection between this work and the Capelli Eigen value Problem for classical quantum groups. This talk is based on a joint project with Gail Letzter and Siddhartha Sahi.
À un carquois arbitraire, on peut associer une algèbre de Kac—Moody généralisée, définie par générateurs et relations. Son algèbre enveloppante a une déformation naturelle, le groupe quantique. Dans cet exposé, on s’intéressera à ces algèbres associatives ainsi qu’à différents ensembles de générateurs de celles-ci. Les fonctions symétriques non-commutatives jouent un rôle crucial pour comprendre les carquois à un seul sommet et plusieurs boucles. Outre la définition de bases naturelles pour ces algèbres, les constructions ont aussi une motivation géométrique que l’on mentionnera.
Le fragment de la logique combinatoire engendré par le combinateur M, également connu sous le nom du "Moqueur", possède une combinatoire riche. Entre autres, les composantes connexes du graphe de réécriture des termes sur M sont des diagrammes de Hasse de treillis. Nous présentons ce résultat en réalisant ce graphe de réécriture par des forêts duplicatives, qui sont des structures arborescentes particulières. Nous présentons également des résultats énumératifs à propos de ces treillis, comme leur nombre d'éléments et leur nombre d'intervalles.
Cet exposé ne demande aucun prérequis en logique combinatoire : toutes les notions importantes pour le suivre seront données dans sa première partie, tout comme les questions d'informatique théorique que l'on se pose habituellement dans ce contexte. La deuxième partie est véritablement combinatoire, tandis que la dernière s'inscrit plutôt en combinatoire algébrique.
Cauchy’s determinantal identity (1840s) expands via Schur polynomials the determinant of the matrix f[uvT ], where f(t) = 1/(1 − t) is applied entrywise to the rank-one matrix (uivj ). This theme has resurfaced in the 2010s in analysis (following a 1960s computation by Loewner), in the quest to find polynomials p(t) with a negative coefficient that entrywise preserve positivity. The key novelty here has been an application of Schur polynomials, which essentially arise from a determinantal identity for p[uvT].
In the first two parts of the talk, I will explain the above journey from matrix positivity to determinantal identities and Schur polynomials; then go beyond, to the expansion for f[uvT ] for all power series f. (Partly based on joint works with Alexander Belton, Dominique Guillot, Mihai Putinar, and with Terence Tao.) In the third part, joint with Siddhartha Sahi, I will explain how to extend the above determinantal identities to (a) any subgroup of signed permutations;(b) any character of G, or even complex class function; (c) any commutative ground ring R; and (d) any power series over R.
The collection of parking functions under a natural Sn-action (which has Catalan-many orbits) has been a central object in Algebraic Combinatorics since the work of Haiman more than 30 years ago. One of the lines of research spawned around it was towards defining and studying analogous objects for real and complex reflection groups W; the main candidates are known as the W-non-nesting and W-non-crossing parking functions.
The W-non-nesting parking functions are relatively well understood; they form the so called algebraic W-parking-space which has a concrete interpretation as a quotient ring. The W-non-crossing ones on the other hand have defied unified explanations while simultaneously proving themselves central in the study of Coxeter and Artin groups (their geometric group theory, representation theory, and combinatorics). One of the main open problems in the field since the early 2000's has been to give a type-independent proof of the W-isomorphism between the algebraic and the non-crossing W-parking spaces. In this talk, I will present such a proof, solving the more general Fuss version of the problem, that proceeds by comparing a collection of recursions that are shown to be satisfied by both objects. This relies on a variety of recent techniques we introduced, in particular the enumeration of certain flats of full support via Crapo's beta invariant, the W-Laplacian matrices for reflection arrangements and, in collaboration with Matthieu Josuat-Verges, the refined f- to h- transformation between the cluster complex and the non-crossing lattice of W.
Cyclic polytopes are a very special family of polytopes possessing some beautiful properties. In particular, the set of triangulations of a cyclic polytope has a rich combinatorial structure which appears in several other areas of mathematics. This set of triangulations possesses two natural partial orders, which can be seen as generalisations of the Tamari lattice. These are known as the first and second higher Stasheff--Tamari orders, the first of which was introduced by Kapranov and Voevodsky, and the second introduced by Edelman and Reiner. Edelman and Reiner conjectured these two orders to coincide. In this talk we outline our proof of this conjecture. This result also has ramifications for the representation theory of certain finite-dimensional algebras, which we will touch on if time permits.