Algebraic Combinatorics in Bayreuth

A. Kerber

May 23, 1995

Abstract

I should like to give a brief introduction of our group, describe its main activities in the field of Algebraic Combinatorics, and illustrate them by a few typical examples.

1 Introduction

We are a small group of people working in the field of mathematics (my main field of research originally was the representation theory of symmetric groups, at present it is the constructive theory of discrete structures; Thomas Scharf’s main interest lies in the field of representation theory of symmetric groups and related classes of groups, Hecke algebras, Hopf methods etc.) or computer science (Reinhard Laue, who originally came from group theory, is also particularly interested in the constructive theory of discrete structures, algorithm design and data bases; Axel Kohnert is the designer of SYMMET-RICA and works on Schubert polynomials, Weintrauben and on symmetric functions in general). Let me mention already here, that a close and friendly cooperation between mathematics and computer science is absolutely crucial as soon as you really want to make efficient use of computers as a scientific tool, and if you want to deal with the constructive theory of discrete structures. Besides the people already mentioned who have regular positions, there are doctoral students. Christine Barop’s thesis will contain in particular a new approach to the projective matrix representations of the symmetric groups, or, in other words, the linear matrix representations of a covering group of the symmetric group. Christoph Benecke considers classification problems of deeply nested discrete structures, Thomas Wieland works on geometric placement problems. Several students are preparing their diploma theses, Anton Betten, Thomas Grüner and Markus Meringer in particular do construction of codes, geometries and graphs. Our joint research is focussed on Algebraic Combinatorics, in particular on the constructive theory of discrete structures, as I said already. The idea is to provide tools that are both general and efficient. A corresponding software package is now under development. Part of these tools is already available in

SYMMETRICA,

a powerful software package devoted to the representation theory and combinatorics of the symmetric group and of related classes of groups, for example, of wreath products of symmetric groups, of alternating groups and of general linear groups. Using this software package you can do enumeration under finite group action, Pólya theory, symmetric polynomials, group characters, matrix representations (both ordinary and modular) and many other things. SYMMETRICA is developed in cooperation with several colleagues, among which the groups around Alain Lascoux, Heinz Lüneburg and Alun Morris contributed parts of particular importance. For example, the world wide most efficient package on the plethysm of Schur polynomials is due to Christophe Carré, Rouen, the long integer arithmetic is based on a Pascal version due to Manfred Hain, Kaiserslautern. while the cyclotomic arithmetic is due to Tom McDonough, Aberystwyth. The extension and the progress of SYMMETRICA is the main goal of the network activities of our group. For this purpose we used the financial support for invitations of people from Paris and Marne la Vallée (Lascoux, Thibon, Leclerc) as well as Graz (Fripertinger) who made substantial progress with SYMMETRICA. The people from Paris and Marne la Vallée are working on Kostka-Foulkes polynomials, Schubert polynomials, noncommutative symmetric functions (see [5]), while H. Fripertinger implemented cycle index polynomials of linear groups which were applied already for the enumeration of linear codes (see [3]).

2 Discrete Structures

In order to begin with a brief review of what is going on at present in Bayreuth and in the field of Algebraic Combinatorics, here is a list of discrete structures that we met and which we were able to construct up to a certain extent:

• Graphs and multigraphs. Here is a multigraph:

[figure]

Obviously a multigraph can be considered as an interaction model (see e.g. [2]), where the edges indicate the strength of the interaction between the various objects indicated by the vertices. In many cases it is therefore of interest to construct the multigraphs with given number of vertices and with given vertex degrees. The next item shows a case when a construction of complete catalogs is even crucial for the purpose of application:

• Molecular graphs. One of the most famous examples is the following one:

C H C H  C Cl C O C C Cl C H C H C Cl C O C C Cl

The underlying graph is

• • • •  • • • • • • • • • • • • • • • • • •

This graph together with the coloring of the vertices by atom names (which is essential since there are atoms with the same valency 1 but with different names: H and Cl!) is called a molecular graph and it describes the interaction between the carbon, the oxygen, the chlorine and the hydrogene atoms. There are in fact 22 molecular graphs that have this underlying graph and which correspond to the chemical formula C_{12}O_{2}H_{4}Cl_{4}. (They are the 22 isomers of dioxin, and the isomer shown above is the most dangerous of them.) Thus a molecular graph is a (usually connnected) multigraph with a coloring of the vertices by atom names, and (optional) a prescribed substructure, for example, a prescribed skeleton graph, which is the underlying graph without the atoms of valence 1.

It is therefore very important in molecular structure elucidation to have a computer program at hand that generates all the mathematically possible molecular graphs corresponding to a molecular formula. MOLGEN is such a computer program which we have developed during the last ten years, it is quite efficient and already used in chemical research and industry (for a detailed description of the underlying algorithm see [7]).

• Error correcting linear codes are another interesting example. A lot of effort was made in the search for linear codes with good properties, i.e. which contain many code words but have a good minimal (Hamming) distance. Such linear codes are therefore considered as being equivalence classes of subspaces of finite vector spaces with respect to the group of all isometries that keep the Hamming distances fixed. As it will be described below, you can use cycle index polynomials of certain linear groups in order to count linear codes. They were implemented by H. Fripertinger, and a lot of tables were obtained which give their numbers for certain parameters and characteristics of the ground field. There is an interesting notion of indecomposability of linear codes, and a structure theorem says that each linear codes is an essentially unique direct sum of indecomposable linear codes, and so in particular the tables on the numbers of indecomposable linear codes are of interest. Such tables were known for the binary case, but the methods used by Fripertinger do hold for other characteristics, too. Here is such a table, it gives the numbers of ternary indecomposable linear (n, k)-codes:

\begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 5 & 1 & 3 & 3 & 1 & 0 & 0 & 0 \\ 6 & 1 & 5 & 10 & 5 & 1 & 0 & 0 \\ 7 & 1 & 7 & 24 & 24 & 7 & 1 & 0 \\ 8 & 1 & 10 & 55 & 105 & 55 & 10 & 1 \\ 9 & 1 & 13 & 116 & 403 & 403 & 116 & 13 \\ 10 & 1 & 17 & 231 & 1506 & 3000 & 1506 & 231 \\ 11 & 1 & 21 & 438 & 5425 & 23579 & 23579 & 5425 \\ 12 & 1 & 27 & 813 & 19440 & 199473 & 469473 & 199473 \end{matrix}

This table indicates that the numbers of indecomposable (n, k)-codes may form a unimodal and reciprocal sequence of natural numbers. The reciprocity is obvious, but the unimodality apparently not, but numerical evidence shows that it is a reasonable conjecture that all these sequences are in fact unimodal. (This is another example of pattern recognition, and I hope that a bijective proof of that in the spirit of the “Lotharingian Eye of Combinatorics” will be given soon!)

• t − (v, k, λ)–Designs form a further interesting class of discrete structures. They come from the design of experiments. For example, if you play lotto, you might ask the question if there is an optimal way of doing that in order to guarantee, say, that you have at least 5 hits (from six numbers which you marked, out of 49 as usual, say). This would mean to ask for a 5 − (49, 6, 1)–design (in words: each 5-subset of the correct 6-set out of the 49 numbers should be contained in exactly one block of 6 numbers indicated by the player). It can be shown that such a design does not exist, but that there do exist 5 − (48, 6, 1)–designs. Hence if you are willing to take the risk of ignoring a certain number, say 49, then you can do an optimal experiment which would guarantee a 5-hit (in fact altogether six 5-hits), as long as 49 does not occur among the chosen 6. But it should be mentioned that this would mean to fill 285 384 lotto forms at that particular weekend, which will keep you quite busy. Nevertheless this would be the optimal strategy. It is therefore clear that the search for designs is important in the design of experiments. During the last decade there was an intensive search going on for 6– and for 7–designs. Recently B. Schmalz opened a successful way to the construction of complete lists of designs with prescribed symmetry group, the corresponding isomorphism was solved on the basis of [14] in this case. B. Schmalz gave a lot of 6–designs, even for new sets of parameters (see [21]), but the question of the existence of 7–designs remained open. I shall come to this later.

From the foregoing it should have become clear that it is quite often important really to put the hands on discrete structures, which means that in many applications we need complete catalogs, and not just to know the number of possible structures. Therefore we have put a lot of effort into that, and we are using the network to improve the knowledge about that and the software which can support such applications. In order briefly to describe some of the main streams in our research on the constructive theory of discrete structures, in particular of graphs, molecular graphs, codes and designs, I should like to list some of the basic problems and principles, and then I shall demonstrate their use by nice examples.

3 Basic methods, principles and strategies

In order to prepare the description of some of the basic constructive principles, we recall that the theory of a discrete structure, for example graph theory, is done in steps, some of which are the following ones. (It is in fact the case that each of these steps is important for the next one. Usually the way the i-th step is done can make the (i + 1)-st step easy or difficult, and, moreover, quite often the result of the i-th step is crucial for the next one. For example, if the result of the i-th step is a number of discrete structures, then this number can be used in one of the next steps, say in the construction or generation, quite often as a stopping rule, since it tells us when the construction is finished.)

• The first step clearly is the definition. Already this step should be done carefully, so that the following steps can be done easily. For example, there is usually a labelled form of the discrete structure in question, and an unlabelled form of it, which mostly is the more interesting one. The incidence structures are a typical case of this. They consist of points, lines, edges, planes, and so on, but it is obvious that the nature of the points doesn’t really matter. An incidence structure obtained by renumbering is not essentially different from the original one, it is equivalent or isomorphic to it. Hence the unlabelled form is usually defined to be an equivalence or, better say, an isomorphism class of the labelled form. In order to prepare the next step we therefore describe it as an orbit of a suitable finite group on a suitable finite set, if possible. For example, an unlabelled graph on v vertices can be defined as an orbit of the symmetric group S_{v} on the set of mappings from the set of numbers of pairs of points \{1, …, \binom{v}{2}\} into the set \{0, 1\} (if we want to get simple graphs only), or into the set {0, 1, …, m} if we want multigraphs with multiplicity of bonds restricted by m, say. In the case we want to obtain directed graphs (with loops allowed) we can simply take {1, …, v^{2}} as the range set, and so on. Hence such definitions should also be quite flexible.

• The second step may be the enumeration of all the structures with given parameters, for example, the graphs with given number of vertices. Having defined the unlabelled graphs as orbits of a symmetric group on the set of mappings from the set of pairs of vertices into the set {0, 1}), we can use the well–known Lemma of Cauchy–Frobenius, in order to count the number of (unlabelled simple) graphs with given number of vertices. The resulting numbers — of graphs or multigraphs with given number of vertices, say — can be used as a stopping rule later on when it comes to the construction. They tell us when we are ready. It also helps in the generation of graphs with given number of vertices uniformly at random, since these numbers show up in certain probabilities that have to be evaluated.

• The next step quite often is the refinement of the enumeration, say the enumeration by weight. In the case of graphs it is the enumeration of all the graphs with given number of vertices and prescribed number of edges. In order to do this, for example, in the case of graphs we need only to replace the classical constant form of the Lemma of Cauchy– Frobenius by its so–called weighted form. And it is interesting to see that this weighted form of the lemma is as easy to prove as the constant form. From this we can easily obtain the basic result of Pólya on the enumeration of graphs by number of vertices and edges. The result is a generating function, a polynomial — mostly multivariate — the coefficients of which are the desired numbers. In the case of the Pólya theory of enumeration this generating function is obtained from the so-called cycle index polynomial by a well-defined so-called Pólya substitution. This fact gives, among other things, a lot of interesting results on the unimodality of such generating functions (it can be shown, for example, that a Pólya substitution of a unimodal polynomial with natural coefficients into a cycle index of a finite group gives a unimodal polynomial again!). Moreover it allows to do a lot of interesting combinatorics in the “Lotharingian Spirit”. The generating functions are symmetric polynomials and therefore linear combinations of Schur polynomials, the coefficients of which are easily described in terms of representation theory of symmetric groups. But there are also some interesting open problems left: Since Schur polynomials count tableaux, it is natural to ask what these tableaux have to do with the discrete structure that was just counted. This is still open, even in the graph case!

• Furthermore we can also prescribe the symmetry group, prescribe the symmetry group together with the weight, and so on. These refinements need, of course, more information on the acting group. In fact, we need to have the table of marks at hand, which Burnside introduced. In order to evaluate that table there is a lot of information necessary about the lattice of subgroups of the group in question. Hence these refining steps rapidly become more difficult, and the question becomes urgent, if there is a way of carefully analyzing suitable actions, say, in order to obtain the table of marks without having to evaluate the subgroup lattice (or, at least, the poset of conjugacy classes of subgroups) in full detail.

• The most ambitious step is, of course, the construction of all the structures with given parameters, weight, symmetry group etc. Since we want (or even have to be able, like in the molecular structure elucidation case) to put our hands really on these discrete structures, like graphs, molecular graphs, codes and designs, we are in particular interested in this quite difficult step. In order to do this, we use a mixture of combinatorial and of algebraic algorithms, some basic principles of them will be described and illustrated here.

• Clearly, it is in many cases not possible to evaluate in the constructive step all the structures with given properties. In these cases nevertheless it is often helpful and interesting to provide an algorithm that allows to generate structures with given parameters uniformly at random. If such an algorithm is available (which is true for the cases when the structure in question can be defined as an orbit of a finite group on a finite set) and implemented, then we can check hypotheses on the structure in question. For example, we can check if invariants are good or even complete, find counterexamples, and so on. It is easy to find this way a pair of nonisomorphic labelled graphs with the same set of eigenvalues of the adjacency matrices, showing this way that the spectrum is not a complete invariant for simple graphs. We also used this in order to check the quality of generalized matrix function applied to the adjacency matrix of simple graphs.

Between these steps there is room for a lot of further research, the evaluation of generating functions, the examination of the sequences of coefficients, which are unimodal in many cases, and so on. And it is interesting to see how the permanent struggle against the complexity of all these difficult problems gives rise to new mathematical problems, results, algorithms, conjectures, etc.

4 A Quite General Ansatz

Many discrete structures can be defined as equivalence classes on sets of mappings Y^{X} between finite sets. An example was mentioned above: The labelled simple graphs on v vertices can be considered as mappings from the set of pairs of vertices, or, in formal terms, from the set X := \{1, …, \binom{v}{2}\} into the set Y := {0, 1} of all the possible multiplicities of edges joining these pairs. Thus a labelled graph is an element

f ∈ Y^{X} := \{f: X → Y \}, where X := \{1, …, \binom{v}{2}\}, Y := 2 := \{0, 1\}.

In contrast to this, an unlabelled graph on v vertices is an orbit of the symmetric group S_{v} on this set of mappings, induced by the action of this group on the set of vertices (which again induces a canonical action on the set of pairs, which again induces a canonical action on the set of mappings). Hence, the set of unlabelled graphs on v vertices can be identified with the set of orbits

S_{v}\\2^{\binom{v}{2}}.

More generally, in Pólya’s theory of enumeration, we consider such sets of mappings Y^{X} together with actions of G, H, H × G and H ≀ G which are induced from actions of G on X and H on Y in a canonic way (see e.g. [11] for details):

• G × Y^{X} → Y^{X}: (g, f) ↦ f ∘ g^{−1},

• H × Y^{X} → Y^{X}: (h, f) ↦ h ∘ f,

• (H × G) × Y^{X} → Y^{X}: ((h, g), f) ↦ h ∘ f ∘ g^{−1},

• (H ≀ G) × Y^{X} → Y^{X}: ((ψ, g), f) ↦ f̃, f̃(x) := ψ(x)f(g^{−1}x).

One of the aims we have is to cover at least these four cases, which means to be able efficiently to enumerate, construct and generate discrete structures that can be defined as orbits of such actions. Let me briefly mention what can be done for these cases and why it is useful to know about these methods. To begin with, it is important to note that in principle we can reduce all these cases to the first one, where a a group G is acting on X and where we consider the corresponding action of G on Y^{X} by g: f ↦ f ∘ g^{−1}. The reason is that there exist bijections

1. (H × G)\\Y^{X} ⟶ G\\ (H\\(Y^{X})) .

2. (H ≀ G)\\Y^{X} ⟶ G\\ ((H\\Y)^{X}) .

The first bijection is due to de Bruijn, as far as I know, the second one is due to W. Lehmann ([17],[18]). A particular example which was already mentioned is the case of the linear codes. These linear codes are subspaces of finite vector spaces GF (q)^{n}, which we assume to be equipped with the Hamming distance. Therefore we consider two subspaces of dimension k, say, as being essentially the same, if we can obtain one from the other via an isometry. It can be shown that the isometries form the group of monomial matrices, which is in fact the wreath product

M_{n}(q) := GF (q)^{∗} ≀ S_{n},

and so the isometry classes of linear codes are the orbits of this group on GF (q)^{n}. The problem is that these subsets form quite an abstract entity and that we can only put our hands on them by introducing bases. Again we are therefore faced with a labelled and an unlabelled structure. The set of labelled structures is the set of generator matrices, i.e. (by Gauss’ algorithm) an orbit of the general linear group GL_{k}(q) on the set GF (q)_{k}^{k×n} of all the k × n-matrices over GF (q) which are of rank k :

GF (q)_{k}^{k×n} ⊆ Y^{X} := (GF (q)^{k})^{n}.

The set of all these orbits satisfies the inclusion

GL_{k}(q)\\GF (q)_{k}^{k×n} ⊆ GL_{k}(q)\\(GF (q)^{k})^{n}.

Hence the set of unlabelled structures, i.e. the set of isometry classes of linear codes of dimension k in GF (q)^{n}, is the set of orbits

(GL_{k}(q) × GF (q)^{∗} ≀ S_{n})\\GF (q)_{k}^{k×n} ⊆ (GL_{k}(q) × GF (q)^{∗} ≀ S_{n})\\(GF (q)^{k})^{n}.

It is now crucial to note (H. Fripertinger pointed to this) that, according to the bijection of Lehmann, this set of orbits is bijective to the set

S_{n}\\ (GF (q)^{∗}\\GF (q)^{k})^{n} .

This bijection clarifies a lot of things in linear coding theory which at first glance look astonishing. To begin with, let us recall that the set of orbits

GF (q)^{∗}\\GF (q)^{k}

is the set of k-tuples of onedimensional subspaces of GF (q)^{k} and so this explains why the projective spaces enter coding theory. Moreover, we recall that the orbits of the symmetric group S_{X} on Y^{X} are the sets of mappings of different weight, and so the set of mappings of weight (1, …, 1) is of particular interest, and these are in fact the well-known Hamming Codes. For more details cf. [4]. Thus it is useful to have a clear cut definition of a structure as an orbit of a finite group on a finite set of mappings in order to understand what is going on in this particular theory. The next step is the evaluation of orbit representatives. Here it turned out that an appropriate philosophy is that of looking for a transitive group and then using the fact that the orbits of the group in question are in bijection with double cosets. Here is the crucial lemma: If a group A acts on a set M, then the set of orbits of a subgroup U ≤ A on an orbit A(m) of A has a canonic bijection onto the set of (U, G_{m})-double cosets as follows:

U\\A(m) ⟶ U\A/G_{m}: U(am) ↦ UaG_{m},

for any m ∈ M and its stabilizer G_{m}. So the philosophy behind this is to look for transitive groups. Such transitive groups do always exist, since there are the symmetric groups. But usually these groups are much too big. So what we do is to impose further conditions in order to find smaller transitive groups. For example, in the case of graphs, we can restrict attention to the graphs with given numbers of points and edges, in which case we can take the symmetric group S\binom{v}{2} instead of the full symmetric group on 2^{\binom{v}{2}}. It remains to discuss the evaluation of a transversal of the set U\A/G_{m} of double cosets from which we then obtain the desired transversal of the set U\\A(m) of orbits. For this purpose the ladder game is at hand which B. Schmalz invented and used for the evaluation of designs with prescribed automorphism groups ([20],[21],[22]). It was applied to the following situation: The Kramer/Mesner matrix of a design on a set V consisting of v vertices with a given automorphism group A ≤ S_{v} has columns labelled by the elements of a transversal of A\\\binom{V}{k} and rows labelled by the elements of

a transversal of A\\\binom{V}{t}. So, as the symmetric group S_{v} acts transitively both

on \binom{V}{k} and \binom{V}{t}, we are faced with the problem of evaluating transversals of A\S_{v}/S_{(v−k,k)} and of A\S_{v}/S_{(v−t,t)} where the Young subgroups S_{(v−k,k)} and S_{(v−t,t)} are stabilizers of a k- and of a t-subset of the set of vertices, respectively. The ladder game allows to solve these two problems in one wash by going along a sequence of Young subgroups which starts from S_{v} and which ends in S_{(v−k,k)} and where in between these two groups the Young subgroup S_{(v−t,t)} occurs (note that t ≤ k). Since the double cosets are unions of left cosets, on which the automorphism group A is acting by left multiplication, the following basic principle applies (for a detailed discussion and applications of this principle see [15]): The Homomorphism Principle Assume that a finite group G is acting on two finite sets M and N and that there exists a surjective mapping φ: M → N which is compatible with the two group actions:

φ(gm) = gφ(m).

Then the following is true:

• The image of a transversal T of the set of orbits of G on M, in formal

terms, the image of

T (G\\M)

contains a transversal of the set of orbits G\\N of G on N.

• The inverse images φ^{−1}(n) of the elements of N are blocks (which means that they are permuted amongst each other by the action of G). Since φ is assumed to be surjective, these inverse images therefore form a decomposition of M into blocks with respect to the action of G.

• The stabilizer of n ∈ N is the setwise stabilizer of the inverse image φ^{−1}(n). Therefore we can obtain a transversal T_{M} of the orbits of G on M from a transversal T_{N} of the orbits of G on N in the following way:

– Compute, for each n ∈ T_{N}, its stabilizer G_{n}.

– Compute the inverse images B_{n} := φ^{−1}(n).

– Compute, for each of these blocks, a transversal

T (G_{n}\\B_{n}).

Then the following set is a transversal of the orbits of G on N :

T (G\\M) := ⋃_{n∈T_{N}} T (G_{n}\\B_{n}).

This principle is essential for the evaluation of double coset transversals using Schmalz’ ladder game. Here is a very recent application of it which lead to the discovery of the very first 7-designs with moderate parameters. Assume that we are asking for the existence of 7 − (33, 8, 10) designs. A brute force attack would need to answer the question for the existence of 0-1-solutions of a system of linear equations over the integers with a matrix of coefficients of size \binom{33}{7} × \binom{33}{8}, containing approximately 7 · 10^{13} coefficinets, and so there is no hope of affirmatively answering this question for a solution. But if we impose a further condition (this is, of course, risky, since there may be no designs with that additional property) we get it into the reach of present computers. The suggested condition was to assume that the group P ΓL(2, 32) is a group of automorphisms. Supposing this we can use the theorem of Kramer and Mesner, which reduces the problem to the existence of 0-1-solutions of a system of linear equations of size

(P ΓL(2, 32)\\\binom{33}{7}) × (P ΓL(2, 32)\\\binom{33}{8}) = 32 × 97.

The crucial point is that the number of entries of that matrix, compared with the other one, is reduced by the factor 2.3 · 10^{10}, which shows the enormous reduction of complexity by imposing the existence of that group of automorphisms! The entries of the matrix were evaluated by A. Betten using the homomorphism principle mentioned above. Here is the ladder of Young subgroups which was used:

[figure: S_{(7,1,25)}; S_{(8,25)}; S_{(7,26)}; S_{(2,1,30)}; S_{(3,30)}; S_{(2,31)}; S_{(1,1,31)}; S_{(1,32)}; S_{33}; ⋮; 8; 26; 3; 31; 2; 32; 33]

The numbers attached to the edges of the graph give the size of the steps, and they indicate that this ladder game gives another reduction of the complexity. Instead of having to evaluate a transversal of a set of more than 17 · 10^{6} left cosets of S_{(8,25)} in S_{33} in one wash, it is only needed to do orbit caculations in sets of sizes 33, 32, 2, 31, …, 26, 8, one after the other. The complexity is “logarithmically reduced” by the ladder game. Thus it was easy to evaluate that matrix (which was in fact already known, but this is not the point, since the ladder game allows to evaluate such matrices in cases of which one could only dream before).

After the evaluation of the Kramer/Mesner matrix by A. Betten, the final step was made by A. Wassermann, who implemented a modern version of the LLL-algorithm which he adapted to this particular problem. A run on a PC then finally settled the question for the existence of 7-designs with moderate parameters, the answer is: Yes, there do exist 7 − (33, 8, 10)-designs, and therefore also 7 − (33, 8, 16)-designs! The first one was found by the end of 1994, in the meantime and in cooperations with Brendan MacKay, Canberra, several thousand further ones were found, but the complete set of such designs is not known yet (for details see [1]). Besides, for the evaluation of the Kramer/Mesner matrix we used the homomorphism principle in order to provide a recursion procedure for the evaluation of transversals of the form G\\Y^{X}. The recursion is by the order of Y. This allows to obtain, for example, multigraphs with bounded multiplicity of bonds, from simple graphs. These methods, principles and algorithms are, in a sense, algebraic ones. But we should not forget that all this needs a good mixture of algebraic and of combinatorial reasoning. So let me finally mention one of the most important tools we took from combinatorics: The orderly generation, a method introduced by R. C. Read in his paper “Every One a Winner” ([19]). The basic idea is to order the set M on which the group in question is acting and to make use of the fact that in this case we have canonic transversals, consisting either of the biggest (or of the smallest, if you prefer) elements in their respective orbits. Details about this were given in [10].

5 Summary

Let me try to summarize our experiences and activities within the network on algebraic combinatorics in a few items:

• We are very thankful for the financial support given by that network, and we use it in particular for extensions of SYMMETRICA.

• The extensions we have in mind are in particular devoted to the constructive theory of discrete structures. The discrete structures in question are defined as orbits of finite groups on sets of mappings. Examples are graphs, molecular graphs, linear codes, designs etc.

• We already extended SYMMETRICA by implementing and incorporating new programs for cycle indices of linear groups. Moreover several activities were devoted to symmetric functions, both with commuting and with noncommuting indeterminates.

• For constructive purposes we considered applications of the homomorphism principle to the evaluation of double coset transversals. One of the results was the recent discovery of the very first 7-designs with moderate parameters.

• The intention is to continue this in cooperation with other groups of the network,within the Séminaire Lotharingien de Combinatoire and in the “Lotharingian Spirit”, using, in terms of A.Garsia, the Lotharingian Eye of Combinatorics.

• In addition to these discrete methods we shall continue the development of representation theoretical aspects, too. The projective matrix representations of symmetric groups were recently achieved, a program was implemented. A new version is in preparation, it will be ready very soon.

• Close cooperation with several groups will go on, in particular I should like to mention the groups in Paris, Marne la Vallée, Aberystwyth, Graz.

• Some of the applications are relevant for industry, too. The computer package MOLGEN that allows to construct all the molecular graphs corresponding to certain conditions (molecular formula, prescribed and forbidden substructures etc.) is already used in chemical research and industry.

References

[1] A. Betten, A. Kerber, A. Kohnert, R. Laue, A. Wassermann. The Discovery of Simple 7-Designs with Automorphism Group P ΓL(2, 32). (to appear in Springer LNCS).

[2] N.L.Biggs. Interaction Models. Cambridge University Press, 1977.

[3] H. Fripertinger. Enumeration of isometry-classes of linear (n, k)- codes over GF (q) in SYMMETRICA. Bayreuther Mathematische Schriften 49 (1995), 215–223.

[4] H. Fripertinger, A. Kerber. Isometry Classes of Indecomposable Linear Codes. (to appear in Springer LNCS).

[5] I.M. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V.S. Retakh, and J.-Y. Thibon. Noncommutative symmetric functions. Adv. Math. 112 (1995), 218-348.

[6] R. Grund. Symmetrieklassen von Abbildungen und die Konstruktion von diskreten Strukturen. Bayreuther Mathematische Schriften 31 (1990), 19–54.

[7] R. Grund. Konstruktion molekularer Graphen mit gegebenen Hybridisierungen und überlappungsfreien Fragmenten. Bayreuther Mathematische Schriften 49 (1995), 1–113.

[8] R. Grund, A. Kerber, and L. Laue. Construction of discrete structures, especially isomers. to appear in Appl. Discr. Math.

[9] R. Grund, A. Kerber, and R. Laue. MOLGEN, ein Computeralgebra-System für die Konstruktion molekularer Graphen. MATCH, 27, S. 87–131, 1992.

[10] R. Hager, A. Kerber, R. Laue, D. Moser, and W. Weber. Construction of orbit representatives. Bayreuther Mathematische Schriften, 35, S. 157–169, 1991.

[11] A. Kerber. Algebraic Combinatorics Via Finite Group Actions. BI-Wissenschaftsverlag, Mannheim, Wien, Zürich, 1991.

[12] D. E. Knuth. The Art of Computer Programming, vol 3. Addison– Wesley, 1973.

[13] A. Kohnert, S. Veigneau. Using Schubert toolkit to compute with polynomials in several variables. (in preparation).

[14] R. Laue. Eine konstruktive Version des Lemmas von Burnisde. Bayreuther Mathematische Schriften, 28, S. 111–125, 1989.

[15] R. Laue. Construction of combinatorial objects – a tutorial. Bayreuther Mathematische Schriften, 43, S. 53–96, 1993.

[16] B. Leclerc, Th. Scharf, J.-Y. Thibon. Non commutative cyclic characters of symmetric groups. (submitted to JCTA).

[17] W. Lehmann. Das Abzähltheorem der Exponentialgruppe in gewichteter Form. Mitt. Math. Sem. Univ. Gießen, 112 (1974), 19-33.

[18] W. Lehmann. Ein vereinheitlichender Ansatz für die REDFIELD-PÓLYA-de BRUIJNsche Abzählungstheorie. Doctoral thesis, Gießen 1976.

[19] R.C. Read. Every one a winner. Ann. Discr. Math., 2, S. 107–120, 1978.

[20] B. Schmalz. Verwendung von Untergruppenleitern zur Bestimmung von Doppelnebenklassen. Bayreuther Mathematische Schriften, 31, S. 109–143, 1990.

[21] B. Schmalz. t-Designs zu vorgegebener Automorphismengruppe. Bayreuther Mathematische Schriften, 41, S. 1–164, 1992.

[22] B. Schmalz. The t-designs with prescribed automorphism group, new simple 6-designs. J. Comb. Designs, 1, S. 125–146, 1993.