Cardinality of Balls in Permutation Spaces

Liviu P. Dinu, Catalin Zara

For a right invariant distance on a permutation space $S_n$ we give a sufficient condition for the cardinality of a ball of radius $R$ to grow polynomially in $n$ for fixed $R$. Fo…