| This book considers one of the basic problems in discrete mathematics: given a collection of constraints, describe up to isomorphism all the objects that meet them. Only a handful of classification results for combinatorial objects are dated before the mid-20th century; indeed, it is through modern computers and recent developments in algorithms that this topic has flourished and matured. This book is the first comprehensive reference on combinatorial classification algorithms, with emphasis on both the general theory and application to central families of combinatorial objects, in particular, codes and designs. The accompanying DVD provides an exhaustive catalogue of combinatorial objects with small parameters. The book will be of great interest to researchers and can be used as course material for graduate courses in both computer science and mathematics.
the objects themselves. In the mid-19th century, Kirkman, Steiner, and others became the fathers of modern combinatorics, and their work – on various objects, including (what became later known as) Steiner triple systems – led to several classification results. Almost a century earlier, in 1782, Euler [180] published some results on classifying small Latin squares, but for the first few steps in this direction one should actually go at least as far back as ancient Greece and the proof that there are exactly five Platonic solids.
One of the most remarkable achievements in the early, pre-computer era is the classification of the Steiner triple systems of order 15, quoted above. An onerous task that, today, no sensible person would attempt by hand calculation. Because, with the exception of occasional parameters for which combinatorial arguments are effective (often to prove nonexistence or uniqueness), classification in general is about algorithms and computation. |