Young–Fibonacci lattice

The Young–Fibonacci graph, the Hasse diagram of the Young–Fibonacci lattice.

In mathematics, the Young–Fibonacci graph and Young–Fibonacci lattice are two closely related structures involving sequences of the digits 1 and 2. Any digit sequence of this type can be assigned a rank, the sum of its digits: for instance, the rank of 11212 is 1+1+2+1+2 = 7. As was already known in ancient India, the number of sequences with a given rank is a Fibonacci number. The Young–Fibonacci lattice is an infinite modular lattice compatible with this rank structure, and the Young–Fibonacci graph is the graph of this lattice.

The Young–Fibonacci graph and the Young–Fibonacci lattice were both initially studied in two papers by Fomin (1988) and Stanley (1988). It is named after the closely related Young's lattice and the Fibonacci number of its elements at any given rank.

Graphs of digit sequences

The Young–Fibonacci graph is an infinite graph, with a vertex for each string of the digits “1” and “2” (including the empty string). The neighbors of a string s are the strings formed from s by the following operations:

1. Insert a “1” into s, prior to the leftmost “1” (or anywhere in s if it does not already contain a “1”).
2. Change the leftmost “1” of s into a “2”.
3. Remove the leftmost “1” from s.
4. Change a “2” that does not have a “1” to the left of it into a “1”.

It is straightforward to verify that each operation can be inverted, so the resulting graph may be considered to be undirected. However, it is usually considered to be a directed acyclic graph in which each edge connects from a vertex of lower rank to a vertex of higher rank.

As both Fomin (1988) and Stanley (1988) observe, this graph has the following properties:

• It is connected: any nonempty string may have its rank reduced by some operation, so there is a sequence of operations leading from it to the empty string, reversing which gives a directed path in the graph from the empty string to every other vertex.
• It is compatible with the rank structure: every directed path has length equal to the difference in ranks of its endpoints.
• For every two nodes u and v, the number of common immediate predecessors of u and v equals the number of common immediate successors of u and v; this number is either zero or one.
• The out-degree of every vertex equals one plus its in-degree.

Fomin (1988) calls a graph with these properties a Y-graph; Stanley (1988) calls a graph with a weaker version of these properties (in which the numbers of common predecessors and common successors of any pair of nodes must be equal but may be greater than one) the graph of a differential poset.

Partial order and lattice structure

The transitive closure of the Young–Fibonacci graph is a partial order. As Stanley (1988) shows, any two vertices x and y have a unique greatest common predecessor in this order (their meet) and a unique least common successor (their join); thus, this order is a lattice, called the Young–Fibonacci lattice.

To find the meet of x and y, one may first test whether one of x and y is a predecessor of the other. A string x is a predecessor of another string y in this order exactly when the number of “2” digits remaining in y, after removing the longest common suffix of x and y, is at least as large as the number of digits remaining in x after removing the common suffix. In this case, the meet is whichever of x and y is the predecessor. In a second case, if neither x nor y is the predecessor of the other, but one or both of them begins with a “1” digit, the meet is unchanged if these initial digits are removed. And finally, if both x and y begin with the digit “2”, the meet of x and y may be found by removing this digit from both of them, finding the meet of the resulting suffixes, and adding the “2” back to the start.

A common successor of x and y (though not necessarily the least common successor) may be found by taking a string of “2” digits with length equal to the longer of x and y. The least common successor is then the meet of the finitely many strings that are common successors of x and y and predecessors of this string of “2”s.

As Stanley (1988) further observes, the Young–Fibonacci lattice is modular. Fomin (1988) incorrectly claims that it is distributive; the sublattice formed by the strings {21,22,121,211,221} forms a diamond sublattice, forbidden in distributive lattices.

References

• Fomin, S. V. (1988), "Generalized Robinson-Schensted-Knuth correspondence", Journal of Mathematical Sciences, 41 (2): 979–991, doi:10.1007/BF01247093. Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR 155: 156–175, 1986.

• Stanley, Richard P. (1988), "Differential posets", Journal of the American Mathematical Society, 1 (4): 919–961.