Circle and disk as a cell complexes

The circle in its simplest decomposition has one 0-cell (a point) and one 1-cell (an interval).

Figure: Circle

./Chapter1/circle1.eps

This is the only way to form a circle from an interval. If we try to decompose a disk of higher dimension, then we have choices. In the table below we give a few examples of decomposition of an $n$-cell.

0	1	2	...	$n$
./Chapter1/point.eps	./Chapter1/interval.eps	./Chapter1/disk.eps		$n$-cell
./Chapter1/point.eps	./Chapter1/interval.eps	./Chapter1/globular.eps		globular set
./Chapter1/point.eps	./Chapter1/interval.eps	./Chapter1/2simplex.eps		$n$-simplex
./Chapter1/point.eps	./Chapter1/interval.eps	./Chapter1/2cube.eps		$n$-cube
./Chapter1/point.eps	./Chapter1/interval.eps	./Chapter1/2associahedron.eps		$n$-associahedron
./Chapter1/point.eps	./Chapter1/interval.eps	./Chapter1/2permutohedron.eps		$n$-permutohedron

The construction of an $n$-associahedron can be given by the use of Stasheff complex. Its vertices are defined to be all ways of putting parentheses to a word of length $(n+1)$. They are in bijection with the set of planar binary rooted trees as we can see on example of words of length 3 and 4.

$((x_1x_2)x_3)$	$(x_1(x_2x_3))$
./Chapter1/tree3_1.eps	./Chapter1/tree3_2.eps

There is a partial order on trees in which first tree on the picture is before the second one. This can be generalized for the trees with more leaves, and is called the Tamari order.

$(((x_1x_2)x_3)x_4)$	$(x_1(x_2(x_3x_4)))$
./Chapter1/tree4_1.eps	./Chapter1/tree4_2.eps

We can associate a tree to each vertex of a 2-assciahedron and order them using the ordering on trees.

The realization of the Stasheff polytope as a subset in $\bR^n$ is homeomorphic to a ball. To each planar binary tree $t$ we associate a point $M(t)=(x_1, \hdots, x_n)$ in $\bR^n$ as follows. The $i$-th coordinate is the product of the number of leaves to the left of $i$-th vertex times the number of leaves to the right.

Figure: Tree $t$

./Chapter1/tree5_1.eps

$$M(t)=(1\cdot 1, 2\cdot 1, 3\cdot 2, 1\cdot 1)=(1,2,6,1)\in\bR^4$$

The Stasheff polytope of dimension $n$ is the convex hull of the points $M(t)$ for all planar binary tree with $(n+1)$ leaves. The sum of coordinates is

$$\sum_{i=1}^n x_i =\frac{n(n+1)}{2}$$

so the Stasheff polytope lies in the hyperplane given by this equation. The examples of Stasheff polytopes $\sK^1$ and $\sK^2$ are in the following pictures.

./Chapter1/Stasheff2.eps

./Chapter1/Stasheff3.eps

The Stasheff polytope $\sK^3$ has 14 vertices and 7 faces. The faces are three squares and four pentagons (2-associahedrons). In general, the Stasheff polytope $\sK^n$ has faces of the form $\sK^p\times \sK^q$, where $p+q=n$.

What about the permutohedron? Take an element $\sg$ in the symmetric group $S_n$. Associate to it the point $M(\sg)=(\sg(1), \hdots, \sg(n))\in\bR^n$. Then we have permutohedron $\sP^{n-1}$ as a convex hull of all points $M(\sg)$ for all permutations. Of course $\sum_{i=1}^n \sg(i)=\frac{n(n+1)}{2}$, so it lies in the hyperplane given by the equation $\sum_{i=1}^n x_i=\frac{n(n+1)}{2}$.

Figure: 2-permutohedron

./Chapter1/permutohedron.eps

In general $\sP^n$ has faces of the form $\sP^p\times\sP^q$, where $p+q=n-1$.

Observe that we have an order on vertices of our complexes.

./Chapter1/disk_order.eps	./Chapter1/globular_order.eps	./Chapter1/2simplex_order.eps
./Chapter1/2cube_order.eps	./Chapter1/2associahedron_order.eps	./Chapter1/2permutohedron_order.eps

On the set of vertices of $n$-simplex the order comes from the order on natural numbers, because vertices are numbered from 0 to $n$.

On the set of vertices $n$-associahedron the order is called the Tamari order.

Figure: Tamari order on trees

./Chapter1/Tamari.eps

On $n$-permutohedrons the order comes from the weak Bruhat order on the symmetric group $S_n$.