One-two trees, let’s twist!

Attention: séminaire reporté à juin 2026 !

Il y a fort longtemps (en l’an 2018), dans un bureau fort lointain (le S3-354), le jeune Matthieu Dien et ma modeste personne se sont lancés dans une quête : un problème qui ne prendrait que “10 minutes à résoudre”. Il aura fallu 8 ans, et l’aide du chevaleresque Paul Dorbec, pour qu’un article ait vu le jour et soit publié. Cet exposé célèbrera cet heureux évènement en vous contant l’intérieur de cet article.

De quoi est-il question ? Nous voulions à l’origine étudier les graphes cordaux à treewidth borné. Malgré le nom aux allures terrifiantes, ces familles de graphes apparaissent naturellement dans beaucoup de domaines (en algèbre linéaire numérique, dans les réseaux bayésiens, en philogénétique).

Nous avons commencé par majorer la treewidth à 2, et avons baptisé les graphes en question “1,2-arbres croissants”. Nous nous sommes vite rendus compte que les 1,2-arbres croissants à n sommets étaient comptés par n^{n-2}. Ce nombre pourrait vous sembler familier, puisqu’il s’agit aussi du nombre d’arbres dont les sommets sont étiquetés de 1 jusqu’à n (célèbre résultat dû à Cayley). Notre article montre les connexions entre ces deux familles, tant du point de vue analytique que bijectif.