Hyperplane arrangements, interval orders, and trees.
A hyperplane arrangement is a finite set of hyperplanes in a real affine space. An especially important arrangement is the braid arrangement, which is the set of all hyperplanes xi - xj = 1, 1 </= i < j </= n, in Rn. Some combinatorial properties of certain deformations of the braid arrangement are surveyed. In particular, there are unexpected connections with the theory of interval orders and with the enumeration of trees. For instance, the number of labeled interval orders that can be obtained from n intervals I1,..., In of generic lengths is counted. There is also discussed an arrangement due to N. Linial whose number of regions is the number of alternating (or intransitive) trees, as defined by Gelfand, Graev, and Postnikov [Gelfand, I. M., Graev, M. I., and Postnikov, A. (1995), preprint]. Finally, a refinement is given, related to counting labeled trees by number of inversions, of a result of Shi [Shi, J.-Y. (1986), Lecture Notes in Mathematics, no. 1179, Springer-Verlag] that a certain deformation of the braid arrangement has (n + 1)n-1 regions.
Stanley
R P
RP
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA.