2021-2022


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 )

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