Algorithmic Algebraic Combinatorics and Gröbner Bases

✍ Scribed by Mikhail Klin, Gareth A. Jones, Aleksandar Jurisic, Mikhail Muzychuk, Ilia Ponomarenko

• Publisher: Springer
• Year: 2009
• Tongue: English
• Leaves: 315
• Edition: 1st Edition.
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

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