Posts filed under ‘combinatorics’

Operads in Haskell

Mikael Vejdemo Johansson, who was at the Operads conference in Luminy (which I also attended), wrote in only one week a Haskell module computing Gröbner bases for operads. Nice work !


11 May 2009 at 8:25 pm Leave a comment

Cardboard associahedron

After the dodecahedron comes the cardboard associahedron : it represents the combinatorics of moving parentheses to calculate an associative product of five things step by step. The vertices of the associahedron are thus the 14 different binary trees with 5 leaves.

Associahedron 1

Given four factors, there are exactly five ways of multiplying them using a binary operation: by moving parentheses according to the associativity rule, you go through five different trees in a cyclic way. This is known as MacLane’s pentagon coherence rule, which states that in not too weak notions of monoid, checking coherence for pentagon diagrams ensures that the definition of the product is well-behaved.

8 April 2009 at 12:11 am Leave a comment

Laver tables and “unprovable” statements

Laver tables are combinatorial objets whose definition is surprisingly simple. However, they do have somewhat weird properties, which come from their relationship with questions of set theorists (namely, how do elementary embeddings of models of set theory behave). It also have connections with braid group theory, which I do not know. The Wikipedia article gives the basic facts, a survey by Patrick Dehornoy will give relevant bibliography, and friends of mine wrote an undergraduate thesis on the subject (in French).

The most basic definition of Laver tables is the Cayley table of a self-distributive binary operation. This means we define an exotic operation \star on a set of numbers, and fill a square table with the outcomes of this operation. The required property of this operation is a \star (b \star c) = (a \star b) \star (a \star c). This operation does not share properties with our usual operations, which are often associative of commutative. Suppose the set of numbers is \{0, 1, ..., n-1\} and that 1 acts on the right by shifts : i \star 1 = i+1 and (n-1) \star 1 = 0. (more…)

20 February 2009 at 4:51 pm 4 comments