[PDF] Combinatoire des fonctions de parking: espèces énumeration d

View - Download Combinatoire des fonctions de parking: espèces énumeration d

Previous PDF

Next PDF

Séminaire Lotharingien de Combinatoire84B(2020)Proceedings of the 32ndConference on Formal Power Article #59, 12 pp.Series and Algebraic Combinatorics (Online)

Some properties of the parking function poset

Bérénice Delcroix-Oger

*1, Matthieu Josuat-Vergès1,3, and Lucas Randazzo 2 1

IRIF, Université de Paris, France

2LIGM, Université Gustave Eiffel, Champs-sur-Marne, France

3CNRS Abstract.In 1980, Edelman defined a poset on objects called the noncrossing 2- partitions. They are closely related with noncrossing partitions and parking func- tions. To some extent, his definition is a precursor of the parking space theory, in the framework of finite reflection groups. We present some enumerative and topological properties of this poset. In particular, we get a formula counting certain chains, that encompasses formulas for Whitney numbers (of both kinds). We prove shellability of the poset, and compute its homology as a representation of the symmetric group. Résumé.En 1980, Edelman a défini un ordre partiel sur des objets appelés les 2- partitions non-croisées. Elles sont intimement reliées aux partitions non-croisées et aux fonctions de stationnement. Dans une certaine mesure, sa définition est un précurseur de la théorie des espaces de stationnement. Nous présentons quelques propriétés énumératives et topologiques de cet ordre. En particulier, nous obtenons une formule comptant certaines chaînes, qui inclut des formules pour les nombres de Whitney (des deux espèces). Nous prouvons l"épluchabilité du poset, et calculons son homologie en tant que représentation du groupe symétrique. Keywords:parking functions, noncrossing partitions, poset topology, representations, symmetric group

Introduction

Parking functionsare fundamental objects in algebraic combinatorics. It is well known that the set of parking functions of lengthnhas cardinalityn+1n1, and the natural action of the symmetric groupSnon this set occurs in the deep work of Haiman [5] about diagonal coinvariants. Generalizations to other finite reflection groups lead to the parking space theoryof Armstrong, Reiner, Rhoades [1,8 ]. The poset mentioned in the title was introduced by Edelman [ 4 ] in 1980, as a variant of thenoncrossing partition latticeintroduced by Kreweras [7] (hence the namenoncrossing

2-partitionsin [4]). One striking feature of Edelman"s definition is that it really fits well in*

bdelcroix@irif.fr

2Bérénice Delcroix-Oger, Matthieu Josuat-Vergès, and Lucas Randazzo

the noncrossing parking space theory mentionned above, so it seems that this overlooked poset can give a new perspective on recent results about parking functions. Our goal is to obtain new enumerative and topological properties of Edelman"s poset. Through various bijections, we will see that several variants of the same objects are relevant:

2-noncr ossingpartitions (

Section 1.1

some pairs of a noncr ossingpartition together with a per mutation(

Section 1.2

parking functions in the usual w ay(

Section 1.3

parking tr ees(

Section 1.3

The latter, which have the additional structure of aspecies, will be useful to write func- tional equations and get our enumerative results in

S ection2

. What we get is a formula counting chains ofkelements whose top element has rank`. A nice feature of this for- mula is that it encompasses a nice formula for Whitney numbers of the second kind at k=1 (this one being obtained by Edelman), and one for Whitney numbers of the first kind atk=1. Then we go on to topological properties: we will see in

S ection3

that the poset is shellable. Unlike the case of noncrossing partitions which can be treated by EL- shellability, we need here the notion ofrecursive atom ordering(equivalent to the notion of CL-shellability). Still, the EL-shellability of noncrossing partitions is a key tool. There are well known consequences of shellability such as Cohen-Macauleyness, and hence that only one homology group of the poset is non trivial. We use this fact in

S ection4

to compute the character of this homology group as a representation ofSn.

1 Parking function posets

1.1 The poset of noncrossing 2-partitions

A set partitionpoff1,...,ngisnoncrossingif there exists noiSome properties of the parking function poset3 noncrossing partition (so that ¯wis a full cycle). The mapp7!K(p)defines an anti- automorphism ofNCn. For example,K(ff1,2g,f3g,f4,5gg) =ff1,3,4g,f2g,f5ggsince in the symetric group we have(12345)(12)(45) = (134). Definition 1.1(Edelman [4]).Anoncrossing 2-partitionoff1,...,ngis a triple(p,r,l) where: •pis a noncrossing partition off1,...,ng,ris a set partition off1,...,ng, •lis a bijection from (the blocks of)pto (those of)r, and8B2p, #l(B) =#B.

This set is denoted

2Pn. A partial order on2Pnis defined by(p0,r0,l0)(p,r,l)iff:

•p0is a refinement ofp,r0is a refinement ofr, if Uj i=1B0i=BwhereB0i2p0andB2p, thenUj i=1l0(B0i) =l(B). For example, such a triple(p,r,l)is as follows:p=ff1,5,6,8g,f2,3g,f4g,f7gg, randlare given byl(f1,5,6,8g) =f2,3,4,7g,l(f2,3g) =f5,8g,l(f4g) =f1g, l(f7g) =f6g. Another representation will be given inS ection1.2 (in particular ,see the example at the end).

The poset

2Pnis ranked, with rk((p,r,l)) =#p1. Let us mention a few other

properties following from the definition. Using the last condition above, we see that if (p,r,l)(p0,r0,l0),landrare uniquely determined byp0,r0,l0,p. It follows that the order ideal of

2Pncontaining all elements below(p,r,l)is isomorphic to an order

ideal in the noncrossing partition lattice, so it is isomorphic to a product of noncrossing partition latticesNCi1NCi2 (herei1,i2,... are the sizes of the blocks ofK(p)).

Similarly, one can prove that the order filter of

2Pncontaining all elements above(p,r,l)

is isomorphic to a product

2Pi12Pi2 (herei1,i2,... are the sizes of the blocks of

p). Moreover,2Pnhas one minimal element, andn! maximal elements.

Edelman proved in [

4 ] that thez-polynomial of this poset is given byZ2P n(k+1) = (nk+1)n1. In particular, settingk=1 we see that noncrossing 2-partitions and parking functions are equienumerous. Another result from [ 4 ] is that for 0kn1, the number of elements of rank`in2Pn, called the`thWhitney number of the second kind, is W `(2Pn) =`!n S

2(n,`+1), (1.1)

whereS2(n,k)are the Stirling numbers of the second kind. There is a natural action ofSnon set partitions off1,...,ng(see [2], for example). It extends to an action on

2Pnby:s(p,r,l) = (p,sr,sl), where inslwe identify

swith its action on set partitions. We will see below another way to think of this action, by defining a species of parking trees. It is straightforward to check that the action preserves the order relation of

2Pn, so that it extends to an action on chains of the poset,

and then on the homology.

4Bérénice Delcroix-Oger, Matthieu Josuat-Vergès, and Lucas Randazzo

1.2 The parking space

It turns out that this action can be identified with one defined in theparking space theory, introduced by Armstrong, Reiner and Rhoades in [ 1 ]. In some sense, Edelman"s poset is a precursor to this theory. To clarify this link, let us mention a few facts. Forp2NCn, we denote bySn(p)the set ofs2Snsuch thatsp=p. ThenSn(p) is aparabolic subgroup(it is conjugated to a Young subgroup). The quotientSn/Sn(p) is acted on bySn, by left multiplication. The character of this action is IndSn S n(p)(1), the trivial character ofSn(p)induced toSn. Under the Frobenius map, it is sent to the homogeneous symmetric function h l, wherelis the integer partition obtained by sorting block sizes ofp. Any pair(p,s)wherep2NCnands2Sn/Sn(p)can be identified with an element (p,r,l)22Pnby lettingr=sp, andlis defined as the action ofson blocks ofp. This identification is compatible with the action ofSn. It follows that the character of the action ofSnon2Pnis: p2NCnIndSn S n(p)(1). Therefore it coincides with thenoncrossing parking spacefrom [1].

In particular, the poset

2Pnappears implicitly in [8]. It follows from this reference that

the character ofSnacting on chainsf1 fkin2Pnis given by s7!(kn+1)z(s)1(1.2) wherez(s)is the number of cycles ofs. Following the above discussion, it is natural to see(p,r,l)22Pnas a pair(p,s) wheres2Snis a minimal length coset representative inSn/Sn(p), i.e. for each block B=fb1,b2,...g 2pwe haves(b1)1.3 The link with parking functions Definition 1.2.Aparking functionof lengthnis a wordw1wnof positive integers, such that for allkbetween 1 andn, we have #fi:wikg k. The symmetric group acts on parking functions as follows: fors2Sn,s(w1wn) =ws1(1)ws1(n).

Some properties of the parking function poset5

To each(p,r,l)22Pn, we associate a parking functionw1wnby the following condition: for eachB2p, we havewi=minBifi2l(B). It can be checked that this defines a bijection that is compatible with the action ofSn. It is worth making explicit what are the parking functions corresponding to(p,p,I) whereIis the identity map, because these are orbit representatives. It turns out that they are the parking functionsw1wnsuch that: i)wiifor alli, and: ii) they are lexicographically maximal among parking functions in the same orbit and satisfying i). Definition 1.3.Aparking treeon a setLis a rooted plane treeTsuch that: i) the internal vertices ofTare labelled with nonempty subsets ofL, ii) the above mentioned labels form a set partition ofL, iii) if an internal vertex hasidescendants then its label has cardinalityi. Thespecies of parking functions(orparking species), denotedPf, is the species which associates to any finite setVthe set of parking trees onV.

Note that a parking tree onLhas #Ledges.

Example 1.4.We represent below the parking trees onf1g,f1,2gandf1,2,3g:1, 12, 21,
12, 123,
123,
132,
231,
123,
132,
231,
123,
213,
312,
123,
132,
213,
231,
312,
321.

1325271

l (f1,7g,f3,5g,f2g,AE,f4g,AE,f6g) l1,763,542Parking trees onf1,...,ngare in bijection with parking functions in such a way that the action of S ncoincides on both sets. A parking function of lengthncan be rewritten as a (weak) set composi- tion(A1,...An)off1,...,ngsatisfyingåki=1jAij k for any 1kn, by lettingAibe the set of po- sitions of letteriin the parking function. Then, the vertices of the parking trees are given by the sets of the composition, andAiis the leftmost child ofAi1 ifAi16=AE, and plugged in the next available place to the right otherwise. The inverse bijection is given by reading nodes in a prefix order. See the picture on the right.

6Bérénice Delcroix-Oger, Matthieu Josuat-Vergès, and Lucas Randazzo

The covering relations on parking trees corresponding to those of the 2-partition poset are then given as follows. From a parking treeT, another oneUsuch thatTlU is obtained fromTby a sequence of operations: choose a v ertexAand partition it into two (non empty) setsA1andA2, deconcatenate the list of its (possibly empty) subtr eesinto thr eelists L1,L2andL3, such thatL1is non empty andL2andA2have the same cardinality, r emovefr omthe tr eethe elements of A2andL2 add the elements of A2to the rightmost leaf ofA1inL1 add L2as the list of children ofA2.

For the leftmost tree in

Figur e1

,A1=f1,5,6gandA2=f2g, the possible lists are(L1,L2,L3) = ((AE),(34),(AE,AE)),((AE,34),(AE),(AE))or((AE,34,AE),(AE),()), which gives each of the other trees in

Figur e1

2 Enumeration of chains of parking functions

Proposition 2.1.The speciesPfof parking trees satisfies: P f=å k1E k(Pf)k, (2.1) whereEk(V) =djVj=kK(whereKis our ground field) and the species of non-empty sets is

E1=åk1Ek.

This is obtained from the tree structure, and accordingly we can write an equation in terms of symmetric functions for the Frobenius image of the characters ofPf. The set ofweak k-chainsof parking functions onIis the set PFIkofk-tuples(a1,...,ak) whereaiare parking functions onIandaiai+1. The species which associates to any setIthe set PFIkis denoted byClk,t.

Theorem 2.2.We have:

C lk,t=å p1Cl,p k1,t tClk,t+1 p, whereCl,p k1,t(V) =djVj=pClk1,t(V)on any set V of size p. In terms of generating functions, this translates to: C lk,t=Clk1,t x tClk,t+1 (2.2) Some properties of the parking function poset71 2 5 6;;34

1 5 6;;234

1 5 6;342

1 5 6234

;Figure 1:A tree and some trees covering it.A 1?A2F 1F pF p+1F lF l+1F n......... A 1Fquotesdbs_dbs41.pdfusesText_41

[PDF] nf-p 91-120 (parcs de stationnement privés)

[PDF] définition intérêt

[PDF] mission d'intérêt général service public

[PDF] concept géographique définition

[PDF] concepts géographie

[PDF] dictionnaire géographique universel

[PDF] méthode aba définition

[PDF] règle de bioche intégrale pdf

[PDF] somme de riemann exercice corrigé

[PDF] règle de bioche exercices corrigés

[PDF] somme de darboux exercice corrigé pdf

[PDF] intégrale de riemann exercice corrigé

[PDF] calcul puissance absorbée moteur triphasé

[PDF] tp synthèse de l'aspirine seconde

[PDF] mise en garde aspirine