Linear extensions of finite posets and a conjecture of G. Kreweras on permutations

✍ Scribed by Gwihen Etienne

• Publisher: Elsevier Science
• Year: 1984
• Tongue: English
• Weight: 416 KB
• Volume: 52
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(84)90108-0

✦ Synopsis

We pmve a conjecture of G. Kreweras on the number of solutions of the equation xy = z for permutations of a given signature. Let x be a permutation of [n) = (1,2, . . . , n), R an integer \2. The signanue of x k~ the (n-l)-tuple e =(el, e2,. . . . , E,,-~) where Ei is the sign + if q : P. of the equation xy = z for t EP, does not depend on z in P,. We prove this eonjeeture jn a more general fo&rm by relating it to linear extensions of pose6 We give an expression of the number of solutions iu terms d a Mobius fur&ion as a corollary of a theorem of Stanley. 2.Linearextemiom A r'i~rear extension of a finite pset (ET, C) with cardinality n, is a one-to-one mapping s : [n] + E such that s, C 4 implies i < /. Let s, t be two one-to-one mappings [II]-\ 2% We denote u,(t) = {al, . . . , CY,\_~) the (;"1 --I)-tuple of signs (+ , -) defined by + if s-'(t) <: s-'l(fi+r)s \*= -otherwise. Let s be a linear extension of {E, s). Suppose that So and s$+~ are incomparable in (E, 2s). WE cdl allowed transposition T on s the transposition {&, Si+l} leading to