Classification Algorithms for Codes and Designs
:
Petteri Kaski, Patric R.J. Östergård
:
Classification Algorithms for Codes and Designs
:
Springer-Verlag
:
9783540289913
:
1
:
CHF 104.40
:
:
Sonstiges
:
English
:
412
:
Wasserzeichen/DRM
:
PC/MAC/eReader/Tablet
:
PDF
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.
Contents
5
Preface
9
1 Introduction
12
2 Graphs, Designs, and Codes
17
2.1 Graphs
17
2.2 Designs
23
2.3 Codes
36
2.4 More Combinatorial Objects
47
3 Representations and Isomorphism
56
3.1 Finite Groups and Group Actions
57
3.2 Categories and Equivalence
73
3.3 Isomorphism Computations
90
4 Isomorph-Free Exhaustive Generation
114
4.1 Exhaustive Generation
114
4.2 Techniques for Isomorph Rejection
123
5 Auxiliary Algorithms
153
5.1 Clique Algorithms
154
5.2 Exact Cover Algorithms
157
5.3 Set Cover Algorithms
160
5.4 Diophantine Linear Systems of Equations
163
5.5 Permutation Group Algorithms
167
5.6 Isomorphism Algorithms
172
5.7 Distributing Computer Search
179
6 Classification of Designs
182
6.1 Balanced Incomplete Block Designs
182
6.2 t-Designs
210
6.3 Resolutions of Designs
215
6.4 Designs with Additional Properties
222
7 Classification of Codes
226
7.1 Error-Correcting Codes
226
7.2 Covering Codes
241
7.3 Linear Codes
253
8 Classification of Related Structures
266
8.1 Triple Systems
266
8.2 Hadamard Matrices
272
8.3 Orthogonal Arrays
275
9 Prescribing Automorphism Groups
279
9.1 Preliminaries
280
9.2 Designs
283
9.3 Codes
297
9.4 Other Objects
301
10 Validity of Computational Results
302
10.1 Errors and Remedies
303
10.2 Double Counting Using the Orbit-Stabilizer
304
Theorem
304
10.3 Double Counting by Identifying Subobjects
306
10.4 Some Final Observations
310
11 Computational Complexity
311
11.1 Preliminaries
311
11.2 Completion Problems
318
11.3 Isomorphism Problems
327
11.4 Classi.cation Problems
334
12 Nonexistence of Projective Planes of Order 10
342
12.1 Projective Planes of Order 10
342
12.2 Codes of Designs
344
12.3 The Main Search
348
References
368
Problem Index
402
Index
403
