Time

Jan 27 2005 - 3:30pm

Location

MW154

Speaker

Adam Hammett (The Ohio State University)

Abstract

In combinatorics, much attention has been paid to properties of the Bruhat order on $S_n$. We show that with high probability, two permutations from $S_n$ selected independently and uniformly at random will not even be comparable in the Bruhat order. In particular, for $\pi ,\sigma \in S_n$, we show $P[ \pi \leq \sigma ]=O( n^{-1/2})$, thus obtaining an explicit rate of convergence to zero for $P[ \pi \leq \sigma ]$ as $n \rightarrow \infty$. This result is found via the well-known Ehresmann's tableau criterion for comparability of permutations in the Bruhat order and a connection to a certain random walk on the real line. We also draw some conclusions about a lower bound for $P[ \pi \leq \sigma ]$, showing that $P[ \pi \leq \sigma ]=\Omega ( \alpha^n\right)$ for each $\alpha < (1/2+(5/12)^{1/2})/2=0.5727\dots$, by utilizing a certain recursive inequality.