The cycle type of the induced action on 2-subsetsEnumeration of symmetry classesGraphs

Graphs

Example: We would like to derive from Theorem a formula for the number of graphs on v vertices. Before we start doing so it should be mentioned that this example is the second typical example which we present. The first examples were devoted to the introduction of group theoretical concepts, to the derivation of Sylow's Theorem and to a number theoretic result of Fermat. The only example where a suitable choice of GX and Y was made in order to define and enumerate a mathematical structure was in fact the composition of two symmetric groups. As this example may have been a little bit artificial we admit that it is only now that we start to apply our paradigmatic actions more systematically. Let us see how suitably chosen G, X and Y can be used in order to define and enumerate the graphs on v vertices.(Later on we shall refine this method by counting these graphs according to the number of edges or according to their automorphism group. Finally we shall even use this Ansatz in order to construct such graphs and also to generate them uniformly at random.) The way of defining graphs as orbits of groups may at first glance seem to be circumstantial, but we shall see that this definition is very flexible since it can easily be generalized to all other kinds of graphs like multigraphs, directed graphs and so on.

Thus graphs, k-graphs, k-graphs with loops and also digraphs can be considered as symmetry classes of mappings. Several other structures will later on be obtained in the same way. Having defined the graphs this way we want to count them by an application of Theorem which means that we have to derive a formula for c( bar ( p)), the number of cyclic factors of bar ( p), the permutation induced by pÎS v on the set [v choose 2] of pairs of points, expressed in terms of the cycle structure of p. In fact we can do better, we can derive the cycle type of bar ( p) from the cycle type of p.


harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001

The cycle type of the induced action on 2-subsetsEnumeration of symmetry classesGraphs