2021-2022


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