#####
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 *S*_{n} let the
*total degree*
be its valency in the Hasse diagram of the strong Bruhat order on
*S*_{n},
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: