Graphical Mahonian statistics on words (Q1691093)

Summary: \textit{D. Foata} and \textit{D. Zeilberger} [J. Comput. Appl. Math. 68, No. 1--2, 79--101 (1996; Zbl 0856.05006)] defined the graphical major index, \(\operatorname{maj}_U\), and the graphical inversion index, \(\operatorname{inv}_U\), for words over the alphabet \(\{1, 2, \ldots, n\}\). These statistics are a generalization of the classical permutation statistics \(\operatorname{maj}\) and \(\operatorname{inv}\) indexed by directed graphs \(U\). They showed that \(\operatorname{maj}_U\) and \(\operatorname{inv}_U\) are equidistributed over all rearrangement classes if and only if \(U\) is \textit{bipartitional}. In this paper we strengthen their result by showing that if \(\operatorname{maj}_U\) and \(\operatorname{inv}_U\) are equidistributed on a single rearrangement class then \(U\) is \textit{essentially bipartitional}. Moreover, we define a graphical sorting index, \(\operatorname{sor}_U\), which generalizes the sorting index of a permutation. We then characterize the graphs \(U\) for which \(\operatorname{sor}_U\) is equidistributed with \(\operatorname{inv}_U\) and \(\operatorname{maj}_U\) on a single rearrangement class.