A Class of Labeled Posets and the Shi Arrangement of Hyperplanes

✍ Scribed by Christos A Athanasiadis

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 244 KB
• Volume: 80
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1997.2793

✦ Synopsis

We consider the class P n of labeled posets on n elements which avoid certain three-element induced subposets. We show that the number of posets in P n is (n+1) n&1 by exploiting a bijection between P n and the set of regions of the arrangement of hyperplanes in R n of the form x i &x j =0 or 1 for 1 i< j n. It also follows that the number of posets in P n with i pairs (a, b) such that a<b is equal to the number of trees on [0, 1, ..., n] with ( n 2 )&i inversions.

1997 Academic Press

1. THE RESULTS

Let P n be the set of posets on [n] :=[1, 2, ..., n] which do not contain any of the three-element posets of Fig. 1, with a<b<c, as induced subposets. For any undefined terminology about posets we refer the reader to [8, Chap. 3]. The objective of this paper is to point out some surprising enumerative properties of P n . Our first theorem follows.

Theorem 1.1. The number of posets in P n is (n+1) n&1 . We will prove this by a bijection between P n and the set of regions of the arrangement of hyperplanes

for 1 i< j n,

x i &x j =1 for 1 i< j n article no. TA972793 158 0097-3165Â97 25.00