The University of Michigan Combinatorics Seminar
We obtain a number of results regarding the distribution of values of a
quadratic function f on the set of n by n permutation matrices
(identified with the symmetric group Sn) around its optimum (minimum or
maximum). We estimate the fraction of permutations w such that
f(w) lies within a given neighborhood of the optimal value of f and
relate the optimal value with the average value of f over a neighborhood of
the optimal permutation.