Classification Algorithms for Codes and Designs (eBook)

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