Séminaire Lotharingien de Combinatoire, B53g (2006), 12 pp.
Ron M. Adin and Yuval Roichman
On Degrees in the Hasse Diagram of the Strong Bruhat Order
Abstract.
For a permutation \pi in the symmetric group Sn let the
total degree
be its valency in the Hasse diagram of the strong Bruhat order on
Sn,
and let the down degree
be the number of permutations which are covered by \pi in
the strong Bruhat order.
The maxima of
the total degree and the down degree and their values at a random permutation
are computed. Proofs involve variants of a classical theorem of Turán from
extremal graph theory.
Received: May 2, 2005.
Accepted: February 14, 2006.
Final Version: March 12, 2006.
The following versions are available: