Maximal elements in the Hurwitz graph

Abstract

The Hurwitz graph has as its vertices the maximal chains in the lattice of non-crossing partitions, with an edge between two chains which differ at exactly one place. Adin and Roichman introduced an order on this graph by choosing a base element and showed that the maximal elements are counted by the Catalan numbers. We show that this set of maximal elements is in natural bijection with non-crossing partitions so that the graph structure corresponds to that of the permutahedron, restricted to non-crossing partitions. We use this to compute the diameter of the graph of maximal elements. We also briefly consider the graph obtained by identifying maximal chains with minimal factorizations of a full cycle into transpositions in the symmetric groups and quotienting by commutation relations.