\documentclass[12pt]{amsart}
\usepackage{graphics,amssymb,amscd,amsthm,verbatim,psfrag}
\textwidth15.6cm
\textheight22.8cm
\hoffset-2truecm
\voffset-.5truecm
\usepackage{graphics,verbatim}
\newtheorem{proposition}{Proposition}[section]
\newtheorem{theorem}[proposition]{Theorem}
\newtheorem{corollary}[proposition]{Corollary}
\newtheorem{lemma}[proposition]{Lemma}
\newtheorem{prop}[proposition]{Proposition}
\newtheorem{cor}[proposition]{Corollary}
\theoremstyle{definition}
\newtheorem{example}[proposition]{Example}
\newtheorem{definition}[proposition]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[proposition]{Remark}
\newtheorem{question}{Question}
\newtheorem{nc_criterion}{Noncrossing Criterion}
\newtheorem{cl_criterion}{Compatibility Criterion}
\newcommand{\vv}{{\bf v}}
\newcommand{\xx}{{\bf x}}
\newcommand{\yy}{{\bf y}}
\newcommand{\naturals}{\mathbb N}
\newcommand{\sphere}{\mathbb S}
\newcommand{\integers}{\mathbb Z}
\newcommand{\rationals}{\mathbb Q}
\newcommand{\reals}{\mathbb R}
\newcommand{\complexes}{\mathbb C}
\newcommand{\dimens}{\mathrm{dim}}
\newcommand{\fix}{\operatorname{fix}}
\newcommand{\La}{\operatorname{L}}
\newcommand{\NC}{\operatorname{NC}}
\newcommand{\M}{\operatorname{M}}
\newcommand{\covers}{{\,\,\,\cdot\!\!\!\! >\,\,}}
\newcommand{\covered}{{\,\,<\!\!\!\!\cdot\,\,\,}}
\newcommand{\rank}{{\mathrm{rank}}}
\newcommand{\0}{{\hat{0}}}
\newcommand{\1}{{\hat{1}}}
\newcommand{\set}[1]{{\left\lbrace #1 \right\rbrace}}
\newcommand{\coef}[2]{{\left\langle #1| #2 \right\rangle}}
\newcommand{\join}{\vee}
\newcommand{\meet}{\wedge}
\newcommand{\Span}{\mathrm{Span}}
\newcommand{\mapname}[1]{\stackrel{#1}{\longrightarrow}}
\newcommand{\ep}{\varepsilon}
\newcommand{\br}[1]{\langle #1 \rangle}
\newcommand{\Cat}{\mathbf{Cat}}
\newcommand{\Pge}{{\Phi_{\ge -1}}}
\newcommand{\ck}{^\vee}
\newcommand{\figpage}[1]{
\special{#1}
\special{ps: /pageforpagesdotps exch def}
}
\begin{document}
\title[The Coxeter plane]{Noncrossing partitions, clusters and the Coxeter plane}
\author{Nathan Reading}
\address{
Department of Mathematics, North Carolina State University, Raleigh, North Carolina 27695-8205, USA}
\thanks{This project began while the author was partially supported by NSF grant DMS-0202430 and was completed while the author was partially supported by NSA grant H98230-09-1-0056.}
\email{nathan\_reading@ncsu.edu}
\urladdr{http://www4.ncsu.edu/$\sim$nreadin}
\subjclass[2000]{Primary 20F55; Secondary 05A18}
\keywords{associahedron, cluster, noncrossing partition, Coxeter plane, $W$-Catalan number}
\begin{abstract}
When $W$ is a finite Coxeter group of classical type ($A$, $B$, or $D$), noncrossing partitions associated to $W$ and compatibility of almost positive roots in the associated root system are known to be modeled by certain planar diagrams.
We show how the classical-type constructions of planar diagrams arise uniformly from projections of small $W$-orbits to the \emph{Coxeter plane}.
When the construction is applied beyond the classical cases, simple criteria are apparent for noncrossing and for compatibility for $W$ of types $H_3$ and $I_2(m)$ and less simple criteria can be found for compatibility in types $E_6$, $F_4$ and $H_4$.
Our construction also explains why simple combinatorial models are elusive in the larger exceptional types.
\end{abstract}
\maketitle
\setcounter{tocdepth}{2}
%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 63 \rms (2010), Article~B63b\hfill}
\def\thepage{}
\section{Introduction}\label{intro}
\subsection{$W$-Catalan combinatorics}
The ``classical'' noncrossing partitions are set partitions $\Pi$ of $[n+1]:=\set{1,2,\ldots n+1}$ such that when the elements of $[n+1]$ are placed in cyclic order on a circle, the convex hulls of the blocks of $\Pi$ are disjoint.
Thus, for example, every partition of $[4]$ is noncrossing except $\set{\set{1,3},\set{2,4}}$, which is ``crossing'' because the line segment defined by $\set{1,3}$ intersects the line segment defined by $\set{2,4}$.
Noncrossing partitions were first studied by Kreweras~\cite{Kreweras} in 1972 and since then their rich combinatorial and enumerative structure has been widely studied. (Surveys include \cite[Chapter~4]{Armstrong} and~\cite{Simion}.)
Noncrossing partitions are counted by the Catalan number.
Recently, through the merger of lines of research in algebraic combinatorics~\cite{Ath-Rei,Reiner} and geometric group theory~\cite{Bessis,Biane,Bra-Wa} it became apparent that the classical noncrossing partitions are a special case (the case $W=S_{n+1}$) of a construction valid for any finite Coxeter group~$W.$
The $W$-noncrossing partitions are counted by the $W$-Catalan number $\Cat(W)$.
The general definition of noncrossing partitions is not phrased in terms of planar diagrams.
Rather, the parabolic subgroups of $W$ play the part of partitions, and an algebraic construction produces a set of parabolic subgroups which are to be considered ``noncrossing.''
When $W$ is the symmetric group, drawing the set partitions in the plane as described above, the noncrossing criterion of Kreweras and the algebraic criterion agree.
Similarly, when~$W$ is one of the other classical finite Coxeter groups ($B_n$ or $D_n$) there exist planar diagrams which can be used to determine whether a parabolic subgroup is crossing or noncrossing.
Another set of objects counted by the Catalan number has also recently been generalized to the context of finite Coxeter groups: triangulations of a convex polygon.
Fomin and Zelevinsky~\cite{ga} showed that a \emph{cluster algebra} satisfies a certain finiteness condition if and only if the underlying combinatorics of the cluster algebra is governed by a finite Coxeter group~$W$ (or more precisely, a finite crystallographic root system associated to~$W$).
The combinatorial structure of the cluster algebra is a simplicial complex whose vertex set is a subset (the \emph{almost positive roots}) of the root system.
The facets of the complex are \emph{clusters}: sets of almost positive roots that are pairwise ``compatible.''
The complex is dual to a simple polytope called the generalized associahedron.
The number of clusters, or equivalently the number of vertices of the generalized associahedron, is $\Cat(W)$.
%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL NATHAN READING}{\SMALL THE COXETER PLANE}
%
%
When~$W$ is the symmetric group, the almost positive roots can be put in bijection with the diagonals of a convex polygon such that two almost positive roots are compatible if and only if the corresponding diagonals do not cross.
Thus a maximal set of compatible roots (or \emph{cluster}) corresponds to a maximal set of noncrossing diagonals of a polygon.
The latter is equivalent to a triangulation of the polygon.
When~$W$ is a Coxeter group of type $B_n$ or $D_n$, there are planar models which encode compatibility and which are only slightly more complicated.
Both the generalized associahedron and the noncrossing partition lattice have natural dihedral symmetry.
The planar models in types $A$, $B$ and $D$ realize these symmetries as dihedral symmetries acting geometrically on the plane.
\subsection{The main construction}\label{intro main}
This paper explains the planar diagrams in types $A$, $B$, and $D$ by giving a Coxeter-theoretically uniform construction of planar diagrams for parabolic subgroups and for almost-positive roots.
To the extent possible, we also give criteria for noncrossing and for compatibility (but not compatibility degree) in other types.
We also suggest a simple explanation for why planar diagrams are easy in types $A$, $B$, and $D$, but problematic in many exceptional types.
The definitions of clusters and noncrossing partitions involve the choice of a \emph{Coxeter element} for~$W$:
an element of~$W$ which can be expressed as the product of some permutation of the set $S$ of simple generators of~$W.$
The order of a Coxeter element is the \emph{Coxeter number} $h$ of~$W$ and the \emph{exponents} $e_1,\ldots,e_n$ of~$W$ are certain integers that can be read off from the eigenvalues of a Coxeter element.
(The Coxeter number and exponents are well-defined because any two Coxeter elements are conjugate in~$W.$)
The $W$-Catalan number is given by
\[\Cat(W)=\prod_{i=1}^n\frac{e_i+h+1}{e_i+1}.\]
The properties of Coxeter elements are closely tied to a certain ($2$-dimensional) plane $P$ which we call the \emph{Coxeter plane}, and which was first considered in generality by Coxeter~\cite{RegPoly}.
A careful analysis of the Coxeter plane by Steinberg~\cite{Steinberg} provided the first uniform proofs of the key properties of Coxeter elements.
Our construction begins with orthogonal projections of a small $W$-orbit $o$ to the Coxeter plane.
Each parabolic subgroup $W'$ defines a partition of $o$ into $W'$-orbits.
The diagram for $W'$ is essentially this partition of $o$, projected to $P$.
The planar models for almost positive roots are obtained by altering the projected orbits, which have dihedral symmetry of order $2h$, to obtain a diagram with dihedral symmetry of order $2(h+2)$.
Once planar diagrams are constructed, it remains to find criteria for reading off, from the diagrams, whether a parabolic subgroup is noncrossing, or whether a pair of roots is compatible.
We give simple criteria for noncrossing and for compatibility for $W$ of types $H_3$ and $I_2(m)$, and slightly more complicated criteria for compatibility in types $E_6$, $F_4$ and $H_4$.
Although a uniform criterion for compatibility in all types remains elusive, the diagrams we construct for almost positive roots seem to come very close to having a uniform criterion.
Indeed, small \textit{ad hoc} alterations of the diagrams in the remaining types $E_6$, $E_7$, $E_8$ $F_4$, and $H_4$ produce a complete model for compatibility, with the simplest possible criterion.
The approach via the Coxeter plane indicates that the classical finite Coxeter groups (and now types $H_3$ and $I_2(m)$) admit simple criteria for noncrossing and for compatibility precisely because they admit small orbits.
In this context, a ``small'' orbit is an orbit whose size is approximately the Coxeter number $h$.
The groups of type $A_n$, $B_n$, $I_2(m)$, $D_n$, and $H_3$ each possess an orbit of size $h$ or $h+2$, while the remaining groups $F_4$, $E_6$, $E_7$, $H_4$, and $E_8$ have orbits of sizes $2h$, $2h+3$, $3h+2$, $4h$, and $8h$, respectively.
The intrinsic complexity of the diagrams unavoidably increases when the size of the orbit is much greater than $h$.
It is well-known that the property of having small orbits is also responsible for the combinatorial models which realize the classical groups as various groups of permutations, by letting the group act as permutations of a small orbit.
However, in this latter context, a ``small'' orbit is one whose size is a small integer multiple of the rank of the Coxeter group.
\subsection{Computer-generated diagrams}\label{computer}
Postscript files, showing the results of the main construction for many finite
Coxeter groups, are available with this paper on the website of the S\'eminaire
Lotharingien de Combinatoire.
The figures were made with the help of John Stembridge's \texttt{coxeter} and \texttt{weyl} maple packages and PostScript drawing routines developed by the author.
The files are optimized for small file size as PostScript files, by taking advantage of the fact that PostScript is a complete programming language.
The author recommends viewing the files (or at least those files associated with the larger exceptional groups) with a PostScript viewer that interprets PostScript directly, rather than converting to PDF.
File sizes in PDF will be up to about 350 times larger than the postscript files.
Each file for parabolic subgroup diagrams (e.g.\ \texttt{e6nc.ps}) displays one representative from each symmetry class of diagram, labels the parabolic subgroup as crossing or noncrossing, and gives a list of the reflections generating the parabolic subgroup.
The blocks in the partitions represented are indicated by line segments connecting pairs of points related by a reflection in the parabolic subgroup.
The blocks are also indicated by colors of vertices, with black points representing singleton blocks.
Colors of multiple points at the origin can be determined from the segments, keeping in mind that there are no degenerate segments connecting different points at the origin.
The reflections are numbered according to the numbering of positive roots in Stembridge's packages.
The noncrossing parabolic subgroups are identified by computer, via a bijection defined in~\cite[Section~6]{sortable} (see also \cite[Theorem~8.9]{typefree}) from \emph{sortable elements} to noncrossing parabolic subgroups.
Each file for diagrams of almost positive roots (e.g.\ \texttt{e6cl.ps}) pictures diagrams for pairs of almost positive roots $(\alpha,\beta)$, where $\alpha$ ranges over all negative simple roots and $\beta$ ranges over all almost positive roots.
Each diagram is a collection of line segments, labeled as necessary by which of the multiple origin points is an endpoint of the segment.
The labeling of segments is given in the diagram files by coloring the segments.
In Section~\ref{cl diag}, descriptions are given of \textit{ad hoc} alterations to the almost positive root diagrams in some types.
These altered diagrams are also available, e.g.\ as \texttt{e6cl\_alt.ps}.
\subsection{Outline of the paper}
The remainder of the paper proceeds as follows.
In Section~\ref{orb sec}, we give background on crossing and noncrossing parabolic subgroups, relate these to partitions of a $W$-orbit, and describe the construction of Coxeter-planar diagrams for parabolic subgroups.
In Section~\ref{nc sec} we show that in the classical types, our construction of planar diagrams for partitions leads to the usual planar models for crossing/noncrossing partitions, and discuss how the construction works out in other types.
In Section~\ref{cl sec} we review the definition of compatibility and describe the usual models for compatibility in the classical types, in preparation for the development, in Section~\ref{root diag}, of a uniform construction of diagrams for almost positive roots.
Finally, in Section~\ref{cl diag}, we show that the construction recovers the classical planar diagrams, and discuss compatibility criteria in other types.
\section{Parabolic subgroups and partitions of orbits}\label{orb sec}
In this section we discuss crossing and noncrossing parabolic subgroups.
We introduce the notion of partitions of an orbit and describe how to obtain planar diagrams for parabolic subgroups by projecting partitions of an orbit to the Coxeter plane.
\subsection{Parabolic subgroups}
We assume basic background on Coxeter groups and root systems, including the classification of finite Coxeter groups.
This background can be found, for example, in~\cite{Bj-Br,Bourbaki,Humphreys}.
Throughout the paper, $(W,S)$ will stand for a finite Coxeter system of rank $n=|S|$.
For $s_1,s_2\in S$, the order of $s_1s_2$ will be denoted by $m(s_1,s_2)$.
We fix a representation of~$W$ as a real reflection group on a Euclidean space $V$, and make no distinction between
elements of~$W$ and their action on $V$.
We also assume that the only element fixed by $W$ is the origin.
This implies in particular that the dimension of $V$ equals the rank of $W$.
The set of elements of $W$ which act as reflections is $T=\set{wsw^{-1}:s\in S, w\in W}$.
For each $t\in T$, let $H_t$ be the reflecting hyperplane associated to $t$.
The collection $\set{H_t:t\in T}$ is called the \emph{Coxeter arrangement} associated to $W$.
Throughout the paper, we will assume that $W$ is \emph{irreducible}, meaning that $W$ cannot be written as a direct product of Coxeter systems of strictly lower rank.
Equivalently, we require that the diagram of $W$ be connected as a graph.
The constructions of this paper rely, in two major ways, on the assumption that $W$ is irreducible.
First, the assumption of irreducibility, together with the assumption that $W$ fixes only the origin, implies that the linear span of any nontrivial orbit is $V$.
Second, the assumption of irreducibility is essential to the construction of the Coxeter plane.
For any $J\subseteq S$, the subgroup $W_J$ generated by $J$ is called a \emph{standard parabolic subgroup}.
More generally, a \emph{parabolic subgroup} is any subgroup which is conjugate in $W$ to a standard parabolic subgroup.
The \emph{rank} of a parabolic subgroup $W'$ is $|J|$, where $W_J$ is some standard parabolic subgroup conjugate to $W'$.
The parabolic subgroups of the symmetric group $S_{n+1}$ (the Coxeter group of type $A_n$) are exactly the subgroups~$W'$ generated by transpositions.
Such a subgroup~$W'$ decomposes the set $[n+1]$ into $W'$-orbits.
On the other hand, to each set partition $\Pi$ of $[n+1]$, one can associate the parabolic subgroup~$W'$ generated by transpositions $(i\,\,j)$ such that $i$ and $j$ are in the same block of $\Pi$.
Thus for an arbitrary finite Coxeter group $W,$ one may think of the parabolic subgroups of $W$ as a $W$-analog of partitions.
Another way to think of set partitions of $[n+1]$ is as subspaces in the intersection lattice of the Coxeter arrangement associated to $S_{n+1}$.
The Coxeter arrangement for the usual reflection representation of $S_{n+1}$ consists of all hyperplanes defined by equations $x_i=x_j$ for $1\le i