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: