Tags: #definition

Fibonacci's lattice

The Fibonacci's lattice is a differential poset that is created as follows:

Iterative construction

• Add $\hat{0}$ at the bottom for the unique minimal element
• At the top rank, for each pair of nodes, draw as many vertices connected on top of it as there are below.
• For each node, add one node above it so that the number of elements covering it is one more than the number of elements that it covers
  In other words, we create this lattice by adding elements to ensure that it satisfies that it is a differential poset.

Tilings with dominos

Each of the elements in the lattice corresponds to a tiling of a $2\times n$ strip (where $n$ is the rank) with $1\times 2$ dominos.
Equivalently, these are compositions (note that order matters) of $n$ with parts of size 1 or 2.

The covering relations are described as follows: Suppose we are at layer $n$ and are constructing layer $n+1$.

• Write an element for each element of layer $n-1$, reflecting the relations across $n$, and append a 2 to the end of each of these compositions.
• For each element in the $n$th layer, add one more element covering it above by adding 1 to the end of that element
  See example below

Properties

• the rank numbers are the Fibonacci numbers $f_{n+1}$ (since it starts at $r_1=1,r_2=1$)
  • Note that for any composition of $n$, the last part is either 1 or 2, and removing it yields a composition of $n-1$ or $n-2$ respectively. Thus, $F_n=F_{n-1}+F_{n-2}$.

Examples