Proving the Rearrangeability of Connecting Networks by Group Calculations

Proving the Rearrangeability of Connecting Networks by Group Calculations By V. E. BENES (Manuscript received May 30, 1974) Concepts and calculations from group theory have led to a new way of demonstrating rearrangeability of networks made of stages of square switches and to new factorizations of symmetric groups of composite degree. Telephone connecting networks usually consist of stages of switching that alternate with fixed cross-connect fields; in effect, these two kinds of units are used to build up desired connection patterns out of simpler permutations by composition (see Fig. 1). Since permutations form a group under composition, the notions of group theory have become relevant to the study of connecting networks. They are particularly useful for looking at desired combinatorial properties such as rearrangeability, which is the capacity to realize any permutation. This is true because, in the group-theoretic setting, the original Slepian-Duguid rearrangeability theorem 1 provides the possibility of factoring a symmetric group into a product of subgroups, or of double cosets of subgroups generated by stages. Here we extend a natural notion of "switch permutation" implicit in Duguid's proof to general networks with nr inlets and as many outlets. For such networks /i and v, we establish a group-theoretic condition on the sets D(n) and D(v) of switch permutations realized by fi and v, respectively, under which the larger network obtained by cascading n and v alternately between three stages of r n X n switches is rearrangeable.