Kaski / Östergård Classification Algorithms for Codes and Designs

1. Auflage 2006
ISBN: 978-3-540-28991-3
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 15, 412 Seiten

Reihe: Algorithms and Computation in Mathematics

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.

Autoren/Hrsg.

Kaski, Petteri

Östergård, Patric R. J.

Inhaltsverzeichnis

1;Contents;5
2;Preface;9
3;1 Introduction;12
4;2 Graphs, Designs, and Codes;17
4.1;2.1 Graphs;17
4.2;2.2 Designs;23
4.3;2.3 Codes;36
4.4;2.4 More Combinatorial Objects;47
5;3 Representations and Isomorphism;56
5.1;3.1 Finite Groups and Group Actions;57
5.2;3.2 Categories and Equivalence;73
5.3;3.3 Isomorphism Computations;90
6;4 Isomorph-Free Exhaustive Generation;114
6.1;4.1 Exhaustive Generation;114
6.2;4.2 Techniques for Isomorph Rejection;123
7;5 Auxiliary Algorithms;153
7.1;5.1 Clique Algorithms;154
7.2;5.2 Exact Cover Algorithms;157
7.3;5.3 Set Cover Algorithms;160
7.4;5.4 Diophantine Linear Systems of Equations;163
7.5;5.5 Permutation Group Algorithms;167
7.6;5.6 Isomorphism Algorithms;172
7.7;5.7 Distributing Computer Search;179
8;6 Classification of Designs;182
8.1;6.1 Balanced Incomplete Block Designs;182
8.2;6.2 t-Designs;210
8.3;6.3 Resolutions of Designs;215
8.4;6.4 Designs with Additional Properties;222
9;7 Classification of Codes;226
9.1;7.1 Error-Correcting Codes;226
9.2;7.2 Covering Codes;241
9.3;7.3 Linear Codes;253
10;8 Classification of Related Structures;266
10.1;8.1 Triple Systems;266
10.2;8.2 Hadamard Matrices;272
10.3;8.3 Orthogonal Arrays;275
11;9 Prescribing Automorphism Groups;279
11.1;9.1 Preliminaries;280
11.2;9.2 Designs;283
11.3;9.3 Codes;297
11.4;9.4 Other Objects;301
12;10 Validity of Computational Results;302
12.1;10.1 Errors and Remedies;303
12.2;10.2 Double Counting Using the Orbit-Stabilizer;304
12.3;Theorem;304
12.4;10.3 Double Counting by Identifying Subobjects;306
12.5;10.4 Some Final Observations;310
13;11 Computational Complexity;311
13.1;11.1 Preliminaries;311
13.2;11.2 Completion Problems;318
13.3;11.3 Isomorphism Problems;327
13.4;11.4 Classi.cation Problems;334
14;12 Nonexistence of Projective Planes of Order 10;342
14.1;12.1 Projective Planes of Order 10;342
14.2;12.2 Codes of Designs;344
14.3;12.3 The Main Search;348
15;References;368
16;Problem Index;402
17;Index;403