2021-2022


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