2021-2022


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.

Transparents Enregistrement


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.

Transparents Enregistrement


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.

Transparents Enregistrement


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.

Transparents Enregistrement


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.

Enregistrement


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.

Transparents, Enregistrement


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

Transparents, Enregistrement


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.

Enregistrement


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.

Enregistrement


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.

Transparents, Enregistrement


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.

Enregistrement


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é).

Enregistrement


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)

Enregistrement


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.

Transparents, Enregistrement


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

Transparents, Enregistrement


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

Enregistrement


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 )

Transparents, Enregistrement


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.

Enregistrement


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

Enregistement | Transparents


Français English

Groupe

Événements

GT

* Années précédentes

Ressources

edit SideBar