Abstract

The so-called “Tamari order” is the partial ordering on fully-bracketed words induced by a “semi-associative” law (ab)c <= a(bc). Among its many remarkable properties, the order induces a lattice structure on the bracketings of a given word (known as the “Tamari lattice”, or the “rotation lattice of binary trees”), a non-obvious fact that was first proved by Friedman and Tamari in the late 1950s (but published in the late ‘60s).

In this talk, I will describe a new, constructive proof of the lattice property of the Tamari order, which starts from the idea of reconsidering the order as a sequent calculus. Along the way, I will mention connections with the natural notion of “left representable” multicategory recently formulated by Bourke and Lack, as well as some additional motivations coming from the surprising combinatorics of lambda calculus.

(Based on the paper “A sequent calculus for a semi-associative law”, to appear in LMCS . Link: https://arxiv.org/abs/1803.10080.)