Cyclomatic numbers and permutations

Abstract

We show that several apparently different aspects of a permutation are all tied to a single quantity, the cyclomatic number of its inversion graph. Every reduced word for the permutation orders the edges of the inversion graph one at a time, with the edges from first-occurrence letters forming a spanning forest and the edges from repeated letters accounting for the rest; the number of repeated letters is therefore the cyclomatic number. The excess of permutation cycles over sum components is also at most this quantity, and it follows that the gap between the Coxeter and reflection lengths is at least the cyclomatic number and at most twice it. When the inversion graph is a forest, these results unify classical characterizations of the boolean permutations due to Edelman, to Tenner, and to Petersen and Tenner. We also give a new proof that every connected acyclic inversion graph is a caterpillar.

19 pages