Finding simple t-designs by using basis reduction

Show full item record

Title: Finding simple t-designs by using basis reduction
Author: Kreher, Donald; Radziszowski, Stanislaw
Abstract: In 1976, Kramer and Mesner observed that finding a t-design with a given automorphism group can be reduced to solving a matrix problem of the form AX=M, X[i]=0 or I, for all i, I<=i<=n, where A is an m by n positive integer matrix built from the required automorphism group and M is a particular m dimensional integer vector. This problem is NP-complete. We present an algorithm that searches for a solution when given an instance of This 0-1 matrix problem. This algorithm always halts in polynomial time but does not always find a solution when one exists. The problem is first converted to one of finding a particular short vector in a lattice and then uses a lattice basis reduction algorithm due to A.K. Lenstra, H.W. Lenstra and L. Lovasz [9] to attempt to find it. We apply this method to the search for simple t-designs with t>=6 and duplicate the results of Leavitt, Kramer and Magliveras [3,10] in substantially shorter time. Furthermore, a new simple 6-design was found using the algorithm described in this paper
Record URI: http://hdl.handle.net/1850/8777
Date: 1986

Files in this item

Files Size Format View
SRadziszowskiArticle1986.pdf 3.384Mb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse