Algorithmic Algebraic Combinatorics and Gröbner Bases

This collection of tutorial and research papers introduces readers to diverse areas of modern pure and applied algebraic combinatorics and finite geometries with a special emphasis on algorithmic aspects and the use of the theory of Gröbner bases. Topics covered include coherent configurations, association schemes, permutation groups, Latin squares, the Jacobian conjecture, mathematical chemistry, extremal combinatorics, coding theory, designs, etc. Special attention is paid to the description of innovative practical algorithms and their implementation in software packages such as GAP and MAGMA. Readers will benefit from the exceptional combination of instructive training goals with the presentation of significant new scientific results of an interdisciplinary nature. Preface......Page 5 Contents......Page 9 Contributors......Page 10 Part A Tutorials......Page 12 Introduction......Page 13 Main Notions......Page 14 Classification......Page 17 Regular Subgroups......Page 20 General Links Between Groups......Page 21 Factorization of Latin Square Graphs......Page 22 The Group Case......Page 23 Main Results......Page 24 The Case n=3......Page 25 The Case n=4......Page 28 The Case n=5, Part a......Page 30 The Case n=5, Part b......Page 31 The Case n=6......Page 36 Computer Aided Answer......Page 39 Further Computer-based Analysis with COCO......Page 40 General Idea......Page 43 Fulfillment of Axioms......Page 44 The Group Aut(S)......Page 45 Regular Subgroup for the Loop Case......Page 47 Exceptional Quasigroup Re-visited......Page 48 More Examples......Page 49 Some Preliminary Observations......Page 50 Defining Points and Lines......Page 51 Constructing a Transversal Design......Page 52 Automorphisms of the Design......Page 53 Analyzing the Results......Page 59 Pseudo-geometrical Graphs......Page 61 Order 5......Page 62 Order 6......Page 63 Q6......Page 65 Erich Schönhardt......Page 66 A Few Books......Page 67 More References......Page 68 References......Page 69 Introduction......Page 76 Coherent Configurations and Association Schemes......Page 78 Steiner Systems......Page 80 Kramer-Mesner Method and Related Issues......Page 81 Computations in Combinatorics......Page 83 COCO......Page 84 GRAPE......Page 85 Computer Algebra Experimentation......Page 86 Siamese Color Graphs......Page 87 Siamese Steiner Designs......Page 88 Siamese Graphs as Simultaneous Antipodal Covers......Page 89 Review of Main Results......Page 90 Data from COCO......Page 92 Theoretical Interpretation......Page 93 Automorphism Group of a Siamese Partition for STS(15)#1......Page 94 Summary of Known Results......Page 95 Faithful Actions of N on 15 Points......Page 97 Explicit Desired Action of N on 15 Points......Page 98 Analytic Enumeration of Orbits of (N,Omega{}3)......Page 99 Constructive Enumeration of Orbits of (N,Omega{}3)......Page 100 Summary of Results About N......Page 101 Starting Group......Page 102 Description of the Model of STS(15)#7......Page 103 All Siamese Color Graphs on 15 Points are Obtained......Page 104 Classical Objects......Page 105 Circulant Example......Page 106 One More Point-Transitive Example......Page 107 Other Siamese Objects......Page 108 Strategy A: Combinatorial Analogue of Transitive Extension......Page 109 Strategy C: Direct Enumeration of Siamese Color Graphs......Page 110 Further Perspectives......Page 112 Double Coset Enumeration......Page 113 Factorization of Graphs......Page 114 Weighing Matrices......Page 115 Group N=(S5xS3)+......Page 116 Empirical Observations......Page 117 References......Page 118 Introduction......Page 122 Gröbner Basis Preliminaries......Page 123 Algebraic Combinatorics Preliminaries......Page 125 Definitions......Page 126 An Application of SPolynomials and Reduction......Page 127 Structure Constants of Association Schemes......Page 128 Fusion......Page 129 Code and Output......Page 130 Concluding Remarks......Page 131 Appendix A......Page 132 References......Page 143 Introduction......Page 145 Finite Permutation Groups......Page 146 Combinatorial Search......Page 147 Search and Symmetry......Page 148 The Basic Algorithm......Page 149 Recycling Information......Page 150 Using the Stabilizer......Page 151 Avoiding Conjugation......Page 152 Enumerating Set Orbits......Page 153 Implementation......Page 154 Applications......Page 155 Generalized Hexagon......Page 156 References......Page 157 The 2-dimensional Jacobian Conjecture: A Computational Approach......Page 159 Introduction......Page 160 A Theorem of J. Hadamard......Page 166 Asymptotic and Sequential Asymptotic Values of Polynomial Maps......Page 167 The Asymptotic Values of a Polynomial Map C2->C2 form a Variety Which is the Union of Two Distinguished Algebraic Curves in C2......Page 168 The Resultant Formulation of the Jacobian Conjecture......Page 172 The Jacobian Conjecture in Dimension 2 is Decidable......Page 175 A Straight Forward Inductive Approach Fails......Page 179 Elementary Properties of Resultants of Jacobian Pairs......Page 182 Grading an Algebra with a Derivation - Introduction......Page 186 Grading an Algebra According to a Derivation......Page 187 The Structure of the D-classes......Page 188 Application to Automorphisms of Polynomial Rings......Page 189 Invertible Morphisms, Their Resultants and Inversion Formulas......Page 190 The Rigidity of Morphisms......Page 194 The Fibre Theorem......Page 199 One more Inversion Formula and an Equivalent Formulation to the Jacobian Conjecture......Page 200 Parametrization of the Jacobian Variety......Page 206 References......Page 209 Part B Research Papers......Page 212 Introduction......Page 213 Gröbner Bases and Standard Monomials......Page 215 The Hilbert Function......Page 216 Computation of the Lex Standard Monomials......Page 217 Generalization of the Fundamental Theorem of Symmetric Polynomials......Page 221 Wilson's Rank Formula......Page 224 Applications to Modulo q l-wide Families......Page 226 Modulo q L-intersecting, L-avoiding Families......Page 227 Set Families which do not Shatter Large Sets......Page 229 Harima's Theorem for Set Families......Page 230 References......Page 232 Motivation: Conformation Spaces in Chemistry......Page 234 Oriented Matroids, Chirotopes and Affine Point Configurations......Page 238 Isomorphism......Page 240 Radon Partitions and Oriented Circuits......Page 241 Partial Chirotopes......Page 242 The Generator origen......Page 243 Notes on the Generation Algorithm......Page 244 Comparison......Page 246 Application in Chemical Conformation Analysis: The Example Cyclohexane......Page 249 Acknowledgments......Page 252 References......Page 253 Introduction......Page 255 Preliminaries......Page 257 Primitive Association Schemes with Three Classes......Page 259 General Results......Page 264 Association Schemes of Type 2......Page 265 References......Page 269 Introduction and Motivation......Page 273 Parameters......Page 274 Constrution of Sets of Type (d1,d2)......Page 276 Example......Page 278 Results......Page 279 References......Page 280 Introduction......Page 283 Definitions and Notations......Page 284 Construction of Designs......Page 285 Experiments......Page 286 References......Page 287 Motivation and Background......Page 289 Ovoids in Nondegenerate (Parabolic) Quadrics in P6(Fq), q=3r......Page 291 p-Ranks Related to Projective Spaces......Page 292 p-Ranks via the Hilbert Function......Page 293 Computational Example......Page 294 Example: Projective n-Space......Page 295 p-Ranks Related to Polar Spaces and Grassmannians......Page 296 References......Page 298 Introduction......Page 301 Axioms......Page 302 Total Configuration......Page 303 GAP......Page 304 Definition and Basic Properties......Page 305 Structure Constants of S(n)......Page 306 Mergings of S(n)......Page 307 Definition and Basic Properties......Page 308 Structure Constants of S(n)......Page 310 S(n) and T(n)......Page 311 Details of Computer Search......Page 312 Conclusions......Page 313 References......Page 314

This collection of tutorial and research papers introduces readers to diverse areas of modern pure and applied algebraic combinatorics and finite geometries with a special emphasis on algorithmic aspects and the use of the theory of Gröbner bases.

Topics covered include coherent configurations, association schemes, permutation groups, Latin squares, the Jacobian conjecture, mathematical chemistry, extremal combinatorics, coding theory, designs, etc. Special attention is paid to the description of innovative practical algorithms and their implementation in software packages such as GAP and MAGMA.

Readers will benefit from the exceptional combination of instructive training goals with the presentation of significant new scientific results of an interdisciplinary nature.