Ranks, Subdegrees And Suborbital Graphs Of The Symmetric Group Sn Acting On Unordered r-Element Subsets

Abstract

The main aim of this research is to determine the ranks, subdegrees, and the suborbital graphs of the symmetric group Sn acting on unordered r-element subsets of X = {1, 2, 3, ..., n}. These areas have not received much attention, in fact most of the research has been focused on the action of Sn on unordered pairs. In 1970, Higman proved that Sn, n ≥ 4 acts as a rank 3 group on X(2), with subdegrees 1, 2(n − 2), 0 B@ n − 2 2 1 CA . In this study, it is shown that Sn acts transitively and primitively on X(r)(r-element subsets of X). The ranks and suborbits of Sn acting on X(4) and X(5) are determined, after which it is proved that the rank of Sn acting on X(r) is r + 1 if n ≥ 2r. The suborbits of Sn acting on X(r) are all self paired is shown. It is also proved that the subdegrees of Sn acting on X(r) are 1, r 0 B@ n − r r − 1 1 CA , 0 B@ r 2 1 CA 0 B@ n − r r − 2 1 CA , 0 B@ r 3 1 CA 0 B@ n − r r − 3 1 CA , ..., 0 B@ r r − 1 1 CA 0 B@n − r 1 1 CA , 0 B@ n − r r 1 C A , after which the subdegrees are arranged in an ascending order. The suborbital graphs corresponding to the suborbits of Sn are then constructed and their properties analysed . It is shown that when Sn acts on X(r), its suborbital graphs are undirected and have girth three if n ≥ 3r.