Annotating Kimmo Eriksson’s Poem

 

“Start counting her NUMBER OF FACES,” Kimmo Eriksson, Brush up your Björner (2008).

The time is right to annotate Kimmo Eriksson’s memorable poem:

1. What are Chip firing games?

Many women will find it admirable
if you tell her she makes your CHIPS FIRABLE.

Chip firing games are (solitary) games played on graphs: each node of a directed graph contains a pile of chips. A move consists of selecting a node with at least as many chips as its outdegree, and sending one chip along each outgoing edge to its neighbors. The remarkable property of these games is that depending on the sizes of the piles, either the game continues forever or it reaches a position where it cannot be played further. In the latter case the final position, the number of moves, and even the number of times each node fired do not depend on the specific moves made along the game.

Sheep firing game (You may play the game by clicking on the picture; disclaimer: we object to cruel treatment of animals)

 In the rest of this post you can read about shellability, weak and strong (Bruhat) partial orders on the set of permutations, chessboard complexes, and more.  

Admiring

2. What is Shellability?

If she’s tough there’s a story that’s tellable
’bout a girl who was tough-shelled but SHELLABLE.

 

Tough

Shellability is a property of cell complexes (simplicial complexes, polyhedral complexes or more general complexes). Such complexes are used to describe topological spaces, and shellability is a combinaorial property (more or less) that guarantees that the described topological space is homehomorphic to a ball or to a sphere.

We say that a d-dimensional pure polyhedral complex is shellable if its maximal faces (facets) can be ordered by a sequence F_1,F_t,\dots ,F_t such that for every k, $1 < k \le t$, the intersection of F_k with the union of F_1,\dots,F_{k-1} is itself homehomorphic to a (d-1)-dimensional ball or sphere.

For simplicial complexes, shellability is especially simple. The intersection of F_k with the preveious facets should be a (non empty) union of some (or all) of its own facets.

I used the word “pure” and this refers to the property of a complex asserting that all maximal faces are of the same dimension. A notion of shellability for non pure complexes was introduced by Michelle Wachs. (It is sometimes called “michellability”).  Mary Ellen Rudin constructed in 1958 a 3-ball  with 14 vertices and 41 tetrahedra which is not shellable.  Frank Lutz found an  example with 9 vertices:

non-shellable

(Click on the picture for a description of Lutz’s model and some more background on shellability.)

The boundary of a convex d-dimensional polytope is homeomorphic to S^{d-1}, a (d-1)-dimensional sphere and has a cellular structure. The boundary of a d-polytope is the union of a collection of facets- faces of dimension (d-1) and each facet is a (d-1)-polytope and thus is homehomorphic to a (d-1)-dimensional ball. Bruggesser and Mani proved that the boundary complexes of d-polytopes are shellable. This was assumed by early 19th century proofs of Euler’s formula before the first rigorous proof by Poincare.

 

3. What are F-vectors?

If she pouts and you’ve fallen from graces,
why, start counting her NUMBER OF FACES.

The f-vector of a d-polytope, or a polyhedral complex, or a CW-complex is the vector (f_0,f_1,\dots ) where f_k is the number of k-dimensional faces. We discussed f-vectors and more general invariants of graded posets in several posts.

 

Start counting her number of faces. French actress Isabelle Huppert is reflected in the picture of herself as she attends the photo exhibition “Woman of Many Faces” in Moscow on June 29, 2008.

4. What are the strong (Bruhat) order and the weak order?

Tell’er straight, if you cannot afford ‘er,
your finances ‘re in WEAK PARTIAL ORDER.

 

“If you cannot efford her”

Although defined over arbitrary Coxeter groups, let me define the strong (Bruhat) order and the weak order for the set of permutations on n letters. Both these orders are partial orders and they can be thought of as analogs of the inclusion orders for subsets of an n element sets.

Every permutation in the group of permutations S_n on \{1,2,\dots,n\} can be written as a product of adjacent transposition, namely, transposition of the form (i,i+1). The height h(\pi ) of a permutation \pi is the minimal number of adjacent transpositions needed. The height is an integer between 0 and {{n} \choose {2}}, and the two partial orders on S_n that we are going to consider – the weak order and the strong order (also called the Bruhat order) are graded by the height. In the weak order a permutation \pi covers a permutation \tau if h( \pi) = h(\tau) +1 and \pi is obtained from \tau by multiplying it with an adjacent transposition. In the strong order a permutation pi covers a permutation \tau if h( \pi) = h(\tau) +1 and \pi is obtained from \tau by multiplying it with an arbitrary transposition.

Both these orders are very interesting. The weak order is a lattice. The strong order is the poset of faces of a regular CW complex homehomorphic to a sphere. In fact, this regular CW complex is shellable.

 

 

 The strong (Bruhat) weak order on S_4

 

Another strong order:

The largest order in the Catholic Church, the Society of Jesus (Jesuits), have elected their 30th Superior-General, Fr Adolfo Nicolás, S.J.,…Joseph Griebovsky wishes him well as he begins his new challenge as General of the 19,126-strong Order

 Update: Here is a recent post on the two orders (with a problem set!) by David Speyer.

5. What are Chessboard complexes?

When you’re fighting the battle of sexes
say that mating, your CHESSBOARD COMPLEX is

Battle of sexes 

The chessboard complex is a simplicial complex defined as follows. The vertices are the squares of an n \times m chessboard. and the faces correspond to positions of non-attacking rooks on the chessboard. For example, if n=2,m=3 our simplicial complex is a hexagon. If n=3 and m=4 we have a 2-dimensional simplicial complex with 12 vertices. It is a triangulation of a torus. When n=4 and m=5 we get 3-dimensional pseudomanifolds with the property that the link of every vertex is the 12-vertex torus.   

 chessboard complex

 Chessboard complex?
 
 

6. Tits Buildings

If your lady-friend still isn’t yielding
say you’ve got this big place: a TITS BUILDING.

 This is a high point of vintage British cinema. Not exactly easy or light viewing, but a film you really should see at least once

For Tits Buildings I refer you to the wikipedia article.

Penduline Tits nest-building in birches by the track (Birdblog)

7. Subspace arrangement

If there still is some source of estrangement
make some cozier SUBSPACE ARRANGEMENT.

 Estrangement?

A Subspace arrangement is a finite collection of linear subspaces in R^n. (And sometimes over other fields.) The case of hyperplane arrangements has been especially studied.

Hyperplane arrangement !

 

Update: Followinf Dave Speyer’s comment I googled search again for the images under “strong (Bruhat) order” and to my surprise, in the sixth place, much before what I was really looking for, I got this.

Does Google personalizes searches and biases them towrads the person who searches? Or do you get it too?

About these ads
This entry was posted in Combinatorics, Poetry and tagged , , , , , , , , , . Bookmark the permalink.

7 Responses to Annotating Kimmo Eriksson’s Poem

  1. Kimmo Eriksson says:

    Thanks, Gil! Anders have always mentioned all these terms but I never understood what they meant before. ;-)

  2. David Speyer says:

    I think that the image labeled “The strong (Bruhat) order on S_4″ is actually a picture of the weak order.

  3. Pingback: A Diameter Problem (6): Abstract Objective Functions « Combinatorics and more

  4. Pingback: Lovasz’s Two Families Theorem « Combinatorics and more

  5. Pingback: Telling a Simple Polytope From its Graph « Combinatorics and more

  6. Pingback: How the g-Conjecture Came About? « Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s