Isomorph-Free Exhaustive Generation of Combinatorial Designs

Reference:

Petteri Kaski. Isomorph-free exhaustive generation of combinatorial designs. Research Report A70, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, December 2001.

Abstract:

This thesis investigates algorithmic isomorph-free exhaustive generation of balanced incomplete block designs (BIBDs), resolvable balanced incomplete block designs (RBIBDs), and the corresponding resolutions. In particular, three algorithms for isomorph-free exhaustive generation of -BIBDs and resolutions are described and applied to settle existence and classification problems.

The first algorithm generates BIBDs point by point using an orderly algorithm in combination with a maximum clique algorithm. The second and third algorithm generate resolutions of BIBDs by utilizing a correspondence between resolutions and certain optimal -ary error-correcting codes. The second algorithm generates the corresponding codes codeword by codeword, and is analogous in structure to the first algorithm. The third algorithm generates codes coordinate by coordinate, and is based on the recent isomorph-free exhaustive generation framework of Brendan McKay.

The main result of this thesis is a proof of nonexistence for a (15,5,4) RBIBD by exhaustive computer search. Other new classification results include the classifications of the - and -BIBDs and the -, -, and -RBIBDs together with their resolutions, which correspond to classifications of the , , and error-correcting -codes, respectively. Additionally, a number of earlier classification results are corroborated.

Keywords:

Balanced incomplete block design, error-correcting code, exhaustive search, group action, isomorph rejection, orderly algorithm, resolution, resolvable design

Suggested BibTeX entry:

@techreport{HUT-TCS-A70,
    address = {Espoo, Finland},
    author = {Petteri Kaski},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {December},
    number = {A70},
    pages = {125},
    title = {Isomorph-Free Exhaustive Generation of Combinatorial Designs},
    type = {Research Report},
    year = {2001},
}

NOTE: Reprint of Master's thesis; see URL below.
PostScript (1 MB)
GZipped PostScript (406 kB)
PDF (716 kB)
See www.tcs.hut.fi ...