Strongly Regular Graphs

Description

Strongly regular graphs lie at the intersection of statistical design, group theory, finite geometry, information and coding theory, and extremal combinatorics. This monograph collects all the major known results together for the first time in book form, creating an invaluable text that researchers in algebraic combinatorics and related areas will refer to for years to come. The book covers the theory of strongly regular graphs, polar graphs, rank 3 graphs associated to buildings and Fischer groups, cyclotomic graphs, two-weight codes and graphs related to combinatorial configurations such as Latin squares, quasi-symmetric designs and spherical designs. It gives the complete classification of rank 3 graphs, including some new constructions. More than 100 graphs are treated individually. Some unified and streamlined proofs are featured, along with original material including a new approach to the (affine) half spin graphs of rank 5 hyperbolic polar spaces. Contents Preface 1 Graphs 1.1 Strongly regular graphs 1.2 Distance-regular graphs 1.3 Association schemes and coherent configurations 2 Polar spaces 2.1 Polar spaces 2.2 Embedded polar spaces 2.3 Classification of finite embedded polar spaces 2.4 Witt’s theorem 2.5 Symplectic polar spaces 2.6 Orthogonal polar spaces 2.7 Hermitian or unitary polar spaces 3 Graphs related to polar spaces 3.1 Graphs on the nonsingular or nonisotropic points 3.2 Graphs on half of the maximal singular subspaces 3.3 Affine polar graphs 3.4 Forms graphs 3.5 Grassmann graphs 3.6 The case q = 2 4 Buildings 4.1 Geometries 4.2 Coxeter systems 4.3 Coxeter geometries 4.4 Coxeter geometries of types A𝑛, D𝑛 and E6 4.5 Buildings 4.6 The Klein quadric and Klein correspondence 4.7 Triality 4.8 A construction of G2(𝑞) 4.9 The E6,1(𝑞) graph 5 Fischer spaces 5.1 Definition 5.2 Fischer’s classification 5.3 Hall triple systems 5.4 Cotriangular graphs 5.5 Locally grid graphs 5.6 Copolar spaces 6 Golay codes, Witt designs, and Leech lattice 6.1 Codes 6.2 Designs 6.3 Lattices 7 Cyclotomic constructions 7.1 Difference sets 7.2 Cyclic codes 7.3 Cyclotomy 7.4 One-dimensional affine rank 3 groups 7.5 Icosahedrals 7.6 Bent functions 8 Combinatorial constructions 8.1 Regular Hadamard matrices with constant diagonal 8.2 Conference matrices and conference graphs Conference matrices 8.3 Symmetric designs 8.4 Latin squares 8.5 Quasi-symmetric designs 8.6 Partial geometries 8.7 Semipartial geometries 8.8 Zara graphs 8.9 Terwilliger graphs 8.10 Regular two-graphs 8.11 Pseudocyclic association schemes 8.12 Tensor products of skew schemes 8.13 Cospectral graphs 8.14 Equiangular sets of lines 8.15 Spherical designs 8.16 Higher regularity conditions 8.17 Asymptotics 8.18 Conditions in case 𝝁 = 1 or 𝝁 = 2 8.19 Coloring 8.20 Graphs that are locally strongly regular 8.21 Dropping regularity 8.22 Directed strongly regular graphs 9 p-Ranks 9.1 Points and hyperplanes of a projective space 9.2 Graphs 9.3 Strongly regular graphs 9.4 Smith normal form 10 Individual graph descriptions 10.1 The pentagon 10.2 The 3 × 3 grid 10.3 The Petersen graph 10.4 The Paley graph on 13 vertices 10.5 GQ(2,2) 10.6 The Shrikhande graph 10.7 The Clebsch graph 10.8 The Paley graph on 17 vertices 10.9 The Paulus-Rozenfel’d graphs 10.10 The Schläfli graph 10.11 𝑇 (8) and the Chang graphs 10.12 The strongly regular graphs on 29 vertices 10.13 The S8 graph on 35 vertices 10.14 The G2 (2) graph on 36 vertices 10.15 𝑁𝑂− 6(2) 10.16 The O5 (3) graphs on 40 vertices 10.17 The U4(2) graph on 45 vertices 10.18 The rank 3 conference graphs on 49 vertices 10.19 The Hoffman-Singleton graph 10.20 The Gewirtz graph 10.21 Sp6(2) 10.22 The G2 (2) graph on 63 vertices 10.23 The block graph of the smallest Ree unital 10.24 GQ(3,5) and the hexacode 10.25 𝑉𝑂− 6(2) 10.26 The halved folded 8-cube and 𝑉𝑂+ 6(2) 10.27 The M22 graph on 77 vertices 10.28 The Brouwer-Haemers graph 10.29 𝑉𝑁𝑂−4(3) and the Van Lint-Schrijver partial geometry 10.30 The rank 3 conference graphs on 81 vertices 10.31 The Higman-Sims graph 10.32 The Hall-Janko graph 10.33 The 105 flags of PG(2,4) 10.34 The O−6(3) graph on 112 vertices 10.35 NO+6(3) 10.36 The O8-(2) graph on 119 vertices 10.37 The L3(4).2^2 graph on 120 vertices 10.38 NO5-(4) 10.39 NO+8(2) 10.40 The S10 graph on 126 vertices 10.41 N06-(3) 10.42 The Goethals graph on 126 vertices 10.43 The O+8(2) graph on 135 vertices 10.44 NO-8(2) 10.45 The L3 (3) graph on 144 vertices 10.46 Three M12.2 graphs on 144 vertices 10.47 The O5 (5) graphs on 156 vertices 10.48 The U4 (3) graph on 162 vertices 10.50 A polarity of Higman's symmetric design 10.51 The M22 graph on 176 vertices 10.52 The nonisotropic points of U3(4) 10.53 A rank 16 representation of S7 10.54 The Cameron graph 10.55 The Berlekamp-Van Lint-Seidel graph 10.56 The M23 graph 10.57 28.S10 and 28.(A8 × S3) 10.58 28.L2 (17) 10.59 𝑉𝑂− 8(2) 10.60 𝑉𝑂+ 8(2) 10.61 The McLaughlin graph 10.62 The Mathon-Rosa graph 10.63 The lines of U5(2) 10.64 NO+5(5) and NO-5(5) 10.65 NO+5(5) and NO-5(5) 10.66 𝑁𝑂−⊥7(3) 10.67 NO7+(3) 10.68 The G2(4) graph on 416 vertices 10.69 The O-10(2) graph on 495 vertices 10.71 The U4(2) graphs on 540 vertices 10.72 The Aut(Sz(8)) graph on 560 vertices 10.73 The rank 3 graphs on 625 vertices 10.74 The U6(2) graph on 693 vertices 10.75 The Games graph 10.76 VO-6 (3) 10.77 The rank 3 graphs on 961 vertices 10.78 𝑁𝑂+ 8(3) 10.79 𝑁𝑂- 8(3) 10.80 The dodecad graph 10.81 The Conway graph on 1408 vertices 10.82 The Tits graph on 1600 vertices 10.83 The Suzuki graph 10.84 211.M24 on 2048 vertices with valency 276 10.85 211.M24 on 2048 vertices with valency 759 10.86 The rank 3 graphs on 2209 vertices 10.87 D5,5(2) 10.88 The Conway graph on 2300 vertices 10.89 The rank 3 graphs on 2401 vertices 10.90 The Fi22 graph 10.91 The Rudvalis graph 10.92 212 .HJ.S3 on 4096 vertices 10.93 The 38.21+6.O−6(2).2 graph on 6561 vertices 10.94 The Fi22 graph on 14080 vertices 10.95 The 56.4.HJ.2 graph on 15625 vertices 10.96 The Fi23 graph 10.97 The Fi23 graph on 137632 vertices 10.98 The E6(2) graph 10.99 The Fi24 graph 10.100 The Suz graph on 531441 vertices 11 Classification of rank 3 graphs 11.1 Primitive rank 3 permutation groups 11.2 Wreath product 11.3 Simple socle 11.4 The affine case 11.5 Rank 3 parameter index 11.6 Small rank 3 graphs 11.7 Small rank 4–10 strongly regular graphs 12 Parameter table References [22] [52] [81] [110] [139] [172] [204] [234] [266] [296] [326] [355] [383] [413] [442] [470] [501] [530] [562] [594] [626] [657] [689] [719] [750] Parameter Index Author Index Subject Index