tailieunhanh - Báo cáo toán học: "Parking functions of types A and B"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài:Parking functions of types A and B. | Parking functions of types A and B P. Biane CNRS Departement de Mathematiques et Applications Ecole Normale Superieure 45 rue d Ulm 75005 Paris FRANCE Submitted May 6 2001 Accepted September 30 2001 MR Subject Classifications 06A07 05E25 Abstract The lattice of noncrossing partitions can be embedded into the Cayley graph of the symmetric group. This allows us to rederive connections between noncrossing partitions and parking functions. We use an analogous embedding for type B noncrossing partitions in order to answer a question raised by R. Stanley on the edge labeling of the type B non-crossing partitions lattice. 1 Introduction A type A parking function is a sequence of positive integers ai . an such that its increasing rearrangement bi . bn satisfies b i while a noncrossing partition of 1 n is a partition such that there are no a b c d with a b c d a and c belong to some block of the partition and c d belong to some other block. The set of noncrossing partitions of 1 n is denoted by NCn it is a lattice for the refinement order. In S R. Stanley gives a labeling of edges in NCn 1 and proves that through this labeling parking functions are in one-to-one correspondance with maximal chains in the lattice NCn i. A type B parking function is a sequence a1 . an of positive integers satisfying ai n. A noncrossing partition of type B as defined by Reiner R is a noncrossing partition of 1 2 . n 1 2 . ng which is invariant under sign change. In this paper we shall use a natural embedding of NCn 1 in the Cayley graph of the symmetric group sn i to recover Stanley s result. An analogous embedding of N B into Wn the hyperoctahedral group then leads to a parallel treatment of the type B case. In particular we give an edge labeling of NCB which gives a bijection between maximal chains and type B parking functions thus answering R. Stanley s question in S page 12. The embeddings allow us to use the symmetries of these structures in a very efficient way. This