OMM01
PRELIMINAIRES
Ils trouvent une interpr´etation combinatoire de cette s´equence en termes d’arbres planaires ´etiquet´es. Cependant, comme l’a remarqu´e Josuat-Verg`es dans [JV15], les polynˆomes de Ramanujan sont aussi li´es aux arbres de Greg. Originairement d´efinis par Flight dans [Fli90] afin de mod´eliser les arbres g´en´ealogiques de manuscrits, les arbres de Greg sont des arbres avec deux types de sommets, des sommets ´etiquet´es, et des sommets non ´etiquet´es dont le degr´e vaut au moins trois.
Notre but dans ce chapitre est de trouver un lien entre Qn, les arbres de Greg et les arbres de Cayley, et donner une nouvelle expression de Qn avec les statistiques de ces arbres. Dans la Section III.2, on introduit les diff´erentes notions et d´efinitions n´ecessaires pour ce chapitre, en particulier on d´efinit la s´equence polynˆomiale Rn qui sera la cl´e de voˆute de notre raisonnement. Dans la Section III.3, on exprime Rn en fonction de diff´erentes statistiques des arbres de Greg, en utilisant une formule de r´ecurrence sur Rn. La Section III.4 fera un apart´e sur les nombres de Ward, qui apparaissent naturellement dans Rn. La Section III.5 pr´esente une interpr´etation de Rn avec les arbres de Cayley, mais cette fois en construisant une bijection entre les arbres de Greg et les arbres de Cayley. Enfin dans la Section III.6 on reviendra au lien avec Qn, en construisant une bijection entre les arbres de Cayley et les arbres planaires ´etiquet´es.
Preliminaires
Un arbre de Cayley est un arbre `a n sommets ´etiquet´es sur [n], tel que deux sommets n’ont pas la ˆeme ´etiquette. Soit Cn l’ensemble des arbres de Cayley de taille n enracin´es en 1, la formule de Cayley nous donne que |Cn| = n n−2 . Un arbre planaire est un arbre enracin´e ´etiquet´e dans lequel les enfants de chaque sommet sont ordonn´es. On note On l’ensemble des arbres planaires enracin´es en 1 et ´etiquet´es sur [n]. La d´efinition suivante, pos´ee par Flight dans [Fli90], nous d´ecrit une g´en´eralisation int´eressante des arbres de Cayley.
D´efinition III.2.1 (Flight, [Fli90]). Soit n ≥ 1. Un arbre de Greg de taille n est un arbre tel que exactement n de ses sommets sont ´etiquet´es sur [n], et les sommets non ´etiquet´es sont de degr´e au moins 3.
On note Gn l’ensemble des arbres de Greg de taille n enracin´es en 1. On pose unl(T) le nombre de sommets non ´etiquet´es de T ∈ Gn. Si unl(T) = 0, alors T ∈ Cn. Voir Figure III.2.1 pour un exemple d’arbre de Greg.
Pour un arbre ´etiquet´e T, en particulier pour les arbres de Greg, il est utile d’introduire λT la fonction d’´etiquetage de T, qui `a un sommet de T associe son ´etiquette. On choisit comme convention que λT n’est pas d´efini sur les sommets non ´etiquet´es d’un arbre de Greg.
Comme tous les arbres que nous ´etudions sont enracin´es, on utilisera une notation orient´ee pour les arˆetes : si (i, j) est une arˆete de T, alors i est le parent de j.
Dans une preuve alternative de la formule de Cayley [Sho95], Shor introduit une cat´egorisation int´eressante des arˆetes dans un arbre de Cayley, qui peut se g´en´eraliser aux arbres de Greg.
Definition III.2.3. Soit T ∈ On.
— Soit j un sommet de T. On dit que j est ancien s’il a un fr`ere k `a sa droite qui v´erifie βT (k) < βT (j). Sinon, on dit que j est jeune. Soit youngT (i) le nombre de fils jeunes de i dans T, et eld(T) le nombre de sommets anciens de T.
— Soit e = (i, j) une arˆete de T. On dit que e est une arˆete impropre, ou que j est un enfant impropre de i, si j est un enfant jeune de i, et λT (i) > βT (j). Sinon, e est une arˆete appropri´ee, et j est un enfant appropri´e de i.
Un exemple d’arbre planaire, avec ses arˆetes impropres doubl´ees, est montr´e dans la Figure III.2.2. Quelque soit la nature de T, on note impe(T) le nombre d’arˆetes impropres de T. On remarque que si T est un arbre planaire sans enfant ancien, l’ordre des enfants est donn´e par ordre croissant de valeurs de βT . Dans ce cas, les arˆetes impropres sont les mˆemes que si on retirait l’ordre sur les enfants de T pour obtenir un arbre de Cayley. Les deux d´efinitions co¨ıncident donc bien sur les arbres de Cayley.
Enfin, on peut ´etendre la d´efinition d’impropre aux sommets, qui exprime si le sommet a des arˆetes impropres sortantes ou non.
D´efinition III.2.4. On dit qu’un parent i est appropri´e s’il n’a pas d’enfant impropre. Sinon on dit que i est un parent impropre. De mani`ere ´equivalente, un sommet i est un parent impropre si et seulement si il est ´etiquet´e, et βT (i) 6= λT (i). On note impp(T) le nombre de parents impropres de T.
Definition III.2.9
D´efinir Rn nous permet de construire un interm´ediaire entre Hn et Qn. En effet, la suite Rn est d´efinie de sorte `a g´en´eraliser Hn, on a Rn(1, y, 1, 1) = Hn(y). Cette nouvelle suite de polynˆomes v´erifie des propri´et´es remarquables, par exemple on trouve que Rn+1(0, y, 0, 1) = (2n − 1)!!(y + 1)n , et que Rn(0, y, 0, 0) donne la suite des nombres de Ward, dont la s´equence est A134991. Cette derni`ere propri´et´e sera expliqu´ee plus en d´etails dans la Section III.4.
Avant de terminer cette section, on souhaite introduire une derni`ere statistique sur les arbres. D´efinition III.2.10. Soit T un arbre de Greg ou de Cayley. Soit i un sommet ´etiquet´e de T. Soit L(i) = (1 = a0, a1, . . . , ak = i) le seul chemin dans T partant de la racine 1 et arrivant en i. On d´efinit le chemin des grands ancˆetres de i, not´e gap(i) = (ap, ap+1, . . . , i), le plus long chemin dans T inclus dans L(i) et contenant i tel que, pour tout sommet ´etiquet´e j ∈ gap(i), λT (j) ≥ λT (i).
Lien avec les nombres de Ward
Comme remarqu´e pr´ec´edemment, la s´equence de polynˆomes Rn(0, y, 0, 0) est `a coefficients positifs, et donne le triangle des nombres de Ward A134991 (Table III.2).
Tout d’abord, cela signifie que Qn(0, y + 1, 0, −1) est `a coefficients positifs, ce qui n’est pas ´evident `a partir de sa caract´erisation dans le Th´eor`eme III.2.5. Cette s´equence de nombres peut s’interpr´eter comme le nombre de faces dans l’espace des arbres
phylog´en´etiques, notion introduite par Billera, Holmes et Vogtmann dans [BHV01]. Il a ´et´e prouv´e par Speyer and Sturmfels [SS04] que cet espace est aussi la Grassmannienne tropicale des lignes G2,n. Pour plus d’informations sur la Grassmannienne et la g´eom´etrie tropicale, voir [Pin98, Stu02]. On introduit d’abord quelques d´efinitions. Semi-anneau tropical
D´efinition III.4.1. Un semi-anneau (R, +, .) est un ensemble dot´e d’un z´ero 0R et d’une unit´e 1R, tel que
— R est un mono¨ıde commutatif pour l’addition +, avec 0R comme neutre,
— R est un mono¨ıde pour la multiplication ., avec 1R comme neutre,
— La multiplication est distributive sur l’addition, c’est-`a-dire, pour tout a, b, c dans R,
L’espace des arbres phylogenetiques
On s’int´eresse maintenant `a l’espace des arbres phylog´en´etiques mentionn´es dans le Th´eor`eme III.4.2 pour comprendre le lien avec les arbres de Greg. Son complexe simplicial Tn est ´etudi´e en d´etails dans [BHV01], et se d´efinit de la fa¸con suivante. Son ensemble de sommets Vert(Tn) contient toutes les paires non ordonn´ees {A, B} o`u A et B forment une partition de [n], et sont tous deux de taille au moins 2. On note que la cardinalit´e de Vert(Tn) est 2n−1−n−1. Deux sommets {A, B} et {A 0 , B0 } sont connect´es par une arˆete si et seulement si.
Une bijection pour les arbres de Cayley
On donne maintenant une nouvelle interpr´etation de Rn, qui se base alors sur les arbres de Cayley. La preuve se base sur le th´eor`eme pr´ec´edent, et construit une bijection entre les arbres de Greg et les arbres de Cayley qui conserve les statistiques qui nous int´eressent. Ce th´eor`eme est une g´en´eralisation de la deuxi`eme ´egalit´e de la Proposition III.2.8.
Télécharger le document complet
