Ranks And Subdegrees Of The Symmetric Group Acting On Ordered R-Element Subsets N S

ABSTRACT

The action of the symmetric group Sn on ordered subsets from the set X 1, 2, , n is an aspect that seems to have received little attention for a long time. Most studies have focused on the action of n S on unordered subsets leaving many properties about its action on ordered subsets unknown. This research is set to determine the rank and subdegrees of n S acting on r X , the set of all ordered r-element subsets from X. Particular cases when r  2, 3 and 4 have been considered first and then a generalization has been made for any value of r and n. In the action of n S on 2 3 X , X and 4 X , the rank is shown to be 7, 34 and 209 respectively. By generalizing these results, we have come up with the formulas for the rank and subdegrees of n S acting on r X . This study shows that if n  2r , then for a fixed value of r, the rank of n S on r X is a constant while the subdegrees vary with n. The action of n S on r X has been shown to be both transitive and imprimitive. We have also formulated the conditions for a suborbit of n S corresponding to this action to be either self-paired or paired with another. A formula for computing the number of self-paired suborbits has also been derived using a theorem from character theory. Finally, the suborbital graphs corresponding to this action have been constructed and their theoretic properties studied. The results show that all these graphs are disconnected. We have also come up with the formulas for computing the number of connected components in these graphs. The girth sizes of the suborbital graphs corresponding to suborbits of n S containing exactly r elements and no element from A 1, 2,..., r have also been determined. For the suborbital graphs corresponding to self-paired suborbits of n S with exactly r elements from A, the girth is shown to be zero while that of paired suborbits with precisely r elements from A is shown to be three. This study also reveals that the girth of the suborbital graph corresponding to the suborbit of n S with no element from A is three provided n  3r . The results obtained have been summarized in form of theorems while others are displayed in tables.