2021-2022
Lundi 4 juillet 9h30 : Philippe Duchon
Petite école de combinatoire: Pavages par dominos (existence, comptage, génération aléatoire) (5/5)
Résumé : On s'intéresse ici à des objets qui portent des noms variés: pavages par dominos, modèles de dimères, couplages parfaits de certains graphes. Il s'agit tout simplement des façons de couvrir une région du plan par des rectangles (2x1 ou 1x2); par extension, par d'autres formes qui correspondent à deux cellules d'un autre réseau régulier du plan que le réseau carré (réseau triangulaire, réseau hexagonal).
Au programme: le critère de Conway-Lagarias-Thurston pour dire si une région finie simplement connexe est pavable; le codage de pavages par "fonctions de hauteurs"; le comptage des pavages d'une région donnée et les algorithmes de génération aléatoire (uniforme ou pas) via le "glissement de dominos" (domino shuffling), pour les formes dites de "diamant aztèque" ou pour d'autres. En option, les résultats de type "cercle arctique" et les caractéristiques asymptotiques locales des pavages du diamant aztèque.
Lundi 4 juillet : Nicolas Bonichon
Titre : ⚠ $d$-Permutations de Baxter et autres ⚠ $d$-permutations à motifs exclus
Résumé : Une permutation de taille ⚠ $n$ peut-être identifiée à son diagramme : un nuage de ⚠ $n$ points dans la grille [n]^2 tel que chaque ligne et chaque colonne contienne exactement un point. Dans ce papier nous considérons des permutations multidimensionnelles (ou ⚠ $d$-permutations), qui peuvent être identifiées à des nuages de ⚠ $n$ points dans la grille [n]^d tels que chaque hyperplan ⚠ $x_i=j$ avec ⚠ $i \in [d]$ et ⚠ $j \in [n]$ contienne exactement 1 point.
Dans un premier temps nous investiguons de manière exhaustive l’énumération des classes de permutations qui évitent des petits motifs. Nous proposons quelques bijections vers d’autres objets combinatoires pour expliquer certaines séquences connues, mais nous laissons également quelques questions ouvertes.
Dans un deuxième temps nous proposons une généralisation des permutations de Baxter aux ⚠ $d$-permutations. De plus, nous proposons une caractérisation de ces permutations en termes de motifs liés (vincular patterns).
Travail réalisé en collaboration avec Pierre-Jean Morel.
Lundi 27 juin 9h30 : Valentin Bonzom
Petite école de combinatoire: le wedge semi-infini et la hiérarchie KP
Résumé : On sait que les séries génératrices de cartes, cartes biparties ou encore constellations comptées par nombre de faces de degré k >=1 satisfont un ensemble d'équations aux dérivées partielles appelé la hiérarchie KP. Bien qu'on ne connaisse pas de dérivation bijective de ces équations, la hiérarchie KP peut se décrire combinatoirement soit en termes de fonctions symétriques, soit dans le cadre du wedge semi-infini. Ce dernier est un système de particules sans interactions pouvant occuper des sites sur une ligne. J'expliquerai en quoi ce formalisme est équivalent à la théorie des fonctions symétriques via la correspondance bosons-fermions, et comment on peut interpréter la hiérarchie KP comme relations de Plücker sur le wedge semi-infini.
Lundi 27 juin 10h45 : Valentin Bonzom
Titre : Hiérarchie intégrable BKP et applications aux cartes non-orientées
Résumé : Plusieurs familles de cartes comme les triangulations et les cartes biparties comptées par taille et genre admettent des formules de récurrence remarquablement simples qui permettent de générer ces nombres efficacement. De manière intrigante, on ne sait prouver ces récurrences que par des équations issues des systèmes intégrables appelées hiérarchie KP. Dans cet exposé, j'expliquerai en termes de développement sur les fonctions de Schur ce que signifie pour une série génératrice de satisfaire la hiérarchie KP, et je donnerai plusieurs manières de la prouver dans le cas bien connu des factorisations de permutations (qui correspond également aux constellations et aux nombres de Hurwitz pondérés). Je présenterai le défi du passage aux modèles de cartes non-orientées par une tension entre développement sur les fonctions de Schur et sur les polynomes zonaux et j'évoquerai le problème connexe de la b-conjecture de Goulden et Jackson. Enfin je montrerai comment nous avons pu prouver une hiérarchie intégrable dans un cas assez résistant aux méthodes établies, celui de la série génératrice des nombres de Hurwitz monotones non-orientés. Ce sont des travaux en collaboration avec Guillaume Chapuy et Maciej Dolega.
Lundi 20 juin 9h30 : Philippe Duchon
Petite école de combinatoire: Pavages par dominos (existence, comptage, génération aléatoire) (4/5)
Résumé : On s'intéresse ici à des objets qui portent des noms variés: pavages par dominos, modèles de dimères, couplages parfaits de certains graphes. Il s'agit tout simplement des façons de couvrir une région du plan par des rectangles (2x1 ou 1x2); par extension, par d'autres formes qui correspondent à deux cellules d'un autre réseau régulier du plan que le réseau carré (réseau triangulaire, réseau hexagonal).
Au programme: le critère de Conway-Lagarias-Thurston pour dire si une région finie simplement connexe est pavable; le codage de pavages par "fonctions de hauteurs"; le comptage des pavages d'une région donnée et les algorithmes de génération aléatoire (uniforme ou pas) via le "glissement de dominos" (domino shuffling), pour les formes dites de "diamant aztèque" ou pour d'autres. En option, les résultats de type "cercle arctique" et les caractéristiques asymptotiques locales des pavages du diamant aztèque.
Lundi 20 juin 10h45 : Yvan Le Borgne
Titre :Des structures dans le modèle du tas de sable pour les configurations périodiques dans le réseau carré.
Résumé : Le modèle du tas de sable est un modèle de diffusion de grains entre les sommets d'un graphe introduit en 1987 par Bak, Tang et Wiesenfeld et dont les premières propriétés ont été identifiées par Dhar. Ce modèle est étudié pour ces nombreuses structures notamment dans le cas d'un graphe fini. Par exemple, les pas élémentaires de diffusions commutent, les états récurrents d'une chaîne de Markov naturelle sont en bijection avec arbres couvrants du graphe et forment un groupe ce qui explique l'uniformité de la mesure stationnaire. Dans le cas du réseau carré qui est un graphe infini, plusieurs travaux parfois récents ont montré qu'une partie de ces structures se généralisent de diverses façons. Nous poursuivons l'étude amorcée avec Henri Derycke durant sa thèse qui traite de ces structures pour la restriction aux configurations périodiques de période rectangulaire (W,H) dont l'avantage principal est de permettre des calculs effectifs comme pour les graphes finis.
Lundi 13 juin 9h30 : Philippe Duchon
Petite école de combinatoire: Pavages par dominos (existence, comptage, génération aléatoire) (3/4)
Résumé : On s'intéresse ici à des objets qui portent des noms variés: pavages par dominos, modèles de dimères, couplages parfaits de certains graphes. Il s'agit tout simplement des façons de couvrir une région du plan par des rectangles (2x1 ou 1x2); par extension, par d'autres formes qui correspondent à deux cellules d'un autre réseau régulier du plan que le réseau carré (réseau triangulaire, réseau hexagonal).
Au programme: le critère de Conway-Lagarias-Thurston pour dire si une région finie simplement connexe est pavable; le codage de pavages par "fonctions de hauteurs"; le comptage des pavages d'une région donnée et les algorithmes de génération aléatoire (uniforme ou pas) via le "glissement de dominos" (domino shuffling), pour les formes dites de "diamant aztèque" ou pour d'autres. En option, les résultats de type "cercle arctique" et les caractéristiques asymptotiques locales des pavages du diamant aztèque.
Lundi 13 juin : Krishna Menon
Titre :A branch statistic for trees
Résumé : A hyperplane arrangement is a finite collection of affine hyperplanes in Euclidean space. Its regions are the connected components of the complement of these hyperplanes. By a theorem of Zaslavsky, the number of regions of a hyperplane arrangement is the sum of coefficients of its characteristic polynomial. In this talk, we study an important class of arrangements called extended Catalan arrangements. The regions of such arrangements are known to correspond to certain labeled trees. We define a statistic on these trees such that its distribution is given by the coefficients of the characteristic polynomial. We will end by looking at some other arrangements and interpretations of their characteristic polynomial coefficients. This talk is based on joint work with Priyavrat Deshpande.
Lundi 30 mai 9h30 : Philippe Duchon
Petite école de combinatoire: Pavages par dominos (existence, comptage, génération aléatoire) (2/4)
Résumé : On s'intéresse ici à des objets qui portent des noms variés: pavages par dominos, modèles de dimères, couplages parfaits de certains graphes. Il s'agit tout simplement des façons de couvrir une région du plan par des rectangles (2x1 ou 1x2); par extension, par d'autres formes qui correspondent à deux cellules d'un autre réseau régulier du plan que le réseau carré (réseau triangulaire, réseau hexagonal).
Au programme: le critère de Conway-Lagarias-Thurston pour dire si une région finie simplement connexe est pavable; le codage de pavages par "fonctions de hauteurs"; le comptage des pavages d'une région donnée et les algorithmes de génération aléatoire (uniforme ou pas) via le "glissement de dominos" (domino shuffling), pour les formes dites de "diamant aztèque" ou pour d'autres. En option, les résultats de type "cercle arctique" et les caractéristiques asymptotiques locales des pavages du diamant aztèque.
Lundi 30 mai 10h45 : France Gheeraert
Titre :Dendric words and strongly left proper morphisms
Résumé : Given a language L, we associate to each word its extension graph in L. This graph describes the letters that we can see to the left and to the right of the word in L. If this graph is a tree, then we say that the word is dendric, and if all the elements of L are dendric, we say that L itself is dendric. This notion generalizes the well-studied Sturmian and Arnoux-Rauzy words, as well as the codings of regular interval exchanges.
Among all morphisms, strongly left proper morphisms have some recognizability property which makes the study of their images easier. In this talk, I will then present results related to images of dendric languages under strongly left proper morphisms, in order to obtain an S-adic characterization of dendric languages. This is a joint work with Julien Leroy.
Lundi 23 mai 10h45 : Luca Lionni
Titre : Une famille de triangulations de la 3-sphère construite à partir d'arbres
Résumé : Si le zoo des arbres et surfaces browniens est bien peuplé, on ne connait aucun exemple en dimension topologique supérieure à deux. Il s’agirait par exemple de trouver une généralisation en dimensions supérieures de la 2-sphère brownienne (ou carte brownienne), c’est à dire de produire des suites de triangulations aléatoires ou graphes aléatoires plus généraux qui admettraient pour limite d’échelle continue une 3-sphère brownienne. Tous les efforts dans ce sens ont jusque là redonné des objets limites connus ou vraisemblablement triviaux. Ces résultats sont cependant principalement basés sur des simulations, et dans la plupart des cas, comme par exemple pour les triangulations uniformes de la 3-sphère, les résultats exacts sont hors de portée. Ceci peut notamment s’expliquer par l’absence d’encodages bijectifs par des objets combinatoires plus simples aux propriétés asymptotiques connues, comme des arbres. Je décrirai un sous-ensemble de triangulations de la 3-sphère encodés bijectivement par trois arbres, que nous avons introduits avec Timothy Budd pour tenter de pallier ces problèmes.
Lundi 16 mai 9h30 : Philippe Duchon
Petite école de combinatoire: Pavages par dominos (existence, comptage, génération aléatoire) (1/4)
Résumé : On s'intéresse ici à des objets qui portent des noms variés: pavages par dominos, modèles de dimères, couplages parfaits de certains graphes. Il s'agit tout simplement des façons de couvrir une région du plan par des rectangles (2x1 ou 1x2); par extension, par d'autres formes qui correspondent à deux cellules d'un autre réseau régulier du plan que le réseau carré (réseau triangulaire, réseau hexagonal).
Au programme: le critère de Conway-Lagarias-Thurston pour dire si une région finie simplement connexe est pavable; le codage de pavages par "fonctions de hauteurs"; le comptage des pavages d'une région donnée et les algorithmes de génération aléatoire (uniforme ou pas) via le "glissement de dominos" (domino shuffling), pour les formes dites de "diamant aztèque" ou pour d'autres. En option, les résultats de type "cercle arctique" et les caractéristiques asymptotiques locales des pavages du diamant aztèque.
Lundi 16 mai : Sacha Zvonkine
Titre : La conjecture de Bateman-Horn et ses applications
Résumé : Soient k polynômes ⚠ $f_1,f_2,\ldots,f_k$ à coefficients entiers. On s'intéresse à la question suivante: pour un ⚠ $x\in\mathbb{N}$ donné, combien y a-t-il d'entiers positifs ⚠ $t\le x$ telles que toutes les valeurs ⚠ $f_1(t),f_2(t),\ldots,f_k(t)$ soient des nombres premiers à la fois?
La conjecture de Bateman-Horn propose une réponse asymptotique à cette question quand ⚠ $x\to\infty$. Les estimations correspondantes sont souvent d'une précision étonnante. Je vais formuler la conjecture et présenter quelques applications à la théorie des nombres, la théorie des groupes et la théorie des block designs.
Lundi 9 mai : Wenjie Fang
Titre :Parabolic Tamari Lattices in Linear Type B
Résumé :
We study parabolic aligned elements associated with the type-⚠ $B$ Coxeter group and the so-called linear Coxeter element. These elements were introduced algebraically in (Mühle and Williams, 2019) for parabolic quotients of finite Coxeter groups and were characterized by a certain forcing condition on inversions. We focus on the type-⚠ $B$ case and give a combinatorial model for these elements in terms of pattern avoidance. Moreover, we describe an equivalence relation on parabolic quotients of the type-⚠ $B$ Coxeter group whose equivalence classes are indexed by the aligned elements. We prove that this equivalence relation extends to a congruence relation for the weak order. The resulting quotient lattice is the type-⚠ $B$ analogue of the parabolic Tamari lattice introduced for type ⚠ $A$ in (Mühle and Williams, 2019). These lattices have not appeared in the literature before. As work in progress, we will also talk about various combinatorial models and bijections between them. Joint work with Henri Mühle and Jean-Christophe Novelli.
Lundi 2 mai : Philippe Nadeau
Titre : Algorithmes de parking locaux sur les entiers
Résumé : Les fonctions de parking sont des objets centraux de la combinatoire énumérative et algébrique. Elles sont définies par une simple procédure de "parking" sur les entiers. Nous généralisons cette procédure ici pour définir une classe d'algorithmes "locaux", pour lesquels les fonctions de parking de taille r associées seront à chaque fois comptées par (r+1)^(r-1). Nous expliquerons aussi comment de telles procédures sont naturellement liées aux arbres binaires, et étendrons nos résultats à un cadre probabiliste. Si le temps le permet, nous montrerons comment cette étude est née d'un problème de géométrie énumérative.
Lundi 4 avril (10h45) : Erkan Narmali
Titre :Cartes décorées et chemins dans le quart de plan
Résumé : On montre que les posets plan, les structures transverses, ainsi que deux familles de surfaces orthogonales en lien avec des cartes décorées, peuvent être mises en bijection avec des marches pondérées dans la quart de plan à l'aide de la correspondance de Kenyon, Miller, Sheffield et Wilson sur les orientation bipolaires. En nous servant des résultats de Bostan, Raschel et Salvy sur le comptage asymptotique de marches aléatoire dans un cône, ou à l'aide de méthodes ad-hoc, on trouve des résultats asymptotique pour ces quatre modèles de cartes. On montre également une bijection entre les posets plan à n+2 sommets et les permutations de taille n qui évitent le motif barré : 2[14]3.
Lundi 4 avril (9h30) : Jean-Christophe Aval
Titre : Fonctions quasisymétriques distinguant les arbres (?) (2/2)
Résumé : En 1995, R. Stanley introduit un nouvel invariant sur les graphes, la fonction symétrique chromatique. Il conjecture alors que celle-ci distingue les arbres, ce qui n'a toujours pas été prouvé. Nous étudions un analogue quasisymétrique de cette question en conjecturant que la fonction quasisymétrique chromatique (Shareshian-Wachs 2016, Ellzey 2017) distingue les arbres orientés. Nous observons que cette conjecture serait impliquée par une réponse affirmative à la question de Hasebe et Tsujie (2017) qu'un invariant très étudié sur les posets étiquetés (le polynôme énumérateur des P-partitions) distingue les posets dont le diagramme de Hasse est un arbre. Leurs résultats incluent le cas des arbres enracinés, et nous prouvons une généralisation de ce cas.
Travail en commun avec K. Djenabou et P. McNamara.
Lundi 28 mars : Jean-Christophe Aval
Titre : Fonctions quasisymétriques distinguant les arbres (?) (1/2)
Résumé : En 1995, R. Stanley introduit un nouvel invariant sur les graphes, la fonction symétrique chromatique. Il conjecture alors que celle-ci distingue les arbres, ce qui n'a toujours pas été prouvé. Nous étudions un analogue quasisymétrique de cette question en conjecturant que la fonction quasisymétrique chromatique (Shareshian-Wachs 2016, Ellzey 2017) distingue les arbres orientés. Nous observons que cette conjecture serait impliquée par une réponse affirmative à la question de Hasebe et Tsujie (2017) qu'un invariant très étudié sur les posets étiquetés (le polynôme énumérateur des P-partitions) distingue les posets dont le diagramme de Hasse est un arbre. Leurs résultats incluent le cas des arbres enracinés, et nous prouvons une généralisation de ce cas.
Travail en commun avec K. Djenabou et P. McNamara.
Enregistrement (début avec le son à 1min25)
Lundi 21 mars : Émilie Charlier
Titre : A full characterization of Bertrand numeration systems.
Résumé : Among all positional numeration systems, the widely studied Bertrand numeration systems are defined by a simple criterion in terms of their numeration languages. In 1989, Bertrand-Mathis characterized them via representations in a real base ⚠ $\beta$. However, the given condition turns out to be not necessary. Hence, the goal of this paper is to provide a correction of Bertrand-Mathis' result. The main difference arises when ⚠ $\beta$ is a Parry number, in which case two associated Bertrand numeration systems are derived. Along the way, we define a non-canonical ⚠ $\beta$-shift and study its properties analogously to those of the usual canonical one.
Lundi 7 mars : Etienne Moutot
Titre : Nivat's Conjecture and Decidability of the Domino Problem
Résumé : Nivat's conjecture states that any coloring of the plane with "few enough" different patterns must be periodic. Even if the statement of the conjecture is quite simple and very similar to the one dimensional Morse-Hedlund theorem, the conjecture is still open since stated by Maurice Nivat in 1997. However, there have been a lot of progress towards a proof in the last five years, and many new tools started to emerge.
In this talk I will present the conjecture and some of the last results around it. I will focus on algebraic tools introduced by Kari and Szabados and the results we obtained by working with them with Kari. In particular, I will discuss about the decidability of the domino problem (which consist in trying to know if a given set of tiles does tile the plane or not) depending of the pattern complexity of the considered tileset.
Most of the talk is based on the following paper: [1] Decidability and Periodicity of Low Complexity Tilings. Jarkko Kari, Etienne Moutot, Theory of Computing Systems, 2021
Lundi 7 février : Solène Esnay
Titre : Invariants de sous-shifts bidimensionels sous contraintes horizontales
Résumé :
Si l'on se donne un alphabet fini ⚠ $\mathcal{A}$, on peut considérer l'ensemble des coloriages de la grille ⚠ $\mathbb{Z}^2$ par celui-ci - ⚠ $\mathcal{A}^{\mathbb{Z}^2}$, que l'on nomme le full shift. Muni de la topologie produit et de l'action de ⚠ $\mathbb{Z}^2$ par translation nommée ⚠ $\sigma$, il forme un système dynamique. En rajoutant un ensemble de contraintes, c'est-à-dire des motifs colorés dont on interdit l'apparition, on obtient un sous-système du full shift, appelé un sous-shift. Ce sous-shift est dit « de type fini » (SFT, Subshift of Finite Type) si l'ensemble des contraintes ajoutées est fini. De façon similaire, on peut définir des full shifts et des sous-shifts en dimension 1, sur ⚠ $\mathbb{Z}$.
Deux grands invariants par conjugaison sont bien connus et très étudiés sur les sous-shifts : l'entropie, qui caractérise la croissance asymptotique du nombre de coloriages de taille NxN respectant les contraintes ; et le problème du domino, qui pose la question de l'existence d'un algorithme capable de caractériser exactement tous les sous-shifts non-vides pour un alphabet et une dimension donnés. Il est connu qu'en dimension 1, le problème du domino est décidable et les entropies accessibles sont toutes calculables ; en revanche, en dimension 2, le problème du domino est indécidable et tous les réels positifs ⚠ $\Pi_1^0$ sont accessibles.
Dans le présent exposé, après avoir rappelé ces notions, nous nous intéresserons à la frontière entre les dimensions 1 et 2, en considérant un SFT bidimensionel dont les seules contraintes initiales sont horizontales, et en regardant les SFTs qui sont ses sous-systèmes, c'est-à-dire pouvant être construits en ajoutant des contraintes quelconques à partir de celui initial. Selon les contraintes horizontales initiales, nous mettrons en évidence des différences de comportement sur le problème du domino en découlant, et les entropies accessibles.
Lundi 31 janvier : Ivan Yakovlev
Titre :Enumération des cartes métriques
Résumé : Certaines questions géométriques amènent à l'énumeration des cartes biparties unicellulaires métriques (c. à d. dont les arêtes portent des longueurs positives) avec les sommes des longueurs autour des sommets prescrites. Le résultat du comptage n'est plus un nombre, mais en général une fonction (quasi)polynomiale par morceaux. Dans notre cas particulier, ces fonctions sont plus jolies que ce que l'on attendait a priori. Je vais expliquer mon approche combinatoire dans le cas des arbres planaires (g=0), où on obtient des formules "à la Catalan", ainsi que mes efforts de l'étendre au genre supérieure (g>0), où on s'appuie, entre autres, sur les bijections de Chapuy pour les cartes unicellulaires.
Lundi 24 janvier : Elie de Panafieu
Titre : Énumération exacte des formules 2-SAT satisfaisables
Résumé : L'énumération de familles de graphes orientés (tels que les graphes orientés acycliques ou fortement connexes) se simplifie grandement en introduisant des séries génératrices particulières, appelées `spéciale' ou `graphiques'. Inspirés par cette approche, nous proposons un nouveau type de séries génératrices pour énumérer les formules 2-SAT satisfaisables, une célèbre famille de formules booléennes. Contrairement aux précédentes, notre expression est calculable en temps polynomial. Cela nous permet d'explorer numériquement la transition de phase des formules 2-SAT. Travail en commun avec Sergey Dovgal et Vlady Ravelomanana, disponible sur arXiv https://arxiv.org/abs/2108.08067.
Lundi 17 janvier : Julien Courtiel
Titre : Solving Prellberg and Mortimer's conjecture - bijection(s) between Motzkin paths and triangular walks
Résumé : Alors que la cinquième vague nous fait boire la tasse, nous avons tous besoin de nous réconforter autour de jolies bijections pleines de couleurs.
Cet exposé parle d'un travail coréalisé avec Andrew Elvey-Price (Tours) et Irène Marcovici (Nancy). Nous avons répondu ensemble à une question ouverte de Mortimer et Prellberg, sollicitant une bijection entre une famille de marches dans un domaine triangulaire borné (pensez à un grand triangle équilatéral subdivisé en plusieurs petits triangles équilatéraux) et les fameux chemins de Motzkin, mais avec une hauteur bornée.
Les techniques que nous utilisons pour les preuves sont élémentaires et semblent robustes. En plus de résoudre la conjecture de Mortimer et Prellberg, notre approche nous a permis de trouver une nouvelle bijection inattendue entre des marches tridimensionnelles contraintes dans une pyramide et certaines marches bidimensionnelles sur une grille carrée.
Lundi 10 janvier : Ruxi Shi
Titre : Tuiles et ensembles spectraux sur les entiers et les groupes cycliques
Résumé : Un ensemble fini ⚠ $E$ sur ⚠ $\mathbb{Z}$ (ou ⚠ $\mathbb{Z}_N$) est une tuile par translation si ⚠ $\mathbb{Z}$ (ou ⚠ $\mathbb{Z}_N$) peut être couvert par une union disjointe de translations de ⚠ $E$. Une conjecture de Fuglede de 1974 dit qu'un ensemble ⚠ $E$ est une tuile si et seulement s'il est un ensemble spectral, c'est-à-dire que l'espace ⚠ $L^2(E)$ admet une base orthonormée de fonctions exponentielles. Dans cet exposé, nous parlerons de la caractérisation des tuiles et des ensembles spectraux dans les groupes cycliques ⚠ $\mathbb{Z}_{pqr}$. Nous discuterons également des méthodes pour découvrir la structure des tuiles et des ensembles spectraux.
L'exposé est basé sur la publication ici: https://discreteanalysisjournal.com/article/10570-fuglede-s-conjecture-holds-on-cyclic-groups-mathbb-z-_-pqr (Editorial introduction ici donne un bref historique sur le sujet de mon exposé).
Lundi 6 décembre : Torsten Mütze
Titre : Efficient generation of elimination trees and Hamilton paths on graph associahedra
Résumé : An elimination tree for a connected graph G is a rooted tree on the vertices of G obtained by choosing a root x and recursing on the connected components of G−x to produce the subtrees of x. Elimination trees appear in many guises in computer science and discrete mathematics, and they are closely related to centered colorings and tree-depth. They also encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung-Hoang-Mütze-Williams combinatorial generation framework to elimination trees, and prove that all elimination trees for a chordal graph G can be generated by tree rotations using a simple greedy algorithm (see www.combos.org/elim). This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. Our algorithm for generating all elimination trees for a chordal graph G can be implemented in time O(m+n) per generated elimination tree, where m and n are the number of edges and vertices of G, respectively. If G is a tree, we improve this to a loopless algorithm running in time O(1) per generated elimination tree. We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of G, rather than just Hamilton path, if the graph G is chordal and 2-connected. Moreover, our algorithm characterizes chordality, i.e., it computes a Hamilton path on the graph associahedron of G if and only if G is chordal.
This is joint work with Jean Cardinal (ULB) and Arturo Merino (TU Berlin)
Lundi 29 novembre : Andrew Elvey Price
Titre : Analytic solutions for walks with small steps in the three quarter plane
Résumé : I will discuss the analytic method for counting walks with small steps in the quarter plane, which has been heavily used in the classification of these walk models. In particular I will describe how it can be extended to walks in the 3/4-plane. In particular this work proves a conjecture of Dreyfus and Trotignon that the complexity (algebraic, D-finite, D-algebraic, etc.) of the generating function Q(x,y;t) counting walks in the quarter plane is the same as that of the generating function C(x,y;t) counting walks in the three-quarter plane, at least with respect to the variables x and y.
Lundi 22 novembre : Mélodie Lapointe
Titre :The ⚠ $q$-analog of the Markoff injectivity conjecture holds over the language of a balanced sequence
Résumé : The Markoff injectivity conjecture states that ⚠ $w\mapsto\mu(w)_{12}$ is injective on the set of Christoffel words where ⚠ $\mu:\{\mathtt{0},\mathtt{1}\}^*\to\mathrm{SL}_2(\mathbb{Z})$ is a certain homomorphism and ⚠ $M_{12}$ is the entry above the diagonal of a ⚠ $2\times2$ matrix ⚠ $M$. Recently, Leclere and Morier-Genoud (2021) proposed a ⚠ $q$-analog ⚠ $\mu_q$ of ⚠ $\mu$ such that ⚠ $\mu_{q\to1}(w)_{12}=\mu(w)_{12}$ is the Markoff number associated to the Christoffel word ⚠ $w$. We show that there exists an order ⚠ $<_{radix}$ on ⚠ $\{\mathtt{0},\mathtt{1}\}^*$ such that for every balanced sequence ⚠ $s \in \{\mathtt{0},\mathtt{1}\}^\mathbb{Z}$ and for all factors ⚠ $u, v$ in the language of ⚠ $s$ with ⚠ $u <_{radix} v$, the difference ⚠ $\mu_q(v)_{12} - \mu_q(u)_{12}$ is a nonzero polynomial of indeterminate ⚠ $q$ with nonnegative integer coefficients. Therefore, for every ⚠ $q>0$, the map ⚠ $\{\mathtt{0},\mathtt{1}\}^*\to\mathbb{R}$ defined by ⚠ $w\mapsto\mu_q(w)_{12}$ is increasing thus injective over the language of a balanced sequence. The proof uses an equivalence between balanced sequences satisfying some Markoff property and indistinguishable asymptotic pairs. Joint work with S. Labbé. Preprint available at https://arxiv.org/abs/2106.15886
Lundi 15 novembre : Vincent Delecroix
Titre : Courbes et multicourbes dans les graphes en rubans
Résumé : M. Mirzakhani a démontré des formules pour l'asymptotique de comptage des multicourbes sur une surface hyperblique X. La limite fait intervenir la géométrie de X via un nombre réel positif noté B(X). Cette fonction B peut-être définie pour toute structure X sur la surface qui nous permet de donner un sens à la longueur des courbes. En particulier pour un graphe métrique plongé dans la surface. Dans ce dernier cas la quantité B(X) devient explicite : c'est une fonction rationnelle des longueurs des arêtes. On peut alors exploiter cette formule pour étudier les propriétés de B vue comme fonction sur l'espace des graphes métriques.
travail en commun avec G. Borot, S. Charbonnier, A. Giacchetto et C. Wheeler disponible à https://arxiv.org/abs/2110.12538
Lundi 8 novembre : Cyril Banderier and Michael Wallner
Titre : Young Tableaux with Periodic Walls: Counting with the Density Method
Résumé : We consider a generalization of Young tableaux in which we allow some consecutive pairs of cells with decreasing labels, conveniently visualized by a "wall" between the corresponding cells. Some shapes can be enumerated by variants of hook-length type formulas. We focus on families of tableaux (like the so-called "Jenga tableaux") having some periodic shapes, for which the generating functions are harder to obtain. We get some interesting new classes of recurrences, and a surprisingly rich zoo of generating functions (algebraic, hypergeometric, D-finite, differentially-algebraic). Some patterns lead to nice bijections with trees, lattice paths, or permutations. Our approach relies on the density method, a powerful way to perform both random generation and enumeration of linear extensions of posets.
(exposé à 2 voix, basé sur notre article à FPSAC 2021: https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2021/47.html )
Lundi 18 octobre : Sébastien Labbé
Titre : Une caractérisation des mots Sturmiens par les paires asymptotiques indistinguables
Résumé : Nous donnons une nouvelle caractérisation des mots Sturmiens bi-infinis en termes de paires asymptotiques indistinguables. Deux suites asymptotiques sur un sous-décalage sont indistinguables si les ensembles d'occurrences de chaque motif dans chaque suite coïncident à une permutation finiement supportée près. Cette caractérisation peut être considérée comme une extension aux suites bi-infinies non périodiques du théorème de Pirillo qui caractérise les mots de Christoffel. De plus, nous fournissons une caractérisation complète des paires asymptotiques indistinguables sur des alphabets arbitraires en utilisant des substitutions et des mots Sturmiens caractéristiques bi-infinis. La preuve est basée sur la notion de suites dérivées. Il s'agit d'un travail réalisé avec Sebastián Barbieri et Štěpán Starosta. La prépublication est disponible ici: https://arxiv.org/abs/2011.08112 et la publication ici: https://doi.org/10.1016/j.ejc.2021.103318
Transparents, Enregistrement du même exposé pendant "One World Combinatorics on Words Seminar"
Lundi 20 septembre : Daniel Tamayo Jiménez
Titre : Permutree sorting
Résumé : We define permutree sorting which generalizes the stack sorting and Coxeter sorting algorithms respectively due to Knuth and Reading. Given two disjoint subsets ⚠ $U$ and ⚠ $D$ of ⚠ $\{2,...,n\}$, it consists of an algorithm that fails for a permutation if and only if there are integers ⚠ $i<j<k$ in [⚠ $n$]
such that the permutation contains the pattern ⚠ $jki$ (resp. ⚠ $kij$) if ⚠ $j$ is in ⚠ $U$ (resp. in ⚠ $D$). We present this algorithm through automata that read reduced expressions and accept only those that form a special structure within the weak order. This is joint work with Vincent Pilaud and Viviane Pons.
Lundi 6 septembre : Jean-François Marckert
Titre :Modèles de sous arbres aléatoires d'un graphe.
Résumé : Dans cet exposé j'évoquerai https://arxiv.org/abs/2102.08639.
Dans ce travail nous donnons une preuve combinatoire à un résultat dû à Aldous et Broder: lorsqu'on fait une marche aléatoire au plus proche voisin sur un graphe connexe en partant d'un sommet v, l'arbre obtenu en prenant les arêtes du graphe par lesquelles on arrive pour la première fois à chaque sommet différent de v, est un arbre couvrant uniforme (on parlera aussi de l'énoncé plus général, où est identifiée la loi de l'arbre couvrant obtenu si on utilise une chaîne de Markov générale).
Si le temps le permet, je parlerai de https://arxiv.org/abs/2102.12738 dans lequel on discute de modèles de sous arbres aléatoires d'un graphe, et où on a identifié un certain nombre de questions ouvertes.
Travaux en commun avec Luis Fredes