Log-concavity, the Ulam distance and involutions

Miklós Bóna, Marie-Louise Bruner

We prove that in a large collection of naturally defined sets of permutations of fixed length, the numbers of permutations at Ulam distance k from the identity form a log-concave s…