The group \( S_n \) of permutations on \([n]=\{1,2,\dots,n\} \) is generated by simple transpositions \( s_i = (i,i+1) \). The length \( \ell(\pi) \) of a permutation \( \pi \) is defined to be the minimum number of generators whose product is \( \pi \). It is well-known that the longest element in \( S_n \) has length \( n(n-1)/2 \). Let \( F_n \) be the semigroup of functions \( f:[n]\to[n] \), which are generated by the simple transpositions \( s_i \) and the function \( t:[n]\to[n] \) given by \( t(1) =t(2) = 1 \) and \( t(i) = i \) for \( i\ge3 \). The length \( \ell(f) \) of a function \( f\in F_n \) is defined to be the minimum number of these generators whose product is \( f \). In this talk, we study the length of longest elements in \( F_n \). We also find a connection with the Slater index of a tournament of the
complete graph \( K_n \). This is joint work with Yasuhide Numata.
기초과학연구원 이산수학그룹