NONCROSSING DIAGRAMS AND CANONICAL JOIN REPRESENTATIONS

Abstract. We consider two problems that appear at first sight to be unre-lated. The first problem is to count certain diagrams consisting of noncrossing arcs in the plane. The second problem concerns the weak order on the sym-metric group. Each permutation x has a canonical join representation: a unique lowest set of permutations joining to x. The second problem is to de-termine which sets of permutations appear as canonical join representations. The two problems turn out to be closely related because the noncrossing dia-grams provide a combinatorial model for canonical join representations. The same considerations apply more generally to lattice quotients of the weak or-der. Considering quotients produces, for example, a new combinatorial object counted by the Baxter numbers and an analogous new object in bijection with generic rectangulations. 1. Noncrossing diagrams The key objects in this paper are certain diagrams consisting of arcs satisfying certain rules, including the requirement that arcs not cross. Here we call them simply noncrossing diagrams, although this name does not distinguish them from many other objects defined elsewhere. Each diagram begins with n distinct points on a vertical line. We identify the points with the numbers 1,..., n, with 1 at the bottom. Each diagram is consists of some (or no) curves called arcs connecting the points. Each arc must satisfy the following requirement: (A) The arc connects a point p to a strictly higher point q, moving monotone upwards from p to q and passing either to the left or to the right of each point between p and q. The arc may pass to the left of some points and to the right of others. The diagram must also satisfy the following two pairwise compatibility conditions: (C1) No two arcs intersect, except possibly at their endpoints. (C2) No two arcs share the same upper endpoint or the same lower endpoint. Figure 1. Noncrossing diagrams on 3 points Each noncrossing diagram determines some combinatorial data, namely which pairs of points are joined by an arc and which points are left and right of each arc. Tw