Treillis de Young-Fibonacci

En mathématiques, et notamment en combinatoire, le graphe de Young-Fibonacci et le treillis de Young-Fibonacci, appelés ainsi d'après Alfred Young et Leonardo Fibonacci, sont deux structures voisines sur des suites composées exclusivement de chiffres 1 et 2.

On appelle rang d'une suite de chiffres la somme de ses chiffres ; par exemple, le rang de 11212 est 1 + 1 + 2 + 1 + 2 = 7.

On démontre ci-dessous que le nombre de suites de rang donné est un nombre de Fibonacci. Le treillis de Young-Fibonacci est le treillis modulaire dont les éléments sont ces suites de chiffres et qui est compatible avec cette structure de rang. Le graphe de Young-Fibonacci est le graphe du diagramme de Hasse de ce treillis, et il a un sommet pour chacune de ces suites de chiffres.

Les graphe et treillis de Young-Fibonacci ont été étudiés initialement dans deux articles de Fomin (1988) et Stanley (1988). Ils sont appelés ainsi à cause de leur étroite parenté avec le treillis de Young, et à cause du lien avec les nombres de Fibonacci.

Une suite de chiffres de rang r est obtenue soit en ajoutant le chiffre 2 à une suite de rang r − 2, soit en ajoutant le chiffre 1 à une suite de rang r − 1. Le nombre de suites de rang r est donc la somme du nombre de suites de rang r − 1 et du nombre de suites de rang r − 2. Notons f(r) le nombre de suites de rang r. On a donc la relation de récurrence f(r) = f(r − 2) + f(r − 1) avec les conditions initiales f(0) = f(1) = 1. Ce sont les nombres de Fibonacci aux conditions initiales près, puisque ${\displaystyle {\mathcal {F}}_{1}={\mathcal {F}}_{2}=1}$; on a donc ${\displaystyle f(r)={\mathcal {F}}_{r+1}}$.

Le graphe de Young-Fibonacci est le graphe infini avec un sommet par suite de chiffres de la forme précédente, y compris la suite vide. Les voisins d'une suite s sont les suites formées, à partir de s, par l'une des opérations :

1. Insertion d'un chiffre « 1 » avant le chiffre « 1 » le plus à gauche de s, ou n'importe où dans s si s ne contient pas de « 1 » ;
2. Changement du chiffre « 1 » le plus à gauche de s en « 2 » ;
3. Suppression du « 1 » le plus à gauche de s ;
4. Changement en « 1 » d'un « 2 » de s qui n'a pas de « 1 » à sa gauche.

Les opérations 3 et 4 sont les inverses des opérations 1 et 2. Les deux premières augmentent le rang, les deux dernières le diminuent. Par exemple, la suite 212 de rang 5 est transformée par la première règles en 2112, de rang 6, puis en 2212, de rang 7, par la deuxième règle. La troisième règle transforme cette suite en 222, et la quatrième en 212 si l'on choisit de remplacer le deuxième « 2 » en « 1 ». Les règles 2 et 3 ne laissent pas de choix sur l'opération, alors que 1 et 4 donnent une certaine liberté.

Le graphe peut être vu comme une graphe orienté. Les arcs sont orientés d'un sommet de rang donné vers un sommet de rang immédiatement supérieur.

Le graphe de Young-Fibonacci a les propriétés suivantes, décrites par Fomin (1988) et Stanley (1988) :

• Le graphe est connexe. Toute suite non vide peut être transformée en une suite de rang inférieur, et il existe donc une séquence de transformations qui la mène jusqu'à la suite vide ; en opérant en sens inverse, on obtient un chemin de la suite vide vers la suite initiale. Toute suite est donc accessible à partir de la suite vide.
• Le graphe est compatible avec la structure de rang, en ce sens que la longueur d'un chemin est égal à la différence des rangs entre son sommet d'arrivée et son sommet de départ.
• Pour deux sommets distincts u et v, le nombre de prédécesseurs (de rang immédiatement inférieur) communs à u et v est égal au nombre de successeurs (de rang immédiatement supérieur) de u et v, et ce nombre est zéro ou un.
• Le degré sortant d'un sommet est égal à 1 plus son degré entrant.

Fomin appelle un graphe avec ces propriétés un graphe en Y; Stanley considère des graphes plus généraux qu'il appelle des differential poset , ce que l'on peut traduire par ensembles ordonnés différentiels. Ces graphes vérifient la propriété plus faible que la différence entre le nombre de prédécesseurs communs et le nombre de successeurs communs de deux sommets et toujours la même mais peut être supérieure à 1.

La relation de descendance du graphe de Young-Fibonacci définit un ordre partiel. Comme montré dans Stanley (1988), deux sommets x et y ont une borne inférieure et une borne supérieure unique, ce qui en fait un treillis, appelé le treillis de Young-Fibonacci.

Pour trouver la borne inférieure de deux sommets x et y, on procède comme suit. On teste d'abord si l'un est descendant de l'autre. Cela se produit exactement lorsque le nombre de « 2 » restant dans y après avoir supprimé le plus long suffixe commun de x et y est au moins aussi grand que le nombre de total de chiffres qui restent de x après avoir supprimé ce suffixe commun. Par exemple, 1121 est un descendant de 11, parce que, après suppression du suffixe commun, 112 contient exactement un « 2 » qui est la longueur de la suite 1. En revanche, 1121 n'est pas descendant de 111. Si aucun des sommets x et y n'est descendant de l'autre et si l'une des deux suites commence par des chiffres « 1 », leur borne inférieure est inchangée si l'on supprime ces chiffres initiaux. Si les deux suites commencent par un « 2 », on trouve la borne inférieure en supprimant dans les deux suites ce chiffre initial, calculant la borne inférieure des suites restantes puis de remettre le « 2 » en tête du résultat. Par exemple, le calcul de la borne inférieure de ${\displaystyle 1121\land 2111}$ mène d'abord à

${\displaystyle 1121\land 2111=21\land 2111}$

par suppression des « 1 » initiaux, puis à

${\displaystyle 1121\land 2111=2(1\land 111)}$

par mise en facteur du « 2 » initial, et comme 1 est antécédent de 111, on a ${\displaystyle 1121\land 2111=21}$.

On peut trouver un ascendant commun à deux sommets x et y, qui ne sera pas nécessairement le plus petit ascendant commun, par une méthode un peu sommaire qui consiste à prendre la suite formé uniquement de « 2 » et dont la longueur est la plus grande des longueurs de x et y. La borne supérieure de x et y est alors l'un des descendants, en nombre fini, de cette suite de « 2 » qui est ascendant à la fois de x et de y.

Stanley observe que le treillis de Young-Fibonacci est texte=modulaire. Fomin, dans son article, affirme que le treillis est distributif, mais il n'en est pas ainsi parce que le treillis contient le sous-treillis en forme de diamant composé des suites {21, 22, 121, 211, 221} qui est interdit dans un treillis distributif.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Young–Fibonacci lattice » (voir la liste des auteurs).
• (en) S. V. Fomin , « Generalized Robinson-Schensted-Knuth correspondence », Journal of Soviet Mathematics, vol. 41, n^o 2,‎ avril 1988, p. 979-991 (DOI 10.1007/BF01247093). Traduction d'un article paru dans Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta imeni V. A. Steklova Akademii Nauk SSSR (LOMI), vol. 155, p. 156-175, 1986.
• (en) Richard P. Stanley, « Differential posets », J. Amer. Math. Soc., vol. 1, n^o 4,‎ 1988, p. 919–961 (DOI 10.2307/1990995, JSTOR 1990995).

• Portail des mathématiques