A re-examination of the Diaconis-Graham inequality

Hadjicostas Petros, Monico Chris

Research output: Contribution to journalArticle

1 Scopus citations


In this paper we give an alternative and more intuitive proof to one of two classic inequalities given by Diaconis and Graham in 1977. The inequality involves three metrics on the symmetric group, i.e., the set of all permutations of the first n positive integers. Our technique for the proof of the inequality allows us to resolve an open problem posed in that paper: When does equality hold? It also allows us to estimate how often equality holds. In addition, our technique can sometimes be applied for the proof of other inequalities between metrics or pseudo-metrics on the symmetric group.

Original languageEnglish
Pages (from-to)275-295
Number of pages21
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
StatePublished - Nov 1 2013


Cite this