Classification Algorithms for Codes and Designs (eBook)

Petteri Kaski, Patric R.J. Östergård (Autoren)

eBook Download: PDF

2006 | 2006
XI, 412 Seiten
Springer Berlin (Verlag)
978-3-540-28991-3 (ISBN)

Infos

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.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 3.2.2006
• Reihe/Serie: Algorithms and Computation in Mathematics
• Reihe/Serie: Algorithms and Computation in Mathematics
• Zusatzinfo: XI, 412 p.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Themenwelt: Technik ► Nachrichtentechnik
• Schlagworte: algorithms • classification • Codes • combinatorics • Complexity • Designs
• ISBN-10: 3-540-28991-7 / 3540289917
• ISBN-13: 978-3-540-28991-3 / 9783540289913