Upper bound on the characters of the symmetric groups (Q1923251)

This paper presents a universal upper bound on the normalized characters of the symmetric groups. This upper bound decreases exponentially with the order of the support of the conjugacy classes. The second part of the paper contains a survey of combinatorial, statistical and algebraic applications. Some of them are proved in the paper, and others in subsequent papers. Let \(\lambda\) be a partition of \(n\), \(S^\lambda\) the corresponding irreducible representation of the symmetric group \(S_n\), and \(r^\lambda\) the corresponding normalized character (i.e. the character divided by the degree). Then there exist constants \(b>0\) and \(1>q>0\) such that for \(n>4\), for every conjugacy class \(C\) in \(S_n\) and every irreducible representation \(S^\lambda\) of \(S_n\) \[ |r^\lambda(C)|\leq \bigl(\max\bigl\{q,{\lambda_1\over n},{\lambda_1'\over n}\bigr\}\bigr)^{b\cdot\text{supp}(C)} \] where \(\text{supp}(C)\) is the number of non-fixed digits under the action of a permutation in \(C\), \(\lambda_1\) is the size of the largest part in \(\lambda\), and \(\lambda_1'\) is the number of parts in \(\lambda\). The proof of the upper bound is obtained by enumeration of rim hook tableaux, the hook formula and probabilistic arguments. Applications in different directions follow from this bound: mixing times of random walks with respect to conjugacy classes are determined; an asymptotic decomposition of the conjugation representation is suggested; and expansion properties of certain Cayley graphs are shown.