(CNRS UMR 7586), Universit´e Paris 7, Case 7012, 2 Place Jussieu, F-75251 Paris, C´edex 05, France Received April 24, 2001; Revised April 8, 2003; Accepted April 17, 2003
Abstract. All of the automorphisms of the Fibonacci posetZ(r) are determined (r∈N). A problem of Richard P. Stanley from 1988 is thereby solved.
Keywords: Fibonacci poset, Fibonacci lattice, differential poset, automorphism group, (partially) ordered set
2000 Mathematics Subject Classification: 06C05, 06B99, 06A11, 05E25, 05E10, 08A35, 20B25, 20B27, 20B30, 06A30, 06A20
1. Introduction—To be young again
Young’s lattice Y, the set of Ferrers shapes partially ordered in a certain fashion, is a poset of tremendous combinatorial significance. As is well known, it is closely connected with the representation theory of the symmetric groupsSr(r ∈N).
In [9], Richard P. Stanley investigated lattices that share many of the interesting combina- torial properties ofY, the Fibonacci posetsZ(r) (r∈N). These are posets whose elements are finite words generated from the alphabet {11,12, . . . ,1r,2}, where one defines the covering relation as follows:ycoversxinZ(r) if either
(1) x=2kvandy=2k1iv, or (2) x=2k1ivandy=2k2v
for somei ∈{1, 2,. . . ,r}andv∈ Z(r). In other words, one can either delete the first 1 or convert a 2 into a 1 (as long as no other 1’s appear before it). See figures 1 and 3.
The results in this paper were first obtained by the second author, Dr. SungSoon Kim, and then independently obtained by the first author. The first author would therefore like to thank Dr. SungSoon Kim for graciously inviting him to co-author this paper. The first author was supported by (U.S.) National Science Foundation Grant DMS-9971352.
Figure 1. The Fibonacci posetZ(1).
In [9], Problem 7, Stanley asks:
Problem([9]) What is the automorphism group Aut (Z(r)) of the Fibonacci posetZ(r)?
(Admittedly, Stanley adds, “We suspect that Problem 7 should not be too difficult.”) We solve the problem by explicitly determining all of the automorphisms of Z(r) (Theorem 4.5).
2. Definitions
Throughout this paper, r will denote a positive integer.
For basic terminology, see [2].
Let Pbe a poset; let p,q ∈ P. We sayq covers p(denoted p<·q) if p<qand for all r ∈ P,p ≤r <q implies p =r;pis alower coverofq andq is anupper coverof p.
An element isjoin-irreducibleif it has exactly one lower cover; the set of such elements is denotedJ(P).
A poset with a least element islocally finiteif, for allp∈ P, there are only finitely many elements of Pbelow p. Therankof an element in such a poset is one less than the size of the largest chain whose top element is p.
In a latticeL, the least upper bound ofx,y∈ Lis denotedx∨y.
Anautomorphismτ¯of a poset Pis an order-preserving bijection whose inverse is also order-preserving. Equivalently, ifPis locally finite, a bijection ¯τ : P→ Pis an automor- phism if, for all p,q ∈ P,p<·qimplies ¯τ(p)<·τ¯(q) and vice versa.
makeZ(r) anr-differential poset.
Indeed, Z(r) is the onlyr-differential (locally finite, modular) lattice such that every complemented interval has rank at most 2. It can be constructed inductively by “reflection”
([9], Section 6): One constructs Z(r) rank by rank, reflecting the last layer one has built, then addingrnew join-irreducible upper covers for each element [figures 2(a)–(c)].
One deduces that, forZ(1), the number of elements of each rank is a Fibonacci number.
In [9], Section 6, Stanley observes that the symmetric groupSr acts onZ(r).
Example 3.1 The 3-cycleσ =(123) induces an automorphism ¯σ : Z(3)→ Z(3) which sends, for instance,w=11122112213to ¯σ(w)=12132122211.
“However,” Stanley writes, “Z(1) has (at least) an additional automorphismω, defined by
ω(v11)=v2 ω(v2)=v11
ω(w)=w otherwise”
[i.e., ifwis not of the formv11 orv2 for somev∈ Z(1)]. The fact thatωis an automorphism is “obvious” by reflecting figure 1 about the vertical axis; but we prove it rigorously in Lemma 4.4.
Our list of references contains other papers dealing with the Fibonacci poset.
4. The automorphism group of the Fibonacci posetZ(r): The solution to Stanley’s problem
In this section we solve Stanley’s problem (see Section 1) by finding all of the automorphisms of Z(r) (Theorem 4.5).
The idea is that each wordw∈Z(r) has a setCwofrjoin-irreducible upper covers; and an automorphism ¯τ ofZ(r) must sendCwtoCτ¯(w). Hence, to eachwwe can associate an element ofSr. AsZ(r) is a locally finite lattice, the action of ¯τ onJ(Z(r)) determines ¯τ.
(a) (b)
(c)
Figure 2. (a) BuildingZ(r) by reflection. (b) BuildingZ(r) by reflection. (c) BuildingZ(r) by reflection.
Figure 3. The Fibonacci posetZ(2).
inductively on the length of the argument,as follows:For allw∈ Z(r),let τ¯(w)=
2k if w=2k(k≥0),
2k1τv(i)τ¯(v) if w=2k1iv[k≥0; 1≤i ≤r;v∈Z(r)]. Thenτ¯belongs toAut (Z(r))andτ¯(2)=2.
Proof: It is clear that ¯τis a bijection whose inverse is ¯vfor somev∈ SrZ(r). Thus it suffices to prove that ifx,y∈ Z(r) andx<· y, then ¯τ(x)<·τ¯(y).
It is obvious that, for allv∈ Z(r),τ¯(2v)=2 ¯τ(v).
Case 1. x =2kvandy=2k1iv[k≥0; 1≤i ≤r;v∈ Z(r)]
Then ¯τ(x)=2kτ¯(v) and ¯τ(y)=2k1τv(i)τ¯(v),so ¯τ(x)<· τ¯(y).
Case 2. x =2k1ivandy=2k2v[k≥0; 1≤i ≤r;v∈Z(r)]
Then ¯τ(x)=2k1τv(i)τ¯(v) and ¯τ(y)=2k2 ¯τ(v), so ¯τ(x)<·τ¯(y).
Let ˆτ ∈Aut (Z(r)) be such that ˆτ(2)=2. Since ˆτ mapsJ(Z(r)) bijectively onto itself, but fixes 2, then, by Lemma 4.1, for all w ∈ Z(r) and 1 ≤ i ≤ r,τˆ(1iw) = 1jv for some j ∈ {1,2, . . . ,r}andv ∈ Z(r). We will show thatv depends only onw and not oni:
Lemma 4.3 Letτˆ ∈Aut (Z(r))be such thatτˆ(2)=2. For allw∈ Z(r),defineτw∈Sr
as follows:For1≤i ≤r,τˆ(1iw)=1τw(i)τˆ(w).
Letτ=(τw)w∈Z(r). Defineτ¯ as in Lemma4.2.
Thenτˆ=τ¯.
Proof: From what was said before the statement of the proposition,vmust be ˆτ(w), as wis the unique lower cover of 1iw, so ˆτ(w) is the unique lower cover of 1jv, which isv.
Thusτw∈ Sris well defined.
Claim For allv∈ Z(r),τˆ(2v)=2 ˆτ(v).
Proof of Claim(by induction on|v|): The claim follows from the definition of ˆτifv=. Case 1. v=1iu[1≤i ≤r;u∈ Z(r)].
Then 2u,111iu<·21iu =2v, so 2u∨111iu =2v. By the induction hypothesis, ˆτ(2u)= 2 ˆτ(u) and we know that ˆτ(111iu)=1j1kτˆ(u) [where 1 ≤ j,k ≤r and ˆτ(v) =1kτˆ(u)].
Note that 2 ˆτ(u),1j1kτˆ(u)<·21kτˆ(u), so 2 ˆτ(u)∨1j1kτˆ(u)=21kτˆ(u) and hence ˆτ(2v)= 21kτˆ(u)=2 ˆτ(v).
Case 2. v=2u[u ∈Z(r)].
Then 211u,112u<· 22u =2v, so 211u∨112u = 2v. By Case 1, ˆτ(211u) =2 ˆτ(11u) = 21jτˆ(u) for some j ∈ {1,2, . . . ,r}. Also, ˆτ(112u) = 1kτˆ(2u) =1k2 ˆτ(u) for somek ∈ {1,2, . . . ,r}.
Note that 21jτˆ(u),1k2 ˆτ(u)<·22 ˆτ(u), so 21jτˆ(u)∨1k2 ˆτ(u)=22 ˆτ(u) and hence ˆτ(2v)= 22 ˆτ(u)=2 ˆτ(v),
The lemma follows, as ˆτ and ¯τ agree on all words inZ(r).
The following result is asserted without proof in [9], Problem 7.
Lemma 4.4 The mapωof Section3belongs toAut (Z(1)).
Proof: Asω2=idZ(1), it suffices to prove that ifx,y∈Z(1) andx<· y, thenω(x)<·ω(y).
Case 1. x =2kvandy=2k1v[k≥0;v∈ Z(1)].
If v = u11,u2, or u21 for someu ∈ Z(1), then ω(x)<·ω(y). If v = 1, then ω(x) = ω(2k1)=2k1<·2k2=ω(2k11)=ω(y).
Else, v = . If k = 0, then ω(x) = ω() = <· 1 = ω(1) = ω(y). If k ≥ 1, then ω(x)=ω(2k)=2k−111<·2k−121=2k1=ω(2k1)=ω(y).
Case 2. x =2k1vandy=2k2v[k≥0;v∈ Z(1)].
Ifv=u11,u2,u21, orfor someu∈ Z(1),thenω(x)<·ω(y).
Else,v=1, soω(x)=ω(2k11)=2k2<·2k21=ω(2k21)=ω(y).
Theorem 4.5 The automorphism group of Z(1)is isomorphic toZ2,the non-trivial au- tomorphism beingω:Z(1)→ Z(1)defined for allw∈ Z(1)by:
ω(w)=
u2 if w=u11 [u ∈Z(1)], u11 if w=u2 [u∈ Z(1)], w otherwise.
Lemma 4.1, join-irreducible. Hence the form of ¯τ follows from Lemmas 4.2 and 4.3.
Note that if ¯τand ¯vare automorphisms associated with the sequencesτ=(τw)w∈Z(r),v= (vw)w∈Z(r)∈ SrZ(r), andv∈ Z(r) is a minimal element such thatτv =vv(say,τv(i)= j = k=vv(i)), then ¯τ(1iv)=1jτ¯(v) =1kτ¯(v)=1kv(v)¯ =v(1¯ iv). Hence, each automorphism constructed is unique.
To prove the last statement, note that S2Z(2) has exponent 2. But consider the map ¯τ: Z(2)→ Z(2) where, for allw∈ Z(2),
τw=
(12) ifw=orw=11, (1)(2) otherwise.
(See figure 3.)
Hence ¯τ(1111)=1212,τ¯(1212)=1211, so ¯τ2(1111) =1111and ¯τ2 =idZ(2). Therefore Aut (Z(2)) ∼=S2Z(2).
Collecting all the observations above, we can conclude as follows.
Corollary 4.6 The automorphism groupAut (Z(r))is isomorphic toZ2Sr.
Proof: Let us denote the reflection ofωofZ(1) and letti =(i,i+1)(i =1, . . . ,r−1) permutting the 1i’s. Then one can see that all the automorphisms ofZ(r) are the products oftiandsunder the following conditions:
order relations:
ti2=s2=1 (i=1, . . . ,r−1) and the braid relations:
titj =tjti (for alli,j =0, . . . ,r−1 such that|i−j|>1,t0=s), stj =tjs (j =2, . . . ,r−1),st1st1=t1st1s,
titi+1ti =ti+1titi+1 (i =1, . . . ,r−1).
Hence we can conclude that Aut (Z(r)) ∼= Z2 Sr which is the Weyl group of type Br.
Remark According to the Shephard–Todd notation, this isG(2,1,r), which is a special case of the complex reflection group of typeG(d,1,r)=ZdSrwithd=2.
For further detailed verifications of the relations ofsandti in the proof above, please consult the second author.
The problem of Stanley from 1988 is thereby solved.
References
1. F. Brenti, “Log-concavity and combinatorial properties of Fibonacci lattices,”European Journal of Combi- natorics12(1991), 459–476.
2. B.A. Davey and H.A. Priestly,Introduction to Lattices and Order, 2nd edition, Cambridge University Press, Cambridge, 2002.
3. F.M. Goodman and S.V. Kerov, “The Martin boundary of the Young–Fibonacci lattice,”Journal of Algebraic Combinatorics11(2000), 17–48.
4. R. Kemp, “Tableaux and rank-selection in Fibonacci lattices,”European Journal of Combinatorics18(1997), 179–193.
5. D. Kremer, “A bijection between intervals in the Fibonacci posets,”Discrete Mathematics217(2000), 225–
235.
6. D. Kremer and K.M. O’Hara, “A bijection between maximal chains in Fibonacci posets,”Journal of Combi- natorial Theory (A)78(1997), 268–279.
7. S. Okada, “Algebras associated to the Young–Fibonacci lattice,”Transactions of the American Mathematical Society346(1994), 549–568.
8. R.P. Stanley, “The Fibonacci lattice,”The Fibonacci Quartely13(1975), 215–232.
9. R.P. Stanley, “Differential posets,”Journal of the American Mathematical Society1(1988), 919–961.
10. R.P. Stanley, “Further combinatorial properties of two Fibonacci lattices,”European Journal of Combinatorics 11(1990), 181–188.
