Tamari Lattice

polygon sides

4

5

6

7

graph type

LayeredGraphPlot

GraphPlot

GraphPlot3D

There are multiple ways to parenthesize a sequence of factors two at a time. For instance,

a

,

b

, and

c

can be grouped as either

(a(bc))

or

((ab)c)

; the Catalan numbers count the number of ways this is possible for

n

factors. The groupings form a partially ordered set, where one grouping covers another if the first can be transformed into the second by taking a subelement of the form

x(yz)

and replacing it with

(xy)z

. In these transformations,

x

,

y

, and

z

can be a single factor or a product of factors. These partially ordered sets form a lattice called the Tamari lattice.

This Demonstration shows graphs formed by lattices generated from factor sequences of different lengths, where each vertex label is a polygon triangulation corresponding to a particular grouping of factors.