On considère un automate aléatoire à n états, c’est à dire le choix de deux fonctions aléatoires uniformes a,b de [n] dans [n]. Un mot w est dit synchronisant (« reset word ») s’il existe un état v0 dans [n] tel qu’en lisant lettre-à-lettre le mot w depuis n’importe quel état, on arrive à l’état v0. On démontre une conjecture de Kisielewicz, Kowalski, Szykula (2013) selon laquelle, avec proba tendant vers 1, il existe un mot synchronisant de longueur au plus (√n)1+o(1). La meilleure borne connue était quasilinéaire (Nicaud, 2016). Cela repose sur un théorème de structure un peu étonnant qui dit qu’avec grande proba, il existe un mot w très court (de longueur seulement 1.01log(n)) tel que les w-transitions induisent un arbre. J’expliquerai l’heuristique de la preuve et j’en profiterai pour énoncer quelques questions ouvertes sur ces « w-arbres » que nous introduisons, dont notre preuve trop technique est loin de révéler tous les secrets. Travail commun avec Guillem Perarnau (Barcelone), https://arxiv.org/abs/2207.14108.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne