Classification algorithms for codes and designs (Q819932): Difference between revisions

The authors of this book have been responsible for some quite remarkable combinatorial enumeration results in recent years, including the very impressive classification of the more than \(11\) billion Steiner triple systems of order \(19\). They are therefore well-qualified to provide this comprehensive survey of state-of-the-art algorithms for the classification of codes and designs. As implied by the title, the book is restricted to exhaustive rather than probabilistic methods. The three types of problems focused on are (i) existence, which is to decide whether an object with a given set of properties exists, (ii) counting, which is to count the number of distinct objects with a given set of properties, and (iii) classification, which is to generate the set of objects with a given set of properties, up to some criterion of equivalence. This reviewer personally prefers the term enumeration to describe the last problem, as classification can take on the meaning of partitioning a set of objects according to many types of properties, not only isomorphism. However, it is accepted that enumeration has been confused with counting in the literature. Perhaps it is time for a new term to be used here. Efficient algorithmic methods are an important adjunct to mathematical construction and analysis techniques, as they allow larger base collections of objects to be generated and analysed so that counterexamples or conjectures can be formulated. They also provide the basis for inductive constructions that allow infinite families of objects to be constructed. Such techniques have progressed enormously since their first use in the late 1960s so that now, with the massive increase in power of computers, they provide a very powerful tool set indeed. The authors begin by defining the various types of codes and designs to which these classification algorithms can be applied. Many of these structures can be represented as graphs, and so graph analysis and classification algorithms are highly relevant. In fact, many of the techniques can be applied to more general incidence structures of which graphs, codes and designs are only a particular type. Central to classification is the problem of exhaustively generating, without isomorphs, all objects meeting a collection of constraints. The implementation of isomorph rejection techniques (first investigated by Swift in 1960) is therefore critical in such algorithms. Such techniques are necessary to both guarantee that the final list of objects are all pairwise non-isomorphic and also to avoid unnecessary work during the computation. The traditional approach has been to keep a list of objects generated so far and to check whether the latest object is isomorphic to any in the list. However, the technique of orderly generation introduced by Read in 1978 uses a canonicity test to check, without resorting to lists, whether the latest object is the chosen (canonical) representative of its class. The technique of canonical augmentation introduced by McKay in 1998 further improves this process. These methods are described in Chapter 4. Checking for canonicity and performing isomorph rejection makes heavy use of the automorphism groups of partial structures generated during the search. Algorithms for generating and manipulating groups are therefore covered extensively in Chapter 5. Other auxiliary algorithms for finding cliques and set covers, and for solving Diophantine linear systems of equations are also discussed here, as many design problems can be formulated in these settings. Algorithms specifically for the classification of designs are covered in Chapter 6. Here the idea of a seed is introduced as a basis for the process of canonical augmentation and to provide a means of spreading the generation load over a set of processors. The authors draw heavily on their STS(\(19\)) classification as an example of this process. Algorithms for codes and other types of combinatorial structures, including Latin squares, 1-factorizations of complete graphs, Hadamard matrices and orthogonal arrays, are covered in Chapters 7 and 8. Chapter 9 is devoted to the problem of classifying combinatorial objects with prescribed automorphism groups. The celebrated Kramer-Mesner method, which has been applied successfully to construct many large \(t\)-designs, is discussed in detail, along with the use of tactical decompositions. The authors also describe how these methods can be applied to various types of codes. A valuable part of the text is Chapter 10 where the validity of computational results is discussed. While a positive existence result can be quickly confirmed by a feasibility check of the constructed object, a classification result can never be completely validated as it has arisen from the output of quite sophisticated software running for generally long periods of time on a range of computers. All we can do is to take the steps outlined in this chapter in order to increase our confidence in the end result. Important among these techniques is double counting using the orbit-stablizer theorem. Chapter 11 covers the theory of computational complexity, which can be used to provide a framework for assessing how efficiently we can perform a classification task. Very few combinatorial construction problems have been shown to be NP-hard. Nevertheless, these problems appear to be intractable, and this belief extends to classification where it appears that, apart from a few exceptions, it is unlikely that classification can be performed by polynomial-delay algorithms. The authors expand on these challenges and point to possible areas of further research. Finally the authors discuss the famous 1989 result of Lam, Thiel and Swiercz that there exists no projective plane of order \(10\). The chapter nicely ties together the theory and algorithms discussed in the book, and indeed forms a most appropriate conclusion. Useful to researchers in the area is an accompanying companion DVD which contains lists of various types of balanced incomplete block designs, resolutions of balanced incomplete block designs, optimal error-correcting codes, optimal covering codes, optimal linear codes, one-error-correcting linear codes, 1-factorizations of complete graphs, Latin squares, and Hadamard matrices. Overall the book is a timely and authoritative work, and an extremely valuable reference for any researcher working in the field of combinatorial classification.