Classification Algorithms for Codes and Designs

✍ Scribed by Petteri Kaski, Patric R.J. Östergård (auth.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2006
• Tongue: English
• Leaves: 413
• Series: Algorithms and Computation in Mathematics 15
• Edition: 1
• Category: Library

✦ Synopsis

A new starting-point and a new method are requisite, to insure a complete [classi?cation of the Steiner triple systems of order 15]. This method was furnished, and its tedious and di?cult execution und- taken, by Mr. Cole. F. N. Cole, L. D. Cummings, and H. S. White (1917) [129] The history of classifying combinatorial objects is as old as the history of 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 classi?cation results. Almost a century earlier, in 1782, Euler [180] published some results on classifying small Latin squares, but for the ?rst few steps in this direction one should actually go at least as far back as ancient Greece and the proof that there are exactly ?ve Platonic solids. One of the most remarkable achievements in the early, pre-computer era is the classi?cation of the Steiner triple systems of order 15, quoted above. An onerous task that, today, no sensible person would attempt by hand calcu- tion. Because, with the exception of occasional parameters for which com- natorial arguments are e?ective (often to prove nonexistence or uniqueness), classi?cation in general is about algorithms and computation.

✦ Table of Contents

Introduction....Pages 1-5
Graphs, Designs, and Codes....Pages 7-45
Representations and Isomorphism....Pages 47-104
Isomorph-Free Exhaustive Generation....Pages 105-143
Auxiliary Algorithms....Pages 145-173
Classification of Designs....Pages 175-218
Classification of Codes....Pages 219-258
Classification of Related Structures....Pages 259-271
Prescribing Automorphism Groups....Pages 273-295
Validity of Computational Results....Pages 297-305
Computational Complexity....Pages 307-337
Nonexistence of Projective Planes of Order 10....Pages 339-364

✦ Subjects

Combinatorics; Computational Mathematics and Numerical Analysis; Coding and Information Theory; Communications Engineering, Networks; Signal, Image and Speech Processing