t-Designs Possessing Automorphisms

Speaker: Mario-Osvin Pavcevic (University of Zagreb, Croatia)

Time: 4:00PM
Date: Mon 17th January 2011

Location: Mathematical Sciences Seminar Room

A t-(v,k,n) design consists of a v-element set of points P and of a collection B of k-element subsets of points called blocks, such that each t-element subset of points is contained in exactly n blocks. Every permutation of the set P is called an automorphism, if it preserves the incidences between points and blocks. So, the group of all automorphisms Aut(D) is joined to each t-design D in a natural way.

Very often, the only known way to decide whether a design with given parameters exists is, if possible, its explicit construction. In order to reduce the extremely large number of possibilities and to enable a construction of a t-(v,k,n) design exhaustively, it is natural to assume an action of an automorphism group on the design. For the very general setting of the Kramer-Mesner method developed for such a situation, it is in addition necessary to assume an action of the group on the set of points. This method transforms the construction problem into a linear system of diophantine equations and a lot of work has been done to find fast algorithms solving such systems. We have learnt a lot about this method from a group of mathematicians from Bayreuth, Germany (R. Laue, A. Wassermann, A. Kohnert).

The other known constructive method, which uses the fact that the point and block orbits of the design form a tactical decomposition, can be carried out if the action of the group on the set of points as well as on the set of blocks has been assumed properly. We explain which necessary conditions a tactical decomposition of a t-(v,k,n) fulfills. Here it is maybe worth mentioning some Croatian names whose attempt was successful many times in constructing 2-designs: Z. Janko, V. Cepulic, V. Krvcadinac.

We explain how to combine these two methods, applying the additional knowledge achieved from the coefficients of the tactical decomposition matrix in building the Kramer-Mesner matrix. We give examples which show how the number of columns of the Kramer-Mesner linear system can be largely reduced. We discuss the size of the problem of constructing t-designs with such kind of constraints, which depends on the group size and structure, hoping to be able to fill some gaps in the future for the existence problems for t-designs by combining these two mentioned methods.

(This talk is part of the Algebra/Claude Shannon Institute series.)