Time

Location

Speaker

Abstract

Ubiquitous in theoretical computer science and combinatorics,
sorting networks provide a deterministic algorithm one can apply to
sort an array of n elements through adjacent exchanges. Formally,
a sorting network of order n is a sequence of N+1:=(n(n-1)/2)+1
permutations of length n, (p_0,p_1,...,p_N), such that p_0=12...n,
p_N=n(n-1)...1, and p_i differs from p_{i+1} only by an adjacent
transposition.

Richard Stanley proved that the number of these sorting networks
equals N!/1^{n-1}x3^{n-2}x5^{n-3}x...x(2n-3)^{1}. We study
properties of the uniformly random sorting network of order n. In
particular, it might happen that a contiguous subsequence of the
sorting network (p_k,p_{k+1},...,p{k+m}) does nothing more than
exchange two entries of p_k that are at distance d from each other.
That is, p_{k+m} is obtained from p_k by simply exchanging entry
p_k(j) with entry p_k(j+d) for some j. Let X(n,d) be the number of
*minimal* exchanges of this sort (i.e., m above is minimal; it turns
out that m=2d-1) in the uniformly random sorting network.

We prove that Exp[X(n,d)] =

[(n+d-1)_{2d}/(N)_{2d-2}]x[2/(d4^d)]x{2d-2 choose d-1}^2.

Here a_b:=ax(a-1)x...x(a-b+1), and Exp[.] stands for the expected
value. This extends a result of Victor Reiner, who established the
case d=2, in which case this expectation has value 1 exactly. Time                                                              permitting we will discuss possible extensions.                                                                                                                                                                                                  This is joint work with Boris Pittel.