Strongly Regular Graphs 1st Edition Andries E Brouwer H Van Maldeghem

Strongly Regular Graphs 1st Edition Andries E
Brouwer H Van Maldeghem download
https://ebookbell.com/product/strongly-regular-graphs-1st-
edition-andries-e-brouwer-h-van-maldeghem-42618672
Explore and download more ebooks at ebookbell.com

Here are some recommended products that we believe you will be
interested in. You can click the link to download.
Strongly Coupled Parabolic And Elliptic Systems Existence And
Regularity Of Strong And Weak Solutions Dung Le
https://ebookbell.com/product/strongly-coupled-parabolic-and-elliptic-
systems-existence-and-regularity-of-strong-and-weak-solutions-dung-
le-51010342
Strongly Correlated Systems Coherence And Entanglement Carmelo Jmp
https://ebookbell.com/product/strongly-correlated-systems-coherence-
and-entanglement-carmelo-jmp-2041712
Strongly Correlated Fermi Systems A New State Of Matter 1st Ed Miron
Amusia
https://ebookbell.com/product/strongly-correlated-fermi-systems-a-new-
state-of-matter-1st-ed-miron-amusia-22503924
Strongly Correlated Systems Theoretical Methods 1st Edition Robert O
Jones Auth
https://ebookbell.com/product/strongly-correlated-systems-theoretical-
methods-1st-edition-robert-o-jones-auth-2560774

Strongly Interacting Matter Under Rotation 1st Edition Francesco
Becattini
https://ebookbell.com/product/strongly-interacting-matter-under-
rotation-1st-edition-francesco-becattini-33607626
Strongly Coupled Parabolic And Elliptic Systems Existence And
Regularity Of Strong And Weak Solutions 1st Edition Dung Le
https://ebookbell.com/product/strongly-coupled-parabolic-and-elliptic-
systems-existence-and-regularity-of-strong-and-weak-solutions-1st-
edition-dung-le-34283170
Strongly Coupled Coulomb Systems Gabor Kalman J Martin Rommel Krastan
Blagoev
https://ebookbell.com/product/strongly-coupled-coulomb-systems-gabor-
kalman-j-martin-rommel-krastan-blagoev-4121560
Strongly Correlated Fermions And Bosons In Lowdimensional Disordered
Systems 1st Edition Ian Affleck Auth
https://ebookbell.com/product/strongly-correlated-fermions-and-bosons-
in-lowdimensional-disordered-systems-1st-edition-ian-affleck-
auth-4204230
Strongly Correlated Systems Numerical Methods 1st Edition P Prelovek
https://ebookbell.com/product/strongly-correlated-systems-numerical-
methods-1st-edition-p-prelovek-4245344

STRONGLY REGULAR GRAPHS
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.
Encyclopedia of Mathematics and Its Applications
This series is devoted to significant topics or themes that have wide application in
mathematics or mathematical science and for which a detailed development of the
abstract theory is less important than a thorough and concrete exploration of the
implications and applications.
Books in theEncyclopedia of Mathematics and Its Applicationscover their
subjects comprehensively. Less important results may be summarized as exercises at
the ends of chapters. For technicalities, readers can be referred to the bibliography,
which is expected to be comprehensive. As a result, volumes are encyclopedic
references or manageable guides to major subjects.

Encyclopedia of Mathematics and Its Applications
All the titles listed below can be obtained from good booksellers or from Cambridge
University Press. For a complete series listing visit
www.cambridge.org/mathematics
132 G. SchmidtRelational Mathematics
133 P. Kornerup and D. W. MatulaFinite Precision Number Systems and Arithmetic
134 Y. Crama and P. L. Hammer (eds.)Boolean Models and Methods in Mathematics, Computer Science,
and Engineering
135 V. Berthé and M. Rigo (eds.)Combinatorics, Automata and Number Theory
136 A. Kristály, V. D. R˘adulescu and C. VargaVariational Principles in Mathematical Physics, Geometry,
and Economics
137 J. Berstel and C. ReutenauerNoncommutative Rational Series with Applications
138 B. Courcelle and J. EngelfrietGraph Structure and Monadic Second-Order Logic
139 M. FiedlerMatrices and Graphs in Geometry
140 N. VakilReal Analysis through Modern Infinitesimals
141 R. B. ParisHadamard Expansions and Hyperasymptotic Evaluation
142 Y. Crama and P. L. HammerBoolean Functions
143 A. Arapostathis, V. S. Borkar and M. K. GhoshErgodic Control of Diffusion Processes
144 N. Caspard, B. Leclerc and B. MonjardetFinite Ordered Sets
145 D. Z. Arov and H. DymBitangential Direct and Inverse Problems for Systems of Integral and Differential
Equations
146 G. DassiosEllipsoidal Harmonics
147 L. W. Beineke and R. J. Wilson (eds.) with O. R. OellermannTopics in Structural Graph Theory
148 L. Berlyand, A. G. Kolpakov and A. NovikovIntroduction to the Network Approximation Method for
Materials Modeling
149 M. Baake and U. GrimmAperiodic Order I: A Mathematical Invitation
150 J. Borwein et al.Lattice Sums Then and Now
151 R. SchneiderConvex Bodies: The Brunn–Minkowski Theory (Second Edition)
152 G. Da Prato and J. ZabczykStochastic Equations in Infinite Dimensions (Second Edition)
153 D. Hofmann, G. J. Seal and W. Tholen (eds.)Monoidal Topology
154 M. Cabrera García and Á. Rodríguez PalaciosNon-Associative Normed Algebras I: The Vidav–Palmer
and Gelfand–Naimark Theorems
155 C. F. Dunkl and Y. XuOrthogonal Polynomials of Several Variables (Second Edition)
156 L. W. Beineke and R. J. Wilson (eds.) with B. ToftTopics in Chromatic Graph Theory
157 T. MoraSolving Polynomial Equation Systems III: Algebraic Solving
158 T. MoraSolving Polynomial Equation Systems IV: Buchberger Theory and Beyond
159 V. Berthé and M. Rigo (eds.)Combinatorics, Words and Symbolic Dynamics
160 B. RubinIntroduction to Radon Transforms: With Elements of Fractional Calculus and Harmonic
Analysis
161 M. Ghergu and S. D. TaliaferroIsolated Singularities in Partial Differential Inequalities
162 G. Molica Bisci, V. D. Radulescu and R. ServadeiVariational Methods for Nonlocal Fractional Problems
163 S. WagonThe Banach–Tarski Paradox (Second Edition)
164 K. BroughanEquivalents of the Riemann Hypothesis I: Arithmetic Equivalents
165 K. BroughanEquivalents of the Riemann Hypothesis II: Analytic Equivalents
166 M. Baake and U. Grimm (eds.)Aperiodic Order II: Crystallography and Almost Periodicity
167 M. Cabrera García and Á. Rodríguez PalaciosNon-Associative Normed Algebras II: Representation
Theory and the Zel’manov Approach
168 A. Yu. Khrennikov, S. V. Kozyrev and W. A. Zúñiga-GalindoUltrametric Pseudodifferential Equations
and Applications
169 S. R. FinchMathematical Constants II
170 J. KrajíˇcekProof Complexity
171 D. Bulacu, S. Caenepeel, F. Panaite and F. Van OystaeyenQuasi-Hopf Algebras
172 P. McMullenGeometric Regular Polytopes
173 M. Aguiar and S. MahajanBimonoids for Hyperplane Arrangements
174 M. Barski and J. ZabczykMathematics of the Bond Market: A Lévy Processes Approach
175 T. R. Bielecki, J. Jakubowski and M. Niew¸egłowskiStructured Dependence between Stochastic Processes
176 A. A. Borovkov, V. V. Ulyanov and Mikhail ZhitlukhinAsymptoticAnalysis of RandomWalks: Light-
Tailed Distributions
177 Y.-K. ChanFoundations of Constructive Probability Theory
178 L. W. Beineke, M. C. Golumbic and R. J. Wilson (eds.)Topics in Algorithmic Graph Theory
179 H.-L. Gau and P. Y. WuNumerical Ranges of Hilbert Space Operators
180 P. A. MartinTime-Domain Scattering
181 M. D. de la IglesiaOrthogonal Polynomials in the Spectral Analysis of Markov Processes

University Printing House, Cambridge CB2 8BS, United Kingdom
One Liberty Plaza, 20th Floor, New York, NY 10006, USA
477 Williamstown Road, Port Melbourne, VIC 3207, Australia
314–321, 3rd Floor, Plot 3, Splendor Forum, Jasola District Centre,
New Delhi 110025, India
103 Penang Road, #05–06/07, Visioncrest Commercial, Singapore 238467
Cambridge University Press is part of the University of Cambridge.
It furthers the University’s mission by disseminating knowledge in the pursuit of
education, learning, and research at the highest international levels of excellence.
www.cambridge.org
Information on this title:www.cambridge.org/9781316512036
DOI:
©Andries E. Brouwer and H. Van Maldeghem 2022
This publication is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without the written
permission of Cambridge University Press.
First published 2022
A catalogue record for this publication is available from the British Library.
ISBN 978-1-316-51203-6 Hardback
Cambridge University Press has no responsibility for the persistence or accuracy
of URLs for external or third-party internet websites referred to in this publication
and does not guarantee that any content on such websites is, or will remain,
accurate or appropriate.

Contents
Preface pagexv
1 1
1.1 Strongly regular graphs
1.1.1 Parameters
1.1.2 Complement
1.1.3 Imprimitivity
1.1.4 Spectrum
1.1.5 Rank
1.1.6 Local graphs
1.1.7 Johnson graphs
1.1.8 Hamming graphs
1.1.9 Paley graphs
1.1.10 Strongly regular graphs with smallest eigenvalue−25
1.1.11 Seidel switching
1.1.12 Regular two-graphs
1.1.13 Regular partitions and regular sets
1.1.14 Inequalities for subgraphs
1.1.15 Connectivity
1.1.16 Graphs induced on complementary subsets of the vertex
set of a graph
1.1.17 Enumeration
1.1.18 Proliﬁc constructions
1.2 Distance-regular graphs
1.2.1 Distance-transitive graphs
1.2.2 Johnson graphs
1.2.3 Hamming graphs
1.2.4 Grassmann graphs
1.2.5 Van Dam-Koolen graphs
1.2.6 Imprimitive distance-regular graphs
1.2.7 Taylor graphs
v

vi Contents
1.3 Association schemes and coherent conﬁgurations
1.3.1 Association schemes
1.3.2 The Bose-Mesner algebra
1.3.3 Linear programming bound and code-clique theorem
1.3.4 Krein parameters
1.3.5 Euclidean representation
1.3.6 Subschemes
1.3.7 Absolute bound and??????-bound
1.3.8 Coherent conﬁgurations
2 33
2.1 Polar spaces
2.2 Embedded polar spaces
2.2.1 Projective spaces
2.2.2 Deﬁnition of embedded polar spaces
2.2.3 Rank and radical
2.2.4 Maximal singular subspaces
2.2.5 Order of an embedded polar space
2.2.6 Parameters of the polar space strongly regular graphs
2.2.7 Ovoids, spreads,??????-systems,ℎ-ovoids, hemisystems
2.2.8 Intriguing or regular sets;??????-tight sets
2.2.9 Distance-regular graphs on singular subspaces
2.2.10 Generalized quadrangles
2.2.11 Strongly regular graphs on the lines
2.2.12 Distance-regular graphs on half of the maximal singular
subspaces
2.3 Classiﬁcation of ﬁnite embedded polar spaces
2.3.1 Residues
2.3.2 Reduction to rank
2.3.3 The ﬁnite rank space
2.3.4 The ﬁnite embedded generalized quadrangles
2.3.5 Summary
2.3.6 Group orders
2.4 Witt’s theorem
2.4.1 Reﬂexive forms
2.4.2 Reﬂexive forms and embedded polar spaces
2.4.3 Classiﬁcation of sesquilinear reﬂexive forms
2.4.4 Orthogonal direct sum decomposition
2.4.5 Witt’s theorem
2.5 Symplectic polar spaces
2.5.1 Symplectic forms, polar spaces, and graphs
2.5.2 Parameters
2.5.3 Automorphism groups

Contents vii
2.5.4 Maximal cliques
2.5.5 Ovoids
2.5.6 Maximal cocliques
2.5.7ℎ-Ovoids 61
2.5.8 Spreads
2.5.9 Tight sets
2.5.10 Local graph
2.6 Orthogonal polar spaces
2.6.1 Quadratic forms and orthogonal polar spaces
2.6.2 Finite orthogonal polar spaces and graphs
2.6.3 Parameters
2.6.4 Isomorphisms
2.6.5 Automorphism groups
2.6.6 Maximal cliques
2.6.7 Ovoids and maximal cocliques
2.6.8 Tight sets, spreads, andℎ-ovoids
2.7 Hermitian or unitary polar spaces
2.7.1 Hermitian forms
2.7.2 Hermitian or unitary polar spaces
2.7.3 Finite unitary polar spaces and graphs
2.7.4 Parameters
2.7.5 Isomorphisms
2.7.6 Automorphism groups
2.7.7 Maximal cliques
2.7.8 Maximal cocliques
2.7.9 Tight sets
2.7.10 Partial spreads
2.7.11 Hemisystems
3 84
3.1 Graphs on the nonsingular or nonisotropic points
3.1.1 Association scheme in even characteristic
3.1.2 Nonsingular points overF
2 85
3.1.3 Nonsingular points of one type overF
3in dimension2?????? 86
3.1.4 Nonsingular points of one type in dimension??????+186
3.1.5 Nonsingular points of one type overF
5in dimension2??????+18
3.1.6 Nonisotropic points for a Hermitian form
3.2 Graphs on half of the maximal singular subspaces
3.2.1 General observations
3.2.2 The rank
3.2.3 Rank
3.2.4 Disjoint t.i. planes in
O7(??????)andSp
6(??????) 97
3.3 Aﬃne polar graphs

viii Contents
3.3.1 Isotropic directions
3.3.2 Square directions
3.3.3 Aﬃne half spin graphs
3.4 Forms graphs
3.4.1 Bilinear forms graphs
3.4.2 Alternating forms graphs
3.4.3 Quadratic forms graphs
3.4.4 Hermitian forms graphs
3.4.5 Baer subspaces
3.4.6 A hyperoval at inﬁnity
3.5 Grassmann graphs
3.5.1 Lines in a projective space
3.6 The case??????=2 112
3.6.1 Local structure
3.6.2 Symmetric groups
4 114
4.1 Geometries
4.1.1 Generalized polygons
4.1.2 Diagrams
4.1.3 Simple properties
4.1.4 Shadow geometries
4.2 Coxeter systems
4.3 Coxeter geometries
4.4 Coxeter geometries of types
A??????,D??????andE6 122
4.5 Buildings
4.5.1 Generalities
4.5.2 Spherical buildings
4.5.3 Characterizations
4.5.4 Chain calculus
4.6 The Klein quadric and Klein correspondence
4.7 Triality
4.7.1 Split octonion algebras
4.7.2 Triality
4.8 A construction of
G2(??????) 132
4.9 The
E6,1(??????)graph
4.9.1 Parameters
4.9.2 Cliques, cocliques and regular sets
4.9.3 Construction of
E6,1 137
5 139
5.1 Deﬁnition
5.2 Fischer’s classiﬁcation
5.3 Hall triple systems

Contents ix
5.4 Cotriangular graphs
5.5 Locally grid graphs
5.6 Copolar spaces
5.6.1 Hall’s classiﬁcation
5.6.2 Lax embeddings of the symplectic copolar spaces
6 155
6.1 Codes
6.1.1 The Golay codes
6.1.2 The Golay codes — constructions
6.1.3 Properties and uniqueness
6.1.4 The Mathieu group
M24 159
6.1.5 More uniqueness results
6.2 Designs
6.2.1 The Witt designs
6.2.2 Substructures of??????(5,8,24) 164
6.2.3 Near polygons
6.2.4 The geometry of the projective plane of order
6.3 Lattices
6.3.1 The Leech lattice
6.3.2 The mod
6.3.3 The complex Leech lattice
7 174
7.1 Diﬀerence sets
7.1.1 Two-character projective sets
7.1.2 Projective two-weight codes
7.1.3 Delsarte duality
7.1.4 Parameters
7.1.5 Complements and imprimitivity
7.1.6 Divisibility
7.1.7 Field change
7.1.8 Unions and diﬀerences
7.1.9 Geometric examples
7.1.10 Small two-weight codes
7.1.11 Sporadic two-weight codes
7.2 Cyclic codes
7.2.1 Trace representation of an irreducible cyclic code
7.2.2 Wolfmann’s theorem
7.2.3 Irreducible cyclic two-weight codes
7.3 Cyclotomy
7.3.1 The Van Lint-Schrijver graphs
7.3.2 The Hill graph
7.3.3 The De Lange graphs

x Contents
7.3.4 Generalizations
7.3.5 Amorphic association schemes
7.3.6 Self-complementary graphs and Peisert graphs
7.4 One-dimensional aﬃne rank
7.4.1 Divisibility
7.4.2 Subgroups ofΓ??????(1,??????)with two orbits
7.4.3 One-dimensional aﬃne rank 191
7.4.4 Paley graphs 191
7.4.5 Power residue diﬀerence sets 193
7.5 Icosahedrals 194
7.5.1 Orbits of
A5on the projective line and plane 194
7.5.2 Orbits of
S4on the projective line 195
7.6 Bent functions 195
8 Combinatorial constructions 197
8.1 Regular Hadamard matrices with constant diagonal 197
8.1.1 Examples
8.1.2 Errata
8.2 Conference matrices and conference graphs
8.3 Symmetric designs
8.3.1 Generalities
8.3.2 The McFarland diﬀerence sets
8.4 Latin squares
8.4.1 Generalities
8.4.2 Latin square graphs
8.4.3 Transversaldesigns
8.5 Quasi-symmetric designs
8.5.1 The Calderbank-Cowen inequality
8.5.2 Neumaier’s inequality
8.5.3 No triangular graph
8.5.4 Examples
8.5.5 Classiﬁcation
8.5.6 Table
8.5.7 Parameter conditions from coding theory
8.5.8 Haemers cocliques
8.6 Partial geometries
8.6.1 Examples
8.6.2 Enumeration
8.6.3 Nonexistence
8.6.4 The claw bound
8.6.5 Claws and cliques
8.7 Semipartial geometries
8.7.1 Examples of partial quadrangles

Contents xi
8.7.2 Examples of semipartial geometries
8.8 Zara graphs
8.9 Terwilliger graphs
8.10 Regular two-graphs
8.10.1 Examples
8.10.2 Enumeration
8.10.3 Completely regular two-graphs
8.10.4 Covers and quotients
8.11 Pseudocyclic association schemes
8.12 Tensor products of skew schemes
8.13 Cospectral graphs
8.13.1 Godsil-McKay switching
8.13.2 Wang-Qiu-Hu switching
8.14 Equiangular sets of lines
8.15 Spherical designs
8.15.1 Tight spherical designs
8.15.2 Spherical designs from association schemes
8.15.3 Bounds on the number of??????
4’s 239
8.16 Higher regularity conditions 239
8.16.1 The??????-vertex condition 239
8.16.2??????-Isoregularity 240
8.17 Asymptotics 241
8.17.1 Graph isomorphism 241
8.17.2 Pseudo-randomness 241
8.18 Conditions in case??????=1or??????=2 243
8.19 Coloring 243
8.20 Graphs that are locally strongly regular 245
8.21 Dropping regularity 245
8.22 Directed strongly regular graphs 246
9 p-Ranks 249
9.1 Points and hyperplanes of a projective space 249
9.2 Graphs 249
9.3 Strongly regular graphs 250
9.4 Smith normal form 255
10 260
10.1 The pentagon 260
10.2 The×3 261
10.3 The Petersen graph 261
10.4 The Paley graph on 262
10.5 GQ(2,2) 263
10.6 The Shrikhande graph 264
10.7 The Clebsch graph 265

xii Contents
10.8 The Paley graph on
10.9 The Paulus-Rozenfel’d graphs
10.10 The Schläﬂi graph
10.11??????(8)and the Chang graphs
10.12 The strongly regular graphs on
10.13 The
S8graph on35vertices 275
10.14 The
G2(2)graph on
10.15????????????
6
(2) 279
10.16 The
O5(3)graphs on
10.17 The
U4(2)graph on
10.18 The rank
10.19 The Hoﬀman-Singleton graph
10.20 The Gewirtz graph
10.21
Sp
6(2) 291
10.22 The
G2(2)graph on
10.23 The block graph of the smallest Ree unital
10.24 GQ(3,5)
10.25????????????
−
6
(2) 296
10.26 The halved foldedcube and????????????
+
6
(2) 296
10.27 The
M22graph on77vertices 297
10.28 The Brouwer-Haemers graph 299
10.29??????????????????
−
4
(3)and the Van Lint-Schrijver partial geometry
10.30 The rank
10.31 The Higman-Sims graph
10.32 The Hall-Janko graph
10.33 The 2,4) 309
10.34 The
O
−
6
(3)graph on
10.35????????????
+
6
(3) 313
10.36 The
O
8
(2)graph on
10.37 The
L3(4).2
2
graph on120vertices 315
10.38????????????
5
(4) 316
10.39
????????????
+
8
(2) 317
10.40 The
S10graph on126vertices 321
10.41????????????
6
(3) 322
10.42 The Goethals graph on
10.43 The
O
+
8
(2)graph on
10.44????????????
8
(2) 325
10.45 The
L3(3)graph on
10.46 Three
M12.2 graphs on
10.47 The
O5(5)graphs on
10.48 The
U4(3)graph on
10.49 The nonisotropic points of
U5(2) 330
10.50 A polarity of Higman’s symmetric design

Contents xiii
10.51 The
M22graph on176vertices 331
10.52 The nonisotropic points of
U3(4) 331
10.53 A rank
S7 332
10.54 The Cameron graph
10.55 The Berlekamp-Van Lint-Seidel graph
10.56 The
M23graph 334
10.57
8
.S10and2
8
.(A8×S3) 335
10.58
8
.L2(17) 335
10.59????????????
8
(2) 336
10.60
????????????
+
8
(2) 336
10.61 The McLaughlin graph
10.62 The Mathon-Rosa graph
10.63 The lines of
U5(2) 341
10.64????????????
⊥
5
(5)and????????????
5
(5) 342
10.65????????????
+⊥
5
(5)and????????????
+
5
(5) 343
10.66????????????
⊥
7
(3) 344
10.67????????????
+⊥
7
(3) 345
10.68 The
G2(4)graph on
10.69 The
O
−
10
(2)graph on 495 vertices
10.70 The rank
10.71 The
U4(2)graphs on 540 vertices
10.72 The Aut(
Sz(8))graph on 560 vertices
10.73 The rank
10.74 The
U6(2)graph on 693 vertices
10.75 The Games graph
10.76????????????
−
6
(3) 355
10.77 The rank
10.78????????????
+
8
(3) 356
10.79????????????
8
(3) 357
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
11
.M24on 2048 vertices with valency276 362
10.852
11
.M24on 2048 vertices with valency 759 363
10.86 The rank 364
10.87
D5,5(2) 365
10.88 The Conway graph on 2300 vertices
10.89 The rank
10.90 The
Fi22graph 371
10.91 The Rudvalis graph 372
10.92
12
.HJ.S3on 4096 vertices 374
10.93 The 3
8
.2
1+6
.O
−
6
(2).2 graph on 6561 vertices

xiv Contents
10.94 The
Fi22graph on 14080 vertices 376
10.95 The 5
6
.4.HJ.2 graph on 15625 vertices
10.96 The
Fi23graph 377
10.97 The
Fi23graph on 137632 vertices 378
10.98 The
E6(2)graph
10.99 The
Fi24graph 380
10.100 The
Suzgraph on 531441 vertices 381
11 382
11.1 Primitive rank
11.2 Wreath product
11.3 Simple socle
11.3.1 Alternating socle
11.3.2 Classical simple socle
11.3.3 Exceptional simple socle
11.3.4 Sporadic simple socle
11.3.5 Triangular graphs
11.4 The aﬃne case
11.5 Rank
11.6 Small rank
11.7 Small rank
12 399
References 425
Parameter index 451
Author index 453
Subject index 457

Preface
The present volume is a monograph on the topic of Strongly Regular Graphs. So far,
no book-length treatment of this subject area has been available.
The topic of strongly regular graphs is an area where statistics, Euclidean geometry,
group theory, ﬁnite geometry, and extremal combinatorics meet. The subject concerns
beautifully regular structures, studied mostly using spectral methods, group theory,
geometry and sometimes lattice theory.
Roughly around 1970–1980, Algebraic Combinatorics came up as a separate
branch in mathematics. It turned out that the same structures were studied in statistics
(for the design of experiments), in Euclidean geometry (e.g. in the construction
of systems of equiangular lines), in group theory (where several sporadic groups
arise as automorphism groups of a strongly regular graph), in coding theory (where
association schemes provide a tool for obtaining bounds on the size of codes, and
beautiful structures give rise to good and easy-to-decode codes), in the theory of
special functions (where the spectral data of association schemes give rise to series of
orthogonal polynomials), in ﬁnite geometry (where collinearity graphs of polar spaces
are strongly regular), in extremal combinatorics, in cryptography, and elsewhere.
More recently such very regular structures ﬁnd some application in the theory of
quantum computation (e.g. for mutually unbiased bases (MUBs) and symmetric,
informationally complete, positive operator-valued measures (SICPOVMs)).
Axiomatizing the combinatorial information in the action of a ﬁnite permutation
group??????on a set??????yields a hierarchy of combinatorial structures. A general group
gives the structure of coherent conﬁguration. For a transitive group one ﬁnds an
association scheme. If the representation is multiplicity-free, the pair(??????, ??????), where??????
is the point stabilizer in??????, is called a Gelfand pair. The corresponding combinatorial
object is a commutative association scheme. If??????is generously transitive, one ﬁnds
a symmetric association scheme. The simplest nontrivial case is that of a strongly
regular graph, the combinatorial analog of a rank 3 group, where??????has three orbits
on??????×??????.
xv

xvi Preface
Delsarte’s 1973 thesis1deﬁned the concept of (commutative) association scheme
and showed the use of the linear programming bound. Bannai & Ito2introduced the
term ‘algebraic combinatorics’, described as ‘character-theoretical study of combi-
natorial objects’, or ‘group theory without groups’. Brouwer, Cohen & Neumaier3
published a monograph on distance-regular graphs (that is,??????- and??????-polynomial
association schemes) of diameter at least 3 (where the strongly regular graphs are
precisely the distance-regular graphs of diameter 2). They wrote ‘Another book would
be required to cover the present knowledge about strongly regular graphs (no such
book is available at present)’. The present monograph ﬁlls this gap.
Various teams of authors, starting around 1980 with Van Lint and the present ﬁrst
author, contemplated writing such a book, but for various reasons such a project was
never completed. Many years later J. I. Hall, at a 2011 meeting in Oisterwijk, again
commented on the lack of a good source of information about strongly regular graphs
more recent than Hubaut’s 1975 survey,4and the project was rekindled.
This book was started with the aim to give the classiﬁcation of rank 3 graphs and to
describe these graphs, possibly as members of larger families, and give information
such as parameters, group, cliques, cocliques, local structure, and characterization.
Later, the project was widened to include the theory of general strongly regular
graphs.
The bulk of the material is more or less well known. Many details are new. In
particular, we give information about regular subsets that is often new. Our approach
to the (aﬃne) half spin graphs of rank 5 hyperbolic polar spaces is original and based
on the idea of ‘thickening’ the Clebsch graph. We felt free to omit proofs that are
rather technical, or that do not ﬁt naturally into the line of development of the book.
Chapter 1 contains the fundaments. Chapters 2 and 3 ﬁnd the ﬁnite polar geometries
in a uniform way and describe the related graphs and substructures. Chapter 4 is a
brief introduction to buildings,5and provides an explicit and elementary construction
of the ﬁnite buildings of types
E6andG2. Chapter 5 is a very short introduction to the
geometry related to the Fischer groups.6For later use, lax embeddings of symplectic
copolar spaces are studied. Chapter 6 gives the main facts on the Golay codes and
Witt designs, and contains a very short introduction to the Leech lattice.7Chapter 7 is
about cyclotomy and diﬀerence sets, and the relation to two-weight codes. Chapter 8
contains combinatorial material that is partly new, with, for example, discussions of
orthogonal arrays, quasi-symmetric designs, partial geometries, regular two-graphs,
1 Ph. Delsarte,An algebraic approach to the association schemes of coding theory, Philips Res. Rep.
Suppl.10(1973).
2 E. Bannai & T. Ito,Algebraic Combinatorics I, Benjamin, 1984.
3 A. E. Brouwer, A. M. Cohen & A. Neumaier,Distance-Regular Graphs, Springer, 1989.
4 X. L. Hubaut,Strongly regular graphs, Discr. Math.13(1975) 357–381.
5 For a monograph, see P. Abramenko & K. S. Brown,Buildings, Theory and Applications, Springer,
2008.
6 For a monograph on the group theoretical side, see M. Aschbacher,3-Transposition Groups, Cambridge
University Press, 1997.
7 For a monograph, see J. H. Conway & N. J. A. Sloane,Sphere Packings, Lattices and Groups, Springer,
1988.

Preface xvii
spherical designs, randomness properties and much more. Chapter 9 discusses the
??????-rank of the adjacency matrix, in some cases a useful invariant that may distinguish
graphs with the same parameters. The long Chapter 10 consists of a hundred sections
discussing (more than) a hundred individual graphs in some more detail. In Chapter 11
we give the classiﬁcation of rank 3 groups, and identify in each case the corresponding
strongly regular graph. Everywhere there are extensive tables. Chapter 12 is just a
table, listing all feasible parameter sets of strongly regular graphs with at most
512 vertices together with some information about existence and other details, with
references to other parts of the book.
We would like to especially thank Jon Hall, Ferdinand Ihringer, Dima Pasechnik,
Alexander Gavrilyuk, and the anonymous referees for detailed comments on earlier
drafts. We are also grateful to Maarten De Boeck, Ludmila Tsiovkina, Paulien
Jansen, Jeroen Schillewaert, Anneleen De Schepper, Sam Mattheus, and Jan De
Beule for reading, and commenting on, draft versions of speciﬁc chapters. Finally, we
acknowledge with thanks the help of the librarian, Samuel Perez, for locating several
diﬃcult-to-ﬁnd papers.
Amsterdam and Ghent, March 2021.

1
Graphs
This chapter collects some basic material on strongly regular graphs and gives some
information about more general objects (distance-regular graphs and association
schemes) that will be needed later.
1.1 Strongly regular graphs
Agraphis a set??????ofverticesprovided with a symmetric relation∼on??????called
adjacency, such that no??????∈??????is adjacent to itself. If the graph is denoted byΓ, then
its vertex set??????is also denoted by
VΓ. A pair of adjacent vertices is called anedge.
If????????????is an edge, then??????is called aneighborof??????.
LetΓbe a ﬁnite graph. Theadjacency matrix??????ofΓis the square matrix indexed by
the vertices ofΓsuch that??????
????????????=1 when??????∼??????, and?????? ????????????=0 otherwise. Thespectrum
ofΓis by deﬁnition the spectrum (eigenvalues and multiplicities) of??????, considered
as a real matrix. A nonzero (column) vector??????, indexed by
VΓ, is an eigenvector of??????
with eigenvalue??????when????????????=????????????, i.e., when
ﬀ
??????∼??????????????????=??????????????????for all??????.
A graphΓisregularofdegree(orvalency)??????, for some integer??????, when every
vertex has precisely??????neighbors.
LetΓbe ﬁnite with adjacency matrix??????. The all-1 vector1(of appropriate length)
is an eigenvector (with eigenvalue??????) if and only ifΓis regular (of valency??????). IfΓ
is regular of valency??????, then the multiplicity of the eigenvalue??????is the number of
connected components ofΓ. An eigenvalue??????of a regular graph is calledrestrictedif
it has an eigenvector orthogonal to1.
A ﬁnite regular graph without restricted eigenvalues has at most one vertex. A ﬁnite
regular graph with only one restricted eigenvalue is complete or edgeless. Astrongly
regular graphis a ﬁnite regular graph with precisely two restricted eigenvalues.
History
The term ‘strongly regular graph’ was ﬁrst used byBose[92]. An equivalent concept
was studied byBose&Shimamoto[97].
1

2 Graphs
1.1.1 Parameters
LetΓbe a strongly regular graph, regular of valency??????, with adjacency matrix??????and
restricted eigenvalues??????, ??????, where??????>??????. Let??????be the all-1 matrix of suitable size, so
that????????????=????????????=????????????.Wehave(??????−????????????)(??????−????????????)=????????????for some constant??????, so that
??????
2
=????????????+????????????+??????(??????−??????−??????)for certain constants??????,??????, ??????. Apparently??????=??????and
??????=??????+??????+??????and??????−??????=−????????????.
This can be stated in a combinatorial way: For??????, ??????∈
VΓ, the number of common
neighbors of??????, ??????is??????when??????=??????, and??????when??????∼??????, and??????when??????ﬃ??????. One says
that the strongly regular graphΓhasparameters(??????,??????,??????,??????), where??????=|
VΓ|is the
number of vertices. Conversely, if in a ﬁnite graphΓ, not complete and not edgeless,
the number of common neighbors of two vertices is??????,??????, ??????depending on whether
they are equal, adjacent or nonadjacent, thenΓis strongly regular, and the restricted
eigenvalues??????, ??????are found as the roots of??????
2
+(????????????)??????+(????????????)=0.
The combinatorial deﬁnition of??????,??????, ??????shows that these are nonnegative integers,
and 0≤??????≤??????−1 and 0≤??????≤??????. By Perron-Frobenius’ theorem,??????≥??????. Since
tr??????=0 it follows that??????<0 and??????≥0.
If??????≠0, then the parameters are related by??????=1+??????+??????(??????−1−??????)/??????.
From(??????−????????????)(??????−????????????)=????????????one gets the identity(??????−??????)(??????−??????)=????????????.
History
The parameters??????, ??????, ??????, ??????, ??????, ??????, ??????, ?????? , ??????(with??????=??????and??????=??????−??????−1) were perhaps ﬁrst
used in [419]. Earlier,Bose[92] used??????,??????
1,??????2,??????
1
11
,??????
2
11
.
1.1.2 Complement
IfΓis a strongly regular graph with parameters(??????,??????,??????,??????)and restricted eigenvalues
??????, ??????, then the complementary graph
Γ(with the same vertex set asΓ, and where distinct
vertices are adjacent if and only if they are nonadjacent inΓ) is also strongly regular,
with parameters(??????,??????,??????,¯??????)and restricted eigenvalues??????,??????, where??????=??????−??????−1,
??????=??????−2??????+??????−2,??????=??????−2??????+??????,??????=−1−??????,??????=−1−??????, as is immediately clear
from the deﬁnitions and the fact that
Γhas adjacency matrix??????=??????−??????−??????.
1.1.3 Imprimitivity
A strongly regular graphΓis calledimprimitivewhenΓor
Γis a nontrivial equivalence
relation, equivalently, when??????=??????−1or??????=??????, equivalently, when??????=0or??????=2??????−??????,
equivalently, when??????=−1or??????=0.
In the former caseΓis a disjoint union????????????
??????of??????complete graphs of size??????(and
??????=????????????,??????=??????−1,??????=??????−2,??????=0,??????=??????−1,??????=−1), where??????>1.
In the latter caseΓis a complete multipartite graph??????
??????×??????(and??????=????????????,??????=
(??????−1)??????,??????=(??????−2)??????,??????=(??????−1)??????,??????=0,??????=−??????), again with??????>1.

1.1 Strongly regular graphs 3
(The graphs??????
??????and??????1×??????=
????????????have only one restricted eigenvalue, namely−1
and 0 respectively, and hence are not strongly regular.)
For a primitive strongly regular graph it follows that 0≤??????<??????−1 and 0<??????<??????
and??????>0 and??????<−1. A primitive strongly regular graph is connected, and hence
??????>??????.
The graph????????????
2is sometimes called aladder graph. Its complement
????????????2=????????????×2a
cocktail party graph.
1.1.4 Spectrum
LetΓbe strongly regular, with spectrum??????,??????(with multiplicity??????) and??????(with
multiplicity??????). Then??????,??????can be solved from 1+??????+??????=??????and??????+????????????+????????????=tr??????=0.
The fact that??????,??????must be integers is a strong restriction on possible parameter sets.
If??????≠??????, then one can also solve??????, ??????from??????+??????=??????−??????and????????????+????????????=−??????,
and it follows that??????, ??????are rational. Since they are also algebraic integers, they are
integral in this case. On the other hand, if??????=??????, then??????=??????=(??????−1)/2. Now
??????=(??????−??????)??????=(??????−??????)(??????−1)/2, and since 0<??????<??????−1 it follows that??????=(??????−1)/2
and??????=??????+1.Now??????=1+??????+??????(??????−1−??????)/??????yields??????=??????−1−??????=??????/2, so
that(??????,??????,??????,??????)=(4??????+1,2??????,??????−1,??????)for a suitable integer??????, and??????, ??????=(−1±
√
??????)/2.
This is known as the ‘half case’. It occurs, e.g., for the Paley graphs (see §1.1.9). For
further details, see §8.2.
Summary: if we are not in the half case, then the spectrum is integral.
Explicit expressions for??????,??????are??????=
(??????+1)??????(??????−??????)
??????(??????−??????)
and??????=
(??????+1)??????(??????−??????)
??????(??????−??????)
.
The identity
????????????(??????1??????)
????????????
=(??????−??????)
2
(known as theFrame quotient, cf. [123] §2.2A,
2.7A) follows.
In particular,??????=(??????−??????)
2
if and only if{??????,??????}={??????,??????−??????−1}.
1.1.5 Rank 3 permutation groups
Apermutation groupis a group??????together with an action of??????on some set??????, that
is, together with a map??????×??????→??????written(??????, ??????) ↦→????????????, such that 1??????=??????and
??????(ℎ??????)=(??????ℎ)??????for all??????, ℎ∈??????and??????∈??????, where 1 is the identity element of??????.
Anorbitof??????on??????is a set of the form????????????for some??????∈??????. The??????-orbits form a
partition of??????. The action (or the group) is calledtransitivewhen this partition has a
single element only, that is, when????????????=??????for all??????∈??????. A set??????ispreservedby??????
when????????????=??????for all??????∈??????.
The action of??????on??????induces an action of??????on??????×??????via??????(??????,)=(????????????, ????????????).If
??????is transitive, then it is said to beof (permutation) rank??????when it has precisely??????
orbits on??????×??????.
The action (or the group) is calledprimitivewhen there is no nontrivial equivalence
relation??????⊆??????×??????that is preserved by??????. The trivial equivalence relations are the
full set??????×??????and the diagonal??????={(??????, ??????)|??????∈??????}.

4 Graphs
Suppose??????is a rank 3 permutation group on the set??????. Then??????has three orbits
??????, ??????, ??????on??????×??????, where??????is the diagonal. Now either??????and??????are inverse relations:
??????={(??????, ??????)|(??????, ??????)∈??????},or??????and??????are symmetric. In the former case(??????, ??????)is
a complete directed graph, a tournament (and(??????, ??????)is the opposite tournament). In
the latter case(??????, ??????)and(??????, ??????)are a complementary pair of graphs. When??????is
ﬁnite, they are a complementary pair of strongly regular graphs: the group??????acts as
a group of automorphisms on the graphs(??????, ??????)and(??????, ??????), and since??????and??????are
single orbits,??????is transitive on ordered pairs of adjacent (nonadjacent) vertices, and
the number of common neighbors of two vertices does not depend on the vertices
chosen, but only on whether they are equal, adjacent or nonadjacent.
History
The study of rank 3 permutation groups was initiated byHigman[420].
1.1.6 Local graphs
IfΓis a graph, and??????a vertex ofΓ, then thelocal graphofΓat??????is the graph induced
byΓon the set of neighbors of??????inΓ.
A graphΓis calledlocallyΔ(orlocally X) whereΔis a graph and X a graph
property, when all local graphs are isomorphic toΔ(or have property X).
For example, the icosahedron is the unique connected locally pentagon graph.
Hall[391] determined all locallyΔgraphs on at most 11 vertices, for all possibleΔ,
and determined for each graphΔon at most 6 vertices whether there exists a locally
Δgraph.
IfΓis a connected graph, and??????a vertex ofΓ, then the??????thsubconstituentofΓ(at
??????) is the graph induced on the set of vertices at (graph) distance??????from??????.IfΓis a
strongly regular graph, and??????a vertex ofΓ, then the second subconstituent ofΓ(at??????)
is the graph induced on the set of vertices other than??????and nonadjacent to??????.
1.1.7 Johnson graphs
LetΩbe a set, and??????≥0 an integer. TheJohnson graph??????(Ω,??????)is the graph that has
as vertex set the set
ﬀ
Ω
??????
ć
of??????-subsets ofΩ, where two??????-sets??????, ??????are adjacent when
|??????∩??????|=??????−1. Suppose|Ω|≥2??????. Then??????(Ω,??????)has diameter??????, and the symmetric
group
Sym(Ω)acts as a group of automorphisms that is transitive of rank??????+1. If
|Ω|=??????one writes??????(??????, ??????)instead of??????(Ω,??????).
The full group of automorphisms of??????(Ω,??????)is
Sym(Ω)when|Ω|>2??????>0, but
Sym(Ω)×2 when|Ω|=2??????>0, and 1 when??????=0.
In particular, the graph??????(??????,2)(also called thetriangular graph??????(??????)), where
??????≥4, is strongly regular. It has parameters??????=??????(??????−1)/2,??????=2(??????−2),
??????=??????−2,??????=4 and eigenvalues??????,??????=??????−4,??????=−2 with multiplicities 1,
??????=??????−1,??????=??????(??????−3)/2. The graph??????(??????)is the line graph of the complete graph
??????
??????on??????vertices. The complement
??????(5)of??????(5)is thePetersen graph(§10.3).

1.1 Strongly regular graphs 5
These graphs are characterized by their parameters, except when??????=8. There
are four graphs with the parameters(??????,??????,??????,??????)=(28,12,6,4)of??????(8), namely??????(8)
itself and three graphs known as theChang graphs([191, 192]), cf. §10.11.
1.1.8 Hamming graphs
LetΩbe a set, and??????≥0 an integer. TheHamming graph??????(??????,Ω)is the graph
that has as vertex set the setΩ
??????
of??????-tuples of elements ofΩ, where two??????-tuples
(??????
1,...,????????????),(??????1,...,????????????)are adjacent when they haveHamming distance1, i.e.,
when??????
??????≠????????????for a unique??????. Suppose|Ω|≥2. Then??????(??????,Ω)has diameter??????, and its
full group of automorphisms is the wreath product
Sym(Ω)wr Sym(??????). This group
is transitive of rank??????+1. If|Ω|=??????one writes??????(??????, ??????)instead of??????(??????,Ω).
In particular, the graph??????(2,??????)(also called thelattice graph??????
2(??????)or the??????×??????
grid), where??????≥2, is strongly regular. It has parameters??????=??????
2
,??????=2(??????−1),
??????=??????−2,??????=2 and eigenvalues??????,??????=??????−2,??????=−2 with multiplicities 1,
??????=2(??????−1),??????=(??????−1)
2
. The graph??????(2,??????)is the line graph of the complete
bipartite graph??????
??????,??????. The graph?????? 2(3)is isomorphic to its complement. It is the Paley
graph (see §1.1.9) of order 9.
These graphs are characterized by their parameters, except when??????=4. There
are two graphs with the parameters(??????,??????,??????,??????)=(16,6,2,2), namely??????
2(4)and the
Shrikhande graph([649]), cf. §10.6.
The graph??????(??????, ??????)is locally????????????
??????1, the disjoint union of??????complete graphs of
size??????−1. The Shrikhande graph is locally a hexagon.
1.1.9 Paley graphs
Let??????=4??????+1 be a prime power. ThePaley graphPaley(??????)is the graph with the ﬁnite
ﬁeldF
??????as vertex set, where two vertices are adjacent when they diﬀer by a nonzero
square. It is strongly regular with parameters(4??????+1,2??????,??????−1,??????). (The restriction??????≡1
(mod 4) is to ensure that−1 is a square, so that the resulting graphs are undirected.)
Let??????=??????
??????
, where??????is prime. The full group of automorphisms consists of the
maps??????↦→????????????
??????
+??????where??????, ??????∈F ??????,??????a nonzero square, and??????=??????
??????
with 0≤??????<??????
([186]). It has order????????????(??????−1)/2.
Paley(5) is the pentagon. Paley(9) is the 3×3 grid. Paley(13) is a graph that is
locally a hexagon. For a more detailed discussion, see §7.4.4.
1.1.10 Strongly regular graphs with smallest eigenvalue−2
A disjoint union of cliques has smallest eigenvalue??????=−1. The pentagon has smallest
eigenvalue(−1−
√
5)/2. All other strongly regular graphs satisfy??????≤−2.Seidel
[642] determined the strongly regular graphs with smallest eigenvalue??????=−2. There
are three inﬁnite families and seven more graphs:

6 Graphs
(i) the complete??????-partite graph??????
??????×2, with parameters(??????,??????,??????,??????)=(2??????,2??????−2,2??????−
4,2??????−2),??????≥2,
(ii) the lattice graph??????
2(??????), that is, the Hamming graph??????(2,??????), that is, the??????×??????
grid, with parameters(??????,??????,??????,??????)=(??????
2
,2(??????−1),??????−2,2),??????≥3,
(iii) the triangular graph??????(??????)with parameters(??????,??????,??????,??????)=(
ﬀ
??????
2
ć
,2(??????−2),??????−2,4),
??????≥5,
(iv) the Shrikhande graph (cf. §10.6), with parameters(??????,??????,??????,??????)=(16,6,2,2),
(v) the three Chang graphs (cf. §10.11), with parameters(??????,??????,??????,??????)=(28,12,6,4),
(vi) the Petersen graph (cf. §10.3), with parameters(??????,??????,??????,??????)=(10,3,0,1),
(vii) the Clebsch graph (cf. §10.7), with parameters(??????,??????,??????,??????)=(16,10,6,6),
(viii) the Schläﬂi graph (cf. §10.10), with parameters(??????,??????,??????,??????)=(27,16,10,8).
More generally, the strongly regular graphs with ﬁxed smallest eigenvalue are
(i) complete multipartite graphs, (ii) Latin square graphs, (iii) block graphs of Steiner
systems, (iv) ﬁnitely many further graphs, see Theorem 8.6.4.
We include a proof of Seidel’s classiﬁcation. (For diﬀerent proofs, see [419] and
[123], Theorem 3.12.4. See also below.)
Theorem 1.1.1A strongly regular graph with smallest eigenvalue−2is one of the
examplesin (i)–(viii) above.
Proof.We shall assume the classiﬁcation of the graphs with the parameters of the
examples. The proof here derives the possible parameters.
LetΓbe a strongly regular graph with parameters??????,??????,??????,??????and spectrum??????
1
??????
??????
??????
??????
,
where??????=−2. Then??????=??????+??????−2 and??????=??????+2??????(by §1.1.1), so that??????=2??????−??????+4.
If??????=2, thenΓhas the parameters of??????
2(??????)(for??????=??????+2), and hence is?????? 2(??????),
or (if??????=4) the Shrikhande graph (cases (ii) and (iv)). If??????=4, thenΓhas the
parameters of??????(??????)(for??????=??????+4), and hence is??????(??????), or (if??????=8) a Chang graph
(cases (iii) and (v)). Assume??????≠2,4.
From 1+??????+??????=??????and??????+????????????−2??????=0 and????????????=(??????−??????)(??????+2),weﬁnd
??????=
2????????????−2
??????+2
=
(??????+2??????)(??????+2??????+2)
??????(??????+2)
.
Let an??????-clawbe an induced??????
1,??????subgraph. Let aquadranglebe an induced?????? 4
subgraph. Let??????∼??????, ??????with??????ﬃ??????.If{??????, ??????, ??????}is contained in??????3-claws and in??????
quadrangles, then??????=2+2??????−(??????−1−??????)+??????so that??????+??????=1.
First consider the case where the graph contains a 3-claw. Let??????∼??????, ??????, ??????with
mutually nonadjacent??????, ??????, ??????. We shall show that??????=2??????+4 andΓis one of the
examples (iv)–(vi).
For a list of vertices??????, let??????(??????)(‘near’) be the set of vertices adjacent to each??????in
??????, and??????(??????)(‘far’) the set of vertices not in??????and nonadjacent to each??????in??????. Since
the??????−??????−1=??????+1 vertices in??????(??????)∩??????(??????)are in{??????, ??????}∪??????(??????, ??????)\ ??????},wehave??????≤??????.
Since the??????−??????vertices in(??????(??????)∩??????(??????)) ∪ {??????}are among the
??????=??????−2??????+??????−2
vertices of??????(??????, ??????),wehave??????≥5??????+??????+4. Since????????????=(??????−??????)(??????+2)we have
??????=3??????+??????+2+
2??????(??????+1)
??????
so that??????≤??????. It follows that??????=??????,??????=2??????−2,??????=3??????,

1.1 Strongly regular graphs 7
??????=6??????+4=2??????+4,??????=9−
12
??????+2
so that??????∈{1,2,4,10}.For??????=1,2,4 we are in case
(vi), (iv), (v), respectively. The case(??????,??????,??????,??????)=(64,30,18,10)has??????=8, which
violates the absolute bound??????≤
1
2
??????(??????+3)(Proposition 1.3.14 below).
Now assume thatΓdoes not contain 3-claws. Since??????+??????=1, each 2-claw is in a
unique quadrangle. It follows that??????is even, say??????=2??????, and if??????ﬀ??????, then??????(??????, ??????)
induces a??????
??????×2. If moreover??????∼??????,??????ﬀ??????, then??????is adjacent to precisely??????vertices
of??????(??????, ??????). (If??????, ??????∈??????(??????, ??????)with??????ﬀ??????, then??????cannot be nonadjacent to both??????
and??????, since(??????;??????, ??????, ??????)would be a 3-claw, and??????cannot be adjacent to both??????and??????,
since we already see the??????common neighbors of??????and??????in??????(??????, ??????)∪{??????, ??????}.)
Let??????be a vertex, and consider the graph induced on??????(??????). It is strongly regular or
complete or edgeless with parameters(??????
0,??????0,??????0,??????0)=(??????−??????−1,??????−??????, ??????−??????, ??????).
If it is edgeless, then??????=??????, so thatΓis imprimitive, and we are in case (i). If it is
complete, then??????−??????−1=??????−??????+1 so that(??????+2??????)(??????+1)=??????(2??????+1), hence
??????=2(??????+1)and??????=8−
12
??????+2
, so that??????∈{1,2,4,10}.For??????=1wehave??????(5)(in
case (iii)), for??????=2 the Clebsch graph (case (vii)), and??????=4(??????=28,??????=6) and
??????=10 (??????=64,??????=7) both violate the absolute bound.
So we may assume that??????(??????)induces a strongly regular graphΔ. Since??????
0=
2??????
0−??????0+4, alsoΔhas smallest eigenvalue−2, and the other restricted eigenvalue
is??????
0=??????−??????with multiplicity?????? 0=
2??????(??????+1)
??????(??????−??????+2)
. By induction we already knowΔ(and
it does not contain 3-claws) so either??????∈{6,8},orΔis??????
??????×2.For??????=6 there are no
feasible parameters. For??????=8 we ﬁnd the Schläﬂi graph (case (viii)). IfΔis??????
??????×2,
then(??????,??????,??????,??????)=(6??????−3,4??????−4,3??????−5,2??????−2),??????=??????−1,??????=8−
12
??????+2
, so that
??????∈{1,2,4,10}.For??????=1wehave??????
2(3)(in case (ii)), for??????=2wehave??????(6)
(in case (iii)), for??????=4 the Schläﬂi graph (case (viii)), and??????=10 (??????=63,??????=7)
violates the absolute bound. ﬀ
Root systems
In fact it is possible to ﬁnd all graphs with smallest eigenvalue≥−2. By the beautiful
theorem ofCameron,Goethals,Seidel&Shult[179] (see also [123], §3.12 and
[132], §8.4) such a graph is either a generalized line graph or is one in a ﬁnite (but
large) collection.
(Sketch of the proof: Consider??????+2??????. It is positive semideﬁnite, so one can write
??????+2??????=??????
??????
??????. Now the columns of??????are vectors of squared length 2 with integral
inner products, and this set of vectors can be completed to a root system. By the
classiﬁcation of root systems one gets one of
A??????,D??????,E6,E7orE8. In the ﬁrst two
cases the graph was a generalized line graph. In the latter three cases the graph is
ﬁnite: at most 36 vertices, each vertex of degree at most 28. If the graph was regular,
it has at most 28 vertices, and each vertex has degree at most 16. For details, see
[123], Theorem 3.12.2, or [132], Chapter 8.)
There is a lot of literature describing manageable parts of this large collection, and
related problems. A book-length treatment isCvetkovićet al. [249].

8 Graphs
1.1.11 Seidel switching
Instead of the ordinary adjacency matrix??????, Seidel considered theSeidel matrix??????of
a graph, with zero diagonal, where??????
????????????=−1if??????∼??????, and?????? ????????????=1 otherwise. These
matrices are related by??????=??????−??????−2??????.
LetΓbe a graph with vertex set??????. Let??????⊆??????. The graphΓ
??????
obtained byswitching
Γwith respect to??????is the graph with vertex set??????, where two vertices that are both
inside or both outside??????are adjacent inΓ
??????
when they are adjacent inΓ, while a vertex
inside??????is adjacent inΓ
??????
to a vertex outside??????when they are not adjacent inΓ.If
Γhas Seidel matrix??????, thenΓ
??????
has Seidel matrix??????
??????
where??????
??????
is obtained from??????by
multiplying each row and each column with index in??????by−1. It follows that??????and
??????
??????
have the same spectrum.
IfΓ
??????
is obtained fromΓby switching w.r.t.??????, andΓ
????????????
is obtained fromΓ
??????
by
switching w.r.t.??????, thenΓ
????????????
is obtained fromΓby switching w.r.t.??????????????????. It follows that
graphs related by switching fall into equivalence classes (calledswitching classes).
Two graphs in the same switching class are calledswitching equivalent.
If two regular graphs of the same valency are switching equivalent, then they have
the same ordinary spectrum. This happens precisely when each vertex inside (outside)
the switching set is adjacent to half of the vertices outside (inside, respectively) the
switching set. For example, the Shrikhande graph is obtained from the 4×4gridby
switching w.r.t. a diagonal.
It may happen that two strongly regular graphs of diﬀerent valencies are switching
equivalent. If that happens, then they are related to regular 2-graphs (see §1.1.12).
Proposition 1.1.2LetΓbe a strongly regular graph with parameters(??????,??????,??????,??????)
and spectrum??????
1
??????
??????
??????
??????
.LetΔbe a strongly regular graph of valencyℓ>??????switching
equivalent toΓ. Then (i)Δhas spectrumℓ
1
??????
??????−1
??????
??????+1
, (ii)
1
2
??????=??????−??????=ℓ−??????, (iii)
??????−??????=2??????, (iv)
1
2
??????=2??????−??????−??????, (v) any switching set fromΓtoΔhas size
1
2
??????and
is regular of degree??????−??????.
Proof.(i)–(iv) The Seidel matrices??????=??????−??????−2??????ofΓandΔhave the same spectrum
(??????−1−2??????)
1
(−1−2??????)
??????
(−1−2??????)
??????
, and if??????<??????it follows that??????−1−2??????=−1−2??????
and??????−1−2ℓ=−1−2??????. Since(??????−??????)(??????−??????)=????????????for all strongly regular graphs, it
follows from??????−??????=
1
2
??????that??????−??????=2??????. Since??????+??????=??????−??????for all strongly regular
graphs, we ﬁnd
1
2
??????=??????−??????=??????−??????−??????+??????=??????+??????−??????+??????−2??????=2??????−??????−??????.
(v) SupposeΔis obtained fromΓby switching w.r.t. a set??????of size??????. Let??????∈??????
have??????
1neighbors in??????and?????? 2outside. Then??????=?????? 1+??????2andℓ=?????? 1+??????−??????−?????? 2, so that
??????
1and??????2can be expressed in terms of??????,ℓ,??????,??????and are independent of??????. Similarly,
if??????∉??????has??????
3neighbors in??????and?????? 4outside, then??????=?????? 3+??????4andℓ=??????−?????? 3+??????4,
so that??????
3and??????4are independent of??????. Counting the number of edges with one end
in??????in two ways, we ﬁnd??????
2??????=??????3(??????−??????), and since?????? 2=
1
2
(??????−ℓ−??????+??????)and
??????
3=
1
2
(??????−ℓ+??????)this simpliﬁes to(??????−ℓ)??????=(??????−ℓ)(??????−??????), so that??????=
1
2
??????,??????2=??????3,
??????
1=??????4. ﬃ

1.1 Strongly regular graphs 9
The Seidel matrix plays a role in the description of regular two-graphs and of sets
of equiangular lines, cf. [132], Chapter 10. The condition
1
2
??????=2??????−??????−??????is necessary
and suﬃcient for a strongly regular graph to be associated to a regular two-graph,
cf. [132], 10.3.2(i), and see below.
History
The Seidel matrix was introduced inSeidel[641].
1.1.12 Regular two-graphs
Atwo-graphΩ=(??????,Δ)is a ﬁnite set??????provided with a collectionΔof unordered
triples from??????, such that every 4-subset of??????contains an even number of triples from
Δ. The triples fromΔare calledcoherent.
From a graphΓ=(??????,??????), one can construct a two-graphΩ=(??????,Δ)by calling a
triple from??????coherent if the three vertices induce a subgraph inΓwith an odd number
of edges. One checks thatΩis a two-graph. It is called the two-graph associated to
Γ. Switching equivalent graphs have the same associated two-graph.
Conversely, from any two-graphΩ=(??????,Δ), and any ﬁxed??????∈??????, we can construct
a graphΓ=Ω
??????with vertex set??????as follows: let??????be an isolated vertex inΓ, and let
any two other vertices??????, ??????be adjacent inΓif{??????, ??????, ??????}∈Δ. ThenΩis the two-graph
associated toΓ.
Thus we have established a one-to-one correspondence between two-graphs and
switching classes of graphs.
LetΩ=(??????,Δ)be a two-graph, and??????∈??????. ThedescendantofΩat??????is the graph
Ω
∗
??????
, obtained fromΩ ??????by deleting the isolated vertex??????.
A two-graph(??????,Δ)is calledregular(of degree??????) if every unordered pair from??????is
contained in exactly??????triples fromΔ. The two-graphΩ=(??????,Δ)with??????=|??????|vertices
and 0<|Δ|<
ć
??????
3
ﬃ
is regular if and only if any descendant is strongly regular with
parameters(??????−1,??????,??????,??????)where??????=??????/2 (and then this holds for all descendants).
If this is the case, then??????=??????and??????=3??????−2??????.
See also §8.10 and [132], §10.3.
History
Regular two-graphs were introduced by G. Higman. See alsoTaylor[677].
1.1.13 Regular partitions and regular sets
LetΓbe a ﬁnite graph with vertex set??????. A partition{?????? 1,...,????????????}of??????is called
regularorequitablewhen there are numbers??????
????????????,1≤??????, ??????≤??????, such that each vertex
of??????
??????is adjacent to precisely?????? ????????????vertices in?????? ??????. In this situation the matrix??????=(?????? ????????????)
of order??????is called thequotient matrixof the partition.
If??????is an eigenvalue of??????,say????????????=????????????, then??????is also an eigenvalue ofΓ, for the

10 Graphs
eigenvector that is constant??????
??????on????????????. And conversely, the eigenvalues ofΓthat belong
to eigenvectors constant on each??????
??????are eigenvalues of??????.
LetΓbe ﬁnite and regular of valency??????. A subset??????of the vertex set??????is called
regular(ofdegree??????andnexus??????) when the partition{??????, ??????\??????}is regular (and??????
11=??????,
??????
21=??????where?????? 1=??????). Now the quotient matrix??????=(
??????????????????
????????????−??????
)has eigenvalues??????and
??????−??????, so that??????−??????is an (integral) eigenvalue ofΓ.
A regular set is also called anintriguing set([263]).
Proposition 1.1.3LetΓbe strongly regular with parameters(??????,??????,??????,??????).If??????and
??????
??????
are regular sets of degrees??????, ??????
??????
and nexus??????, ??????
??????
belonging to diﬀerent eigenvalues
??????−??????and??????
??????
−??????
??????
other than??????, then|??????∩??????
??????
|=????????????
??????
/??????.
Proof.The vector??????that is 1 on??????and??????:=
??????
??????−??????
outside??????is an eigenvector of the
adjacency matrix??????ofΓwith eigenvalue??????:=??????−??????. Here??????≠1 since??????≠??????. The
characteristic vector of??????is??????
??????
=
1
1−??????
??????
??????
1−??????
1, where
??????
1−??????
=
−??????
??????−??????
. Similarly for??????
??????
.
Since??????, ??????
??????
,1are mutually orthogonal,(1,1)=??????, and????????????=(????????????)(????????????
??????
),wehave
|??????∩??????
??????
|=(??????
??????
,??????
??????
??????)=
????????????
??????
(????????????)(????????????
??????
)
??????=????????????
??????
/??????. ﬃ
We also see that|??????|=(??????
??????
,1)=
????????????
??????−??????
with??????=??????−??????.
The collection of regular sets belonging to the same eigenvalue??????=??????−??????(together
with∅and??????) is closed under taking complements, under taking disjoint unions, and
under removal of one set from one containing it.
In descendants of regular two-graphs, switching sets are regular sets.
Proposition 1.1.4LetΓbe strongly regular with parameters(??????,??????,??????,??????)and re-
stricted eigenvalues??????, ??????, where??????=2??????.Let??????be a regular set inΓof degree??????and
nexus??????.If|??????|=??????−??????, where{??????, ??????−??????}={??????, ??????}, then adding an isolated vertex and
switching w.r.t.??????yields a strongly regular graph with parameters(??????+1,??????−??????, ??????−
??????, ??????−??????). ﬃ
1.1.14 Inequalities for subgraphs
We give inequalities that must hold for a graphΓto have certain induced subgraphs.
Additional regularity holds when there are such subgraphs and the inequality holds
with equality.
Interlacing
LetΓbe a ﬁnite graph with adjacency matrix??????, and letΠ={??????
1,...,????????????}be a
partition of a subset of
VΓ. Thequotient matrixof??????w.r.t.Πis the matrix??????of order
??????where??????
????????????is the average row sum of the submatrix??????(??????, ??????)of??????that has rows
indexed by??????
??????and columns indexed by?????? ??????. If each??????(??????, ??????)has constant row sums,
andΠpartitions
VΓ, thenΠis an equitable partition ofΓ, and??????is a quotient matrix
in the sense of §1.1.13 (hence the present deﬁnition generalizes the previous one).

1.1 Strongly regular graphs 11
Theorem 1.1.5LetΓbe a graph with adjacency matrix??????and??????vertices. Let
Π={??????
1,...,????????????}be a partition of a subset ofVΓwith quotient matrix??????. Then the
eigenvalues of??????interlace those of??????. That is, if??????has eigenvalues??????
1≥···≥?????? ??????
and??????has eigenvalues?????? 1≥ ··· ≥?????? ??????, then?????? ??????≥????????????(1≤??????≤??????)and?????? ??????−??????≥????????????−??????
(0≤??????≤??????−1).
If the interlacing is tight, that is, if there is anℎsuch that??????
??????=????????????for1≤??????≤ℎand
??????
??????=????????????−??????+??????forℎ+1≤??????≤??????, then the partition is equitable.
For a proof, and related results, see [132], §2.5.
Note that this theorem applies to an (induced) subgraphΔofΓwith adjacency
matrix??????. Indeed, one can take forΠthe partition of
VΔinto singletons.
Bounds on the size of regular subgraphs
As an application of interlacing, we ﬁnd bounds on the size of regular subgraphs of
a graph.
Proposition 1.1.6LetΓbe a regular graph with??????vertices, valency??????, second
largest eigenvalue??????and smallest eigenvalue??????.Let??????be a nonempty proper subset of
??????:=
VΓinducing a subgraph that is regular of degree??????. Then
(i)|??????|≤
??????(??????−??????)
??????−??????
, and
(ii)|??????|≥
??????(????????????)
????????????
if??????<??????.
(iii) If equality holds in either (i) or (ii), then each vertex in??????\??????has the same
number??????=??????−??????of neighbors in??????, where??????=??????in case (i), and??????=??????in case (ii).
Proof.Apply Theorem 1.1.5 withΠ={??????, ??????\??????}. Put??????=|??????|. The quotient matrix
is
??????=
ő
???????????? −??????
??????(??????−??????)
??????−??????
??????−
??????(??????−??????)
??????−??????
ă
with eigenvalues??????and??????−
??????(??????−??????)
??????−??????
. By interlacing we have??????≤??????−
??????(??????−??????)
??????−??????
≤??????, which
gives (i) and (ii). If equality holds on either side, then the partition is equitable, and
??????=
??????(??????−??????)
??????−??????
. ﬀ
One sees that in case of equality the vector??????
??????
−
??????
??????
1is an eigenvector of??????with eigenvalue??????=??????−??????.
If??????has small multiplicity this allows a computer search for all such subgraphs??????.
Hoﬀman bound
In particular, we have the so-called Hoﬀman bounds (due to Delsarte for strongly
regular graphs, generalized by Hoﬀman to arbitrary regular graphs, then further by
Haemers to arbitrary graphs) on the sizes of cliques and cocliques.
Proposition 1.1.7LetΓbe a strongly regular graph with parameters(??????,??????,??????,??????)
and smallest eigenvalue??????. Then
(i) If??????is a coclique inΓ, then|??????|≤??????/(1+
??????
−??????
). If equality holds, then each vertex
outside??????has the same number−??????of neighbors inside.

12 Graphs
(ii) If??????is a clique inΓ, then|??????|≤1+
??????
−??????
. If equality holds, then each vertex
outside??????has the same number??????/(−??????)of neighbors inside.
(iii) If a coclique??????and a clique??????both meet the bounds of (i) and (ii), then
|??????∩??????|=1.
Proof.Part (i) is the special case??????=0 of Proposition 1.1.6. Part (ii) is part (i)
applied to
Γ. For part (iii), clearly??????and??????cannot have more than one point in
common. If they are disjoint, then the number of edges joining??????and??????is both??????−??????
and????????????/(??????−??????)=??????−??????, a contradiction. ﬃ
If a regular set in a strongly regular graph is a coclique or a clique, then it has
equality in (i) or (ii), respectively.
The bound on cocliques forΓequals the bound on cliques for the complementary
graph
Γ, i.e.,??????/(1+
??????
−??????
)=1+
????????????1
??????+1
.
Quadratic counting
Similar results are obtained by combinatorial methods. Consider a strongly regular
graph with parameters(??????,??????,??????,??????)and an induced subgraph with??????vertices,??????edges,
and degree sequence??????
1,...,????????????. Let there be?????? ??????vertices outside the subgraph that
are adjacent to precisely??????vertices inside. Then
ň
??????
????????????=??????=??????−??????,
ň
??????
??????????????????=??????=????????????−2??????,
ň
??????
č
??????
2
ă
??????
??????=??????=????????????+??????(
č
??????
2
ă
−??????)−
??????ň
??????=1
č
??????
??????
2
ă
.
Let??????=??????/??????and put??????
=??????????????????and
??????=??????????????????. Then
(??????+2??????)−(??????
+
??????)??????+??????????????????=
ň
??????
(??????−??????)(??????−
??????)????????????≥0. (*)
Equality holds if and only if every vertex outside the subgraph is adjacent to either??????
or
??????vertices inside.
If the subgraph is a clique or a coclique, the inequality
ﬃ
??????(??????−??????)
2
????????????≥0 is equivalent
to the Hoﬀman bound. When??????is nonintegral, inequality (*) is slightly stronger.
This inequality is folklore. For the case of cliques an equivalent inequality was rediscovered in [364].
Sometimes combinatorial bounds are stronger than the Hoﬀman bound. For example, for the parameter
set(??????, ??????, ??????, ??????)=(400,21,2,1)with??????=−4, the Hoﬀman bound for the size of cliques is 6.25, but the
obvious upper bound??????+2is4.
For the case of cliques of size??????, the above counts become
ﬃ
??????
??????=??????−??????,
ﬃ
???????????? ??????=??????(??????−??????+1),
ﬃﬀ
??????
2
ć
??????
??????=
ﬀ
??????
2
ć
(??????−??????+2). For example, for(??????, ??????, ??????, ??????)=(235,42,9,7)with??????=−5, the Hoﬀman
bound is 9.4, but the above counting also rules out size 9. And for(??????, ??????, ??????, ??????)=(11124,882,45,72),
with??????=−45, the Hoﬀman bound is 20.6, but the above counting rules out size 18 so that the upper bound
for clique sizes becomes 17.

1.1 Strongly regular graphs 13
Cvetković bound
LetΓbe a graph on??????vertices, and let??????be a matrix indexed by
VΓsuch that?????? ????????????=0
when??????ﬀ??????. Let??????
+
(??????)(resp.??????
−
(??????)) be the number of positive (resp. negative)
eigenvalues of??????. For the independence number??????(Γ)ofΓwe have the bound (known
asCvetković boundorinertia bound)
??????(Γ)≤min(??????−??????
+
(??????),??????−?????? (??????)).
One has additional regularity in case both the Hoﬀman and the Cvetković bound
are tight.
Proposition 1.1.8(Haemers[376], Theorem 2.1.7)LetΓbe a strongly regular
graph with point set??????, and??????a coclique inΓwith|??????|=1+
????????????1
??????+1
=??????. Then the
graph induced on??????\??????is strongly regular.
This happens for example for a 21-coclique in a graph with parameters(??????,??????,??????,??????)=
(77,16,0,4). See also §8.5.8.
Greaves-Koolen-Park bound
Greaves,Koolen&Park[363] derived a bound on the size of maximal cliques that
rules out an interval of values. In some cases that interval extends past the Hoﬀman
upper bound, so that the upper bound is greatly strengthened. If in addition one
can show that cliques must exist with a size past the start of the interval, then the
corresponding parameter set is ruled out.
Denote by??????(??????, ??????)the graph on??????+??????+1 vertices consisting of a clique??????
??????+??????together
with a vertex that is adjacent to precisely??????vertices of the clique. The graph??????(??????, ??????)
has an obvious equitable partition with quotient matrix
??????=
⎡
⎢
⎢
⎢
⎢
⎣
0?????? 0
1??????−1??????
0????????????−1
⎤
⎥
⎥
⎥
⎥
⎦
.
Lemma 1.1.9LetΓbe a graph having smallest eigenvalue−??????that contains??????(??????, ??????)
as an induced subgraph. Then
(??????−??????(??????−1))(??????−(??????−1)
2
)≤(??????(??????−1))
2
.
Proof.This inequality expresses det(??????+????????????)≥0. ﬀ
If a strongly regular graphΓhas a maximal clique??????of size??????, and a vertex outside
adjacent to??????vertices of the clique, then??????≤??????. The above lemma (with??????=??????−??????)
gives a quadratic inequality on??????, and if the quadratic has two roots??????
1,??????2, then
??????
1<??????<??????2is excluded. If?????? 1≤??????<??????2, it follows that??????≤?????? 1. On the other hand,
there are certainly vertices outside??????that have at least??????=1+
(??????−1)(??????−??????+2)
??????−??????+1
neighbors
in??????. The inequality??????≤??????≤??????
1gives a condition on??????.

14 Graphs
Lemma 1.1.10LetΓbe a strongly regular graph with parameters(??????,??????,??????,??????)and
smallest eigenvalue−??????, where??????>??????(??????−1).IfΓhas a maximal clique??????of order
??????>max{(??????−1)(4??????−1),
??????
2
??????−??????(??????−1)
−??????+1}and??????=(??????+??????−1)(??????−(??????−1)(4??????−1))
then(2(??????−1)(??????−??????+2)−(??????+??????−3)(??????−??????+1))
2
−(??????−??????+1)
2
??????≥0.
This lemma gives a cubic condition on??????.
For example, consider the case(??????, ??????, ??????, ??????)=(1344,221,88,26)where??????=3. The Hoﬀman bound
is??????≤74. Lemma 1.1.10 says that 32≤??????≤80 is impossible for maximal cliques. So a maximal clique
has size at most 31.
By the usual claw-and-clique method (cf. §8.6.5) one ﬁnds a lower bound for the
size of maximum cliques.
Lemma 1.1.11LetΓbe a strongly regular graph with parameters(??????,??????,??????,??????).If??????
is a nonnegative integer such that(??????1)
ﬀ
??????
2
ć
<??????(??????+1)??????, thenΓhas a clique of
size at least??????+2−(??????−2)(??????−1).
Together with the above, this sometimes suﬃces to rule out a parameter set.
For example, consider the case(??????, ??????, ??????, ??????)=(23276,1330,372,58)with??????=4. The Hoﬀman bound
says that cliques have sizes??????≤333. By Lemma 1.1.10, for maximal cliques 71≤??????≤340 is impossible.
By Lemma 1.1.11 with??????=6, there is a clique of size??????≥146. It follows that no such graph exists.
1.1.15 Connectivity
For a graphΓ, letΓ ??????(??????)denote the set of vertices at distance??????from??????inΓ. Instead
ofΓ
1(??????)we writeΓ(??????). Using interlacing, we see that the 2nd subconstituent of a
primitive strongly regular graph is connected.
Proposition 1.1.12IfΓis a primitive strongly regular graph, then the subgraph
Γ
2(??????)is connected for each vertex??????.
Proof.Note thatΓ
2(??????)is regular of valency????????????. If it is not connected, then its
eigenvalue????????????would have multiplicity at least two, and hence would be not larger
than the second largest eigenvalue??????ofΓ. Then??????
2
+(??????−??????)??????+??????−??????≤0for??????=??????−??????,
i.e.,(??????−??????)(??????−??????−1)≤0, a contradiction. ﬃ
Thevertex connectivity??????(Γ)of a connected non-complete graphΓis the smallest
integer??????such thatΓcan be disconnected by removing??????vertices.
Theorem 1.1.13(Brouwer&Mesner[138])LetΓbe a connected strongly regular
graph of valency??????. Then??????(Γ)=??????, and the only disconnecting sets of size??????are the
sets of all neighbors of some vertex??????. ﬃ
One might guess that the cheapest way to disconnect a strongly regular graph such
that all components have at least two vertices would be by removing the 2??????−??????−2
neighbors of an edge.Cioabă,Kim&Koolen[198] observed that this is false (the
simplest counterexample is probably??????(6), where edges have 10 neighbors and certain
triangles only 9), but proved it for several inﬁnite classes of strongly regular graphs
and conjectured that any counterexample must have??????≥??????/2. See also [199].

1.1 Strongly regular graphs 15
1.1.16 Graphs induced on complementary subsets of the vertex set of a
graph
For a real symmetric matrix with two distinct eigenvalues, and with a symmetric 2×2
partition of rows and columns, the spectrum of the upper left-hand corner determines
the spectrum of the lower right-hand corner (cf. [132], Lemma 2.11.1).
For strongly regular graphs with adjacency matrix??????this applies to??????−????????????for
suitable??????, so that the spectrum of a regular induced subgraph determines the spectrum
of the subgraph induced on the complementary set of vertices, when that is also
regular. More generally, one has
Proposition 1.1.14(de Caen[264])LetΓbe strongly regular on??????vertices,
with spectrum??????
1
??????
??????
??????
??????
, and suppose thatVΓhas a partition{??????, ??????}such that
the graphΓ[??????]induced byΓon??????is regular, with valency??????
??????.Let??????=|??????|.If
Γ[??????]has eigenvalues??????
??????,??????1,...,????????????−1, then the graphΓ[??????]has eigenvalues??????(with
multiplicity??????−??????),??????(with multiplicity??????−??????),??????+??????−??????
??????(1≤??????≤??????−1), together
with the two roots of(??????−??????)(??????−??????−??????+??????
??????)+????????????=0.
In the case of a regular partition, these two roots can be given explicitly:
Proposition 1.1.15If also the graphΓ[??????]is regular, with valency??????
??????, then?????? ??????+
??????
??????−??????∈{??????, ??????}, and(??????−??????)(??????−??????−??????+?????? ??????)+????????????=
(??????????????????)(????????????)(????????????)
??????????????????????????????+??????
.
For example, ifΓis a strongly regular graph with parameters(??????,??????,??????,??????)=
(28,9,0,4)and??????is a point-neighborhood (a 9-coclique), then??????has spectrum
1
12
(−5)
−3
(−4)
8
5
1
0
1
, a contradiction. So no such graph exists.
For example, ifΓis the unique strongly regular graph with parameters(??????,??????,??????,??????)=
(77,16,0,4)and??????is a 21-coclique, then??????induces a Gewirtz subgraph (with
parameters(??????,??????,??????,??????)=(56,10,0,2)and spectrum 10
1
2
35
(−4)
20
, see §10.20).
For example, ifΓis the
O
−
6
(3)graph on 112 vertices (with parameters(??????,??????,??????,??????)=
(112,30,2,10)and spectrum 30
1
2
90
(10)
21
, see §10.34), and??????induces a Gewirtz
subgraph, then the subgraph induced on the remaining 56 vertices has the same
spectrum, and hence is also a Gewirtz subgraph.
See also [178], [381].
1.1.17 Enumeration
For some smallish parameter sets, a complete enumeration of all strongly regular
graphs has been made. We list only one graph from a complementary pair. Triangular
graphs and??????×??????grids on more than 50 vertices are not listed.
count???????????????????????? ref
1 5 2 0 1 pentagon
194123 ×3grid
1 10 3 0 1 Petersen graph,
??????(5)
1 13 6 2 3 Paley
continued...

16 Graphs
count???????????????????????? ref
1 15 6 1 3 GQ(2,2),??????(6)
1 16 5 0 2 folded 5-cube, complement of the Clebsch graph
2166224 ×4 grid, Shrikhande graph
1 17 8 3 4 Paley
1 211036
??????(7)
1258325 ×5grid
15 25 12 5 6 Paulus [606]; enumerated by Rozenfel’d [632]
10 26 10 3 4 Paulus [606]; enumerated by Rozenfel’d [632]
1 27 10 1 5 GQ(2,4), complement of the Schläﬂi graph
4 281264 ??????(8), 3 Chang graphs
41 29 14 6 7 enumerated by Bussemaker and by Spence
3854 35 16 6 8 enumerated by McKay & Spence [556]
1 3610426 ×6grid
180 36 14 4 6 enumerated by McKay & Spence [556]
1 361474 ??????(9)
32548 36 15 6 6 enumerated by McKay & Spence [556]
28 40 12 2 4 enumerated by Spence [670]
78 45 12 3 3 enumerated by Coolsaet, Degraer & Spence [223]
1 451684 ??????(10)
1 4912527 ×7grid
1 50 7 0 1 Hoﬀman & Singleton [436]
1 56 10 0 2 Gewirtz [342]
167 64 18 2 6 enumerated by Haemers & Spence [384]
1 77 16 0 4 Brouwer [111]
1 81 20 1 6 Brouwer & Haemers [130]
1 100 22 0 6 Gewirtz [341]
1 105 32 4 12 Coolsaet [221]
1 112 30 2 10 Cameron, Goethals & Seidel [178]
1 120 42 8 18 Degraer & Coolsaet [274]
1 126 50 13 24 Coolsaet & Degraer [222]
1 162 56 10 24 Cameron, Goethals & Seidel [178]
1 176 70 18 34 Degraer & Coolsaet [274]
1 275 112 30 56 Goethals & Seidel [356]
Table 1.1Number of nonisomorphic strongly regular graphs
Let us call a parameter set(??????,??????,??????,??????)feasiblewhen it and its complement satisfy
the conditions of §1.1.1 and §1.1.4. There are further general conditions on strongly
regular graphs, such as the absolute bound (§1.3.7), the Krein conditions (§1.3.4), the
claw bound (§8.6.4), and the condition on conference graphs (§8.2), and on graphs
with??????=1or??????=2 (§8.18). For a few sets of parameters there is an ad hoc proof
that no such graph exists. Below the current list of such cases.
???????????????????????? ref
49 16 3 6 Bussemaker et al. [162]
57 14 1 4 Wilbrink & Brouwer [732]
75 32 10 16 Azarija & Marc [20]
76 21 2 7 Haemers [378]; see also [8]
76 30 8 14 Bondarenko et al. [89]
95 40 12 20 Azarija & Marc [21]
96 38 10 18 Degraer [273]
continued...

1.2 Distance-regular graphs 17
???????????????????????? ref
289 54 1 12 Bondarenko & Radchenko [90]
324 57 0 12 Gavrilyuk & Makhnev [336],
Kaski & Östergård [483]
460 153 32 60 Bondarenko et al. [88]
486 165 36 66 Makhnev [534]
1127 486 165 243 Makhnev [534]
1911 270 105 27 Koolen & Gebremichel
1
3159 1408 532 704 Bannai et al. [49], [646]
Table 1.2Sporadic parameter sets for which no srg exists
Makhnev[535] purports to show the nonexistence of graphs with parameters(??????, ??????, ??????, ??????)=(784,
116,0,20), but the proof is wrong. Also the proof inMakhnev[536] of the nonexistence of graphs with
parameters(3250,57,0,1)is wrong.
Money
J. H. Conway[214] oﬀered $1000 for the construction or nonexistence proof of a
strongly regular graph with parameters(??????,??????,??????,??????)=(99,14,1,2).
Wilbrink[731] showed that such a graph cannot have an automorphism of order 11, and hence cannot
have a transitive group.Behbahani&Lam[55] show that any automorphism of prime order must have
order 2 or 3.Crnković&Maksimović[240] rule out groups of order six or nine.
History
Uniqueness of the triangular graphs??????(??????), given the parameters, was shown for??????≥9
byConnor[211], for??????≤6byShrikhande[648], and for??????≠8byHoffman[432].
The latter also found a counterexample for??????=8. Independently,Chang[191, 192]
settled all cases and found the three counterexamples for??????=8.
Uniqueness of the lattice graph??????
2(??????),??????≠4 was shown byMesner[559].
Shrikhande[649] gave a shorter proof and also found the single exception.
1.1.18 Proliﬁc constructions
Strongly regular graphs live on the boundary between the crystalline world and the
random world. For some parameters there is no graph, or a unique graph. For other
parameters the number of examples is exponentially large. Constructions that produce
hyperexponentially many strongly regular graphs for certain parameters have been
given byWallis[718] andFon-Der-Flaass[328]. See also [184], [176], [580].
1.2 Distance-regular graphs
A ﬁnite connected graphΓof diameter??????is calleddistance-regularwithparameters
??????
??????,????????????,????????????(0≤??????≤??????)if for any two vertices??????, ??????with mutual distance??????(??????, ??????)=??????the
number of vertices??????adjacent to??????and at distance??????−1or??????or??????+1 from??????equals??????
??????
or????????????or????????????, respectively.
1 Pers. comm., Aug. 2021.

18 Graphs
A distance-regular graph is regular with valency??????=??????
0, and?????? ??????+????????????+????????????=??????for
all??????. Obviously??????
0=??????0=????????????=0 and?????? 1=1. Theintersection arrayis the symbol
{??????
0,??????1,...,????????????−1;??????1,??????2,...,????????????}that suﬃces to determine all parameters.
The distance-regular graphs of diameter 2 are precisely the connected strongly
regular graphs. A connected strongly regular graph with parameters(??????,??????,??????,??????)is
distance-regular with intersection array{??????, ??????−??????−1; 1,??????}.
LetΓbe distance-regular, with vertex??????. The number??????
??????of vertices at distance??????
from??????is found by??????
0=1 and?????? ??????+1=????????????????????????/????????????+1for 0≤??????≤??????−1, and is independent
of the choice of??????. The total number of vertices is??????=??????
0+···+?????? ??????.
Let??????=|
VΓ|. Let?????? ??????be the matrix of order??????indexed by VΓwith(?????? ??????)????????????=1 when
??????(??????, ??????)=??????and(??????
??????)????????????=0 otherwise. Clearly?????? 0=??????. Let??????=?????? 1be the adjacency
matrix ofΓ. Then????????????
??????=????????????1????????????1+????????????????????????+????????????+1????????????+1for 0≤??????≤??????, if we agree that
??????
1??????−1=????????????+1????????????+1=0. We ﬁnd an expression for?????? ??????of degree??????in??????, and then
an equation of degree??????+1for??????, so that??????has precisely??????+1 distinct eigenvalues
(since the matrices??????
??????are linearly independent).
Biggs’ multiplicity formula
The previous paragraph implies (for a precise argument see also below) that the??????+1
eigenvalues of??????are the??????+1 eigenvalues of the matrix??????, where
??????=
??????
??????
??????
??????
??????
??????
??????
??????
0??????
0 0
??????
1??????1??????1
??????2??????2??????2
... ... ...
0 ??????
??????????????????
??????
??????
??????
??????
??????
??????
??????
??????
.
Theorem 1.2.1(Biggs[67], Theorem 21.4)If????????????=????????????and??????
0=1, then the
multiplicity of??????as eigenvalue ofΓequals
??????(??????)=??????/(
ň
??????
????????????
2
??????
).
Proof.We have??????
??????=????????????(??????)where the polynomials?????? ??????are deﬁned by?????? 0(??????)=1,
??????
1(??????)=??????,???????????? ??????(??????)=?????? ??????1????????????1(??????)+?????? ??????????????????(??????)+?????? ??????+1????????????+1(??????).If??????is an eigenvalue of??????,
then??????(??????)=(??????
0(??????),...,????????????(??????))is a left eigenvector of??????and??????(??????)??????=????????????(??????). The
??????
??????satisfy?????? ??????????????????1+????????????????????????+????????????????????????+1=??????????????????, so that?????? ??????(??????)=?????? ??????????????????.Now??????=tr
ﬃ
??????????????????????????????=
ﬃ
??????,????????????????????????(??????)?????? ??????(??????)=??????(??????)
ﬃ
????????????????????????
2
??????
, where the sum is over the eigenvalues??????of??????, and
the last equality holds because left and right eigenvectors for diﬀerent eigenvalues
are orthogonal. ﬃ
Thus, the parameters of a distance-regular graph determine eigenvalues and mul-
tiplicities. The fact that the multiplicities must be integers is a strong restriction on
candidate parameter sets.
A comprehensive monograph on the topic of distance-regular graphs, complete up

1.2 Distance-regular graphs 19
to 1989, isBrouwer,Cohen&Neumaier[123]. An update to the state of aﬀairs
in 2016 isVan Dam,Koolen&Tanaka[252].
1.2.1 Distance-transitive graphs
A connected graphΓis calleddistance-transitiveif for any vertices??????, ??????, ??????, ??????with
??????(??????, ??????)=??????(??????, ??????)there is an automorphism??????ofΓsuch that??????(??????)=??????and??????(??????)=??????.
IfΓis distance-transitive of diameter??????, then its group of automorphisms is transitive,
of rank??????+1.
Every ﬁnite distance-transitive graph is distance-regular.
The classiﬁcation of distance-transitive graphs of diameter??????>2 is unﬁnished.
For a survey of the status in 2007, seeVan Bon[86].
1.2.2 Johnson graphs
The Johnson graph??????(??????, ??????), where??????≥2??????, is distance-transitive of diameter??????.It
has parameters??????
??????=(??????−??????)(??????−??????−??????),?????? ??????=??????
2
and eigenvalues?????? ??????−??????with multiplicity
ć
??????
??????
ﬃ
−
ć
??????
??????1
ﬃ
(0≤??????≤??????) and??????=
ć
??????
??????
ﬃ
vertices.
1.2.3 Hamming graphs
The Hamming graph??????(??????, ??????), where??????>1, is distance-transitive of diameter??????.It
has parameters??????
??????=(??????−1)(??????−??????),?????? ??????=??????and eigenvalues?????? ??????−??????with multiplicity
ć
??????
??????
ﬃ
(??????−1)
??????
(0≤??????≤??????) and??????=??????
??????
vertices.
1.2.4 Grassmann graphs
Let??????be a vector space of dimension??????over the ﬁeldF ??????. TheGrassmann graph
??????
??????(??????, ??????)is the graph with vertex set
w
??????
??????
b
, the set of all??????-subspaces of??????, where
two??????-subspaces are adjacent when they intersect in an(??????−1)-space. This graph is
distance-transitive, with parameters??????
??????=??????
2??????+1
w
??????−??????
1
bw
????????????−??????
1
b
,??????
??????=
w
??????
1
b2
, diameter??????=
min(??????, ??????−??????), and eigenvalues??????
??????+1
w
??????−??????
1
bw
????????????−??????
1
b
−
w
??????
1
b
with multiplicity
w
??????
??????
b
−
w
??????
??????1
b
.
(Here
w
??????
??????
b
=(??????
??????
−1)···(??????
????????????+1
−1)/(??????
??????
−1)···(??????−1)is the??????-binomial coeﬃcient,
the number of??????-subspaces of an??????-space.)
In particular, for??????=2,??????≥4, we ﬁnd the graph??????
??????(??????,2)of lines in a projective
space, adjacent when they meet. This graph is strongly regular, with parameters
??????=
w
??????
2
b
,??????=(??????+1)(
w
??????−1
1
b
−1),??????=
w
??????−1
1
b
+??????
2
−2,??????=(??????+1)
2
, and eigenvalues??????,
??????=??????
2
w
??????−3
1
b
−1,??????=−??????−1 with multiplicities, 1,??????=
w
??????
1
b
−1,??????=
w
??????
2
b
−
w
??????
1
b
.

20 Graphs
1.2.5 Van Dam-Koolen graphs
Van Dam&Koolen[251] construct distance-regular graphs vDK(??????, ??????)with the
same parameters as??????
??????(2??????+1,??????). (They call them thetwisted Grassmann graphs.)
The group of automorphisms of these graphs is not transitive.
The construction is as follows. Let??????be a vector space of dimension 2??????+1 over
F
??????, and let??????be a hyperplane of??????. Take as vertices the(??????+1)-subspaces of??????not
contained in??????, and the(??????−1)-subspaces contained in??????, where two subspaces of
the same dimension are adjacent when their intersection has codimension 1 in both,
and two subspaces of diﬀerent dimension are adjacent when one contains the other.
It follows that Grassmann graphs need not be determined by their parameters. Also,
that the combinatorial deﬁnition of distance-regular graphs does not directly imply
the existence of a nice group of automorphisms, not even when the diameter is large.
For??????=2, these graphs are strongly regular.
1.2.6 Imprimitive distance-regular graphs
LetΓbe a distance-regular graph of diameter??????, and letΓ ??????be the graph with the same
vertex set, where two vertices are adjacent when they have distance??????inΓ, so that??????
??????
is the adjacency matrix ofΓ ??????(0≤??????≤??????). The graphΓis calledimprimitiveifΓ ??????is
disconnected for some??????,2≤??????≤??????.
IfΓis apolygon(i.e., if it has valency 2) thenΓ
??????is disconnected for each??????with
??????|??????,1<??????<??????. The only imprimitive distance-regular graphs of valency??????>2 are
the bipartite and the antipodal graphs.
A graph is calledbipartiteif it does not contain an odd cycle. Ahalved graphof
a connected bipartite graphΓis the graph with as vertex set one of the two bipartite
classes, where two vertices are adjacent when they have distance 2 inΓ.
A distance-regular graph of diameter??????is calledantipodalwhen having distance
0or??????is an equivalence relation on its vertex set. Thefolded graphof an antipodal
distance-regular graph is the graph with as vertices the equivalence classes ofΓ
??????,
where two equivalence classes are adjacent when they contain adjacent vertices.
Theorem 1.2.2An imprimitive distance-regular graph of valency??????,??????>2,is
bipartite or antipodal (or both). LetΓbe distance-regular of diameter??????with
intersection array{??????
0,...,????????????1;??????1,...,????????????}, and put??????=?????? 2and??????=y??????/2w.
(i)Γis bipartite if and only if??????
??????=0(i.e.,?????? ??????+????????????=??????) for all??????.IfΓis bipartite,
then its halved graphs are distance-regular of diameter??????with intersection array
{
??????
0??????1
??????
,
??????
2??????3
??????
,...,
??????
2??????2??????2??????1
??????
;
??????
1??????2
??????
,
??????
3??????4
??????
,...,
??????
2??????1??????2??????
??????
}.
(ii)Γis antipodal if and only if??????
??????=??????????????????for all??????≠??????.IfΓis antipodal, then its
antipodal classes have size??????=1+??????
??????/????????????−??????, and the folded graph is distance-regular
of diameter??????with intersection array
{??????
0,...,????????????−1;??????1,...,????????????−1,??????????????????}

1.3 Association schemes and coherent conﬁgurations21
where??????=??????if??????=2??????, and??????=1if??????=2??????+1. ﬀ
For example, the Johnson graph??????(2??????, ??????)is antipodal. Thefolded Johnson graph
??????(2??????, ??????)(of which the vertices are the partitions of a 2??????-set into two??????-sets) is
distance-regular of diameter????????????/2??????, and in particular is strongly regular for??????=4,5.
1.2.7 Taylor graphs
A distance-regular graphΓwith intersection array{??????, ??????,1; 1,??????,??????}is called aTaylor
graph. Such a graph is an antipodal double cover of the complete graph??????
??????+1. The local
graphsΔ=Γ(??????)are strongly regular, and satisfy??????
Δ=??????,??????Δ=??????Γ=??????−??????−1=2?????? Δ,
??????
Δ=
1
2
(3??????Δ−??????−1). See §8.10.4.
Given a graphΣwith vertex set??????, itsTaylor doubleis the graph with vertex set
{??????
??????
|??????∈??????,??????=±1}and edges??????
??????
??????
??????
(for??????≠??????) with????????????=1 when??????∼??????and
????????????=1 otherwise.
Given a strongly regular graphΔwith??????
Δ=2??????Δ, itsTaylor extensionTΔis the
Taylor double of{∞} +Δ. It is a Taylor graph.
1.3 Association schemes and coherent conﬁgurations
We brieﬂy state the main facts for symmetric association schemes. For more details,
see [123], Chapter 2, and [132], Chapter 11. Results proved there are given here
without proof.
1.3.1 Association schemes
A (symmetric)association scheme with??????classesis a ﬁnite set??????together with??????+1
relations??????
??????on??????such that
(i){??????
0,??????1,...,????????????}is a partition of??????×??????;
(ii)??????
0={(??????, ??????)|??????∈??????};
(iii) if(??????, ??????)∈??????
??????, then also(??????, ??????)∈?????? ??????, for all??????, ??????∈??????and??????∈{0,...,??????};
(iv) for any(??????, ??????)∈??????
??????the number??????
??????
????????????
of??????∈??????with(??????, ??????)∈?????? ??????and(??????, ??????)∈?????? ??????
depends only on??????,??????and??????.
The numbers??????
??????
????????????
are called theintersection numbersof the association scheme.
Deﬁne??????=|??????|, and??????
??????=??????
0
????????????
. Clearly, for each??????∈{1,...,??????},(??????, ?????? ??????)is a simple
graph which is regular of degree??????
??????.
Proposition 1.3.1The intersection numbers of an association scheme satisfy
(i)??????
??????
0??????
=??????????????????,??????
0
????????????
=??????????????????????????????,??????
??????
????????????
=??????
??????
????????????
,
(ii)
ﬀ
????????????
??????
????????????
=????????????,
ﬀ
??????????????????=??????,
(iii)??????
??????
????????????
????????????=??????
??????
????????????
????????????,
(iv)
ﬀ
????????????
??????
????????????
??????
??????
????????????
=
ﬀ
????????????
??????
????????????
??????
??????
????????????
. ﬀ

22 Graphs
It is convenient to write the intersection numbers as entries of the so-called
intersection matrices??????
0,...,????????????deﬁned by
(??????
??????)????????????=??????
??????
????????????
.
Note that??????
0=??????and?????? ??????????????????=
ﬃ
??????
??????
????????????
????????????.
From the deﬁnition it is clear that an association scheme with two classes is the
same as a pair of complementary strongly regular graphs. If(??????, ??????
1)is strongly
regular with parameters(??????,??????,??????,??????), then the intersection matrices of the scheme are
??????
1=
⎡
⎢
⎢
⎢
⎢
⎣
0?????? 0
1????????????−??????−1
0????????????−??????
⎤
⎥
⎥
⎥
⎥
⎦
,?????? 2=
⎡
⎢
⎢
⎢
⎢
⎣
00 ??????−??????−1
0??????−??????−1??????−2??????+??????
1??????−????????????−2??????+??????−2
⎤
⎥
⎥
⎥
⎥
⎦
.
History
Association schemes as deﬁned above (known as ‘symmetric association schemes’)
were introduced inBose&Shimamoto[97] as one of the ingredients for a partially
balanced incomplete block design (PBIBD). Almost the same deﬁnition of PBIBD
occurs already inBose&Nair[96].
1.3.2 The Bose-Mesner algebra
The relations?????? ??????of an association scheme are described by their adjacency matrices
??????
??????of order??????deﬁned by
(??????
??????)????????????=
??????
1 whenever(??????, ??????)∈??????
??????,
0 otherwise.
In other words,??????
??????is the adjacency matrix of the graph(??????, ?????? ??????). In terms of the
adjacency matrices, the axioms (i)–(iv) become
(i)
ﬃ
??????
??????=0
????????????=??????,
(ii)??????
0=??????,
(iii)??????
??????=??????
??????
??????
, for all??????∈{0,...,??????},
(iv)??????
??????????????????=
ﬃ
????????????
??????
????????????
????????????, for all??????, ??????∈{0,...,??????}.
From (i) we see that the(0,1)matrices??????
??????are linearly independent, and by use of
(ii)–(iv) we see that they generate a commutative(??????+1)-dimensional algebraAof
symmetric matrices with constant diagonal. This algebra was ﬁrst studied byBose&
Mesner[95] and is called theBose-Mesner algebraof the association scheme.
Since the matrices??????
??????commute, they can be diagonalized simultaneously. It follows
that the algebraAis semisimple and has a unique basis of minimal idempotents
??????
0,...,????????????, where?????? ??????????????????=??????????????????????????????and
ﬃ
??????
??????=0
????????????=??????.
The matrix
1
??????
??????is a minimal idempotent. We shall ﬁx the numbering so that
??????
0=
1
??????
??????. Let??????and
1
??????
??????be the matrices relating our two bases forA:
??????
??????=
??????ň
??????=0
??????????????????????????????,????????????=
1
??????
??????ň
??????=0
??????????????????????????????.

1.3 Association schemes and coherent conﬁgurations23
Then clearly
????????????=????????????=????????????.
It also follows that
??????
??????????????????=??????????????????????????????,
which shows that the??????
????????????are the eigenvalues of?????? ??????and that the columns of?????? ??????are
the corresponding eigenvectors. Thus??????
??????=rk?????? ??????is the multiplicity of the eigenvalue
??????
????????????of????????????(provided that?????? ????????????≠??????????????????for??????≠??????). We see that?????? 0=1,
ﬀ
??????????????????=??????, and
??????
??????=trace?????? ??????=??????·(?????? ??????)????????????(indeed,?????? ??????has only eigenvalues 0 and 1, so rk?????? ??????equals
the sum of the eigenvalues).
Proposition 1.3.2The numbers??????
????????????and?????? ????????????satisfy
(i)??????
??????0=????????????0=1,?????? 0??????=????????????,??????0??????=????????????,
(ii)??????
??????????????????????????????=
ﬀ
??????
??????=0
??????
??????
????????????
??????????????????,
(iii)??????
????????????????????????=??????????????????????????????,
ﬀ
??????????????????????????????????????????????????????=????????????????????????????????????,
ﬀ
??????????????????????????????????????????????????????=????????????????????????????????????,
(iv)|??????
????????????|≤????????????,|??????????????????|≤????????????. ﬀ
An association scheme is calledprimitiveif no union of the relations is a nontrivial
equivalence relation. Equivalently, if no graph(??????, ??????
??????)with??????≠0 is disconnected.
For a primitive association scheme, (iv) above can be sharpened to|??????
????????????|<????????????and
|??????
????????????|<????????????for??????≠0.
If??????=2, and(??????, ??????
1)is strongly regular with parameters(??????,??????,??????,??????)and spectrum
??????
1
??????
??????
??????
??????
, the matrices??????and??????are
??????=
⎡
⎢
⎢
⎢
⎢
⎣
1??????????????????1
1??????−??????−1
1??????−??????−1
⎤
⎥
⎥
⎥
⎥
⎦
,??????=
⎡
⎢
⎢
⎢
⎢
⎣
1 ????????????
1????????????/??????????????????/??????
1−??????
??????+1
????????????−1
−??????
??????+1
????????????−1
⎤
⎥
⎥
⎥
⎥
⎦
.
The matrices??????and??????can be computed from the intersection numbers of the
scheme.
Proposition 1.3.3For??????=0,...,??????, the intersection matrix??????
??????has eigenvalues?????? ????????????
(0≤??????≤??????). ﬀ
The fact that the multiplicities??????
??????=??????0??????must be nonnegative integers is a powerful
restriction on the parameters of an association scheme.
1.3.3 Linear programming bound and code-clique theorem
Being symmetric and idempotent, the matrices?????? ??????are positive semideﬁnite. (Indeed,
for any vector??????∈R
??????
and any??????with??????
??????
=??????=??????
2
one has??????
??????
????????????=??????
??????
??????
2
??????=
??????
??????
??????
??????
????????????=˘????????????˘
2
≥0.) This leads to inequalities.
First of all, we have the linear programming bound for subsets of an association

24 Graphs
scheme. Consider a nonempty subset??????of??????. Itsinner distribution??????is the row vector
with entries??????
??????=
1
|??????|
??????
??????
??????????????????, where??????=??????
??????
is the characteristic vector of??????. The
value??????
??????is the average number of points of??????in relation?????? ??????to a given point of??????.
Note that??????
0=1 and|??????|=
ﬃ
??????????????????.
Theorem 1.3.4The inner distribution??????of a nonempty subset??????of??????satisﬁes
????????????≥0. Moreover,(????????????)
??????=0if and only if?????? ????????????
??????
=0.
Proof.Let??????=??????
??????
. Then
|??????|(????????????)
??????=??????
??????
ň
??????
????????????????????????????????????=????????????
??????
??????????????????=??????˘?????? ????????????˘
2
≥0. ﬃ
This theorem gives inequalities on subsets when information on their inner distri-
bution is given. For example, letΓbe the graph(??????, ??????
??????)deﬁned by relation?????? ??????in
an association scheme. Let it have valency??????(namely,??????
??????) and smallest eigenvalue??????
(namely, some??????
????????????) with??????>0. A clique??????of size??????inΓhas inner distribution??????
with??????
0=1,?????? ??????=??????−1 and?????? ℎ=0forℎ≠0,??????. The inequality(????????????) ??????≥0 yields
1+
??????
??????
(??????−1)≥0, that is,??????≤1+
??????
??????
. For strongly regular graphs this is the Hoﬀman
bound on cliques.
One can also give results for pairs of subsets. First a lemma.
Lemma 1.3.5(Roos[630])For any vectors??????, ??????∈R
??????
, we have
??????ň
??????=0
??????
??????
??????????????????
??????????????????
????????????=
??????ň
??????=0
??????
??????
??????????????????
????????????
????????????.
Proof.
ň
??????
??????
??????
??????????????????
??????????????????
????????????=
ň
??????, ??????
??????
??????
????????????????????????????????????
??????????????????
????????????=
ň
??????, ??????
??????
??????
????????????????????????????????????
??????????????????
????????????=
ň
??????
??????
??????
??????????????????
????????????
????????????.ﬃ
Let??????⊆{1,...,??????}. A nonempty subset??????of??????with characteristic vector??????and
inner distribution??????is called a??????-codewhen??????
??????=0 for all??????∈??????. It is called a??????-
anticodewhen??????
??????=0 for all??????∈{1,...,??????}\??????. It is called a??????-designwhen?????? ????????????=0
for all??????∈??????. It is called a??????-antidesignwhen??????
????????????=0 for all??????∈{1,...,??????}\??????.
Theorem 1.3.6Let??????be a??????-design and??????a??????-antidesign in??????, where??????⊆
{1,...,??????}. Then|??????∩??????|=|??????|·|??????|/??????.
Proof.Let??????and??????have characteristic vectors??????and??????. Then
????????????
??????
??????????????????=??????
ň
??????
????????????????????????
??????
??????????????????=????????????|??????|·|??????|.
The theorem is the special case??????=0. ﬃ
Theorem 1.3.7Let??????be a??????-code and??????a??????-anticode in??????, where??????⊆{1,...,??????}.
Then|??????|·|??????|≤??????. When equality holds,|??????∩??????|=1.

1.3 Association schemes and coherent conﬁgurations25
Proof.Let??????and??????be the characteristic vectors of??????and??????, respectively. Apply
Roos’ lemma with??????=??????=??????, and pre- and post-multiply by??????
??????
and??????to ﬁnd
ﬀ
??????
1
????????????
(??????
??????
??????????????????)(??????
??????
??????????????????)=??????
ﬀ
??????
1
????????????
(??????
??????
??????????????????)(??????
??????
??????????????????). The only nonzero term on the
left-hand side is that for??????=0, which is|??????|·|??????|. The right-hand side is bounded
below by the term for??????=0, which is
1
??????
|??????|
2
|??????|
2
. When equality holds,??????and??????
are an??????-design and??????-antidesign for some??????⊆{1,...,??????}, and the previous theorem
yields the desired conclusion. ﬀ
For example, if in a strongly regular graph a clique and a coclique both meet the
Hoﬀman bound, then they meet in a single point (see also Proposition 1.1.7(iii)).
History
The linear programming bound is due toDelsarte[276].
1.3.4 Krein parameters
The Bose-Mesner algebraAis not only closed under ordinary matrix multiplication,
but also under componentwise (Hadamard, Schur) multiplication (denoted◦). Clearly
{??????
0,...,????????????}is the basis of minimal idempotents with respect to this multiplication.
Write
??????
??????◦????????????=
1
??????
??????ň
??????=0
??????
??????
????????????
????????????.
The numbers??????
??????
????????????
thus deﬁned are called theKrein parameters.
Proposition 1.3.8The Krein parameters of an association scheme satisfy
(i)??????
??????
0??????
=??????????????????,??????
0
????????????
=??????????????????????????????,??????
??????
????????????
=??????
??????
????????????
,
(ii)
ﬀ
????????????
??????
????????????
=????????????,
ﬀ
??????????????????=??????,
(iii)??????
??????
????????????
????????????=??????
??????
????????????
????????????,
(iv)
ﬀ
????????????
??????
????????????
??????
??????
????????????
=
ﬀ
????????????
??????
????????????
??????
??????
????????????
,
(v)??????
??????????????????????????????=
ﬀ
??????
??????=0
??????
??????
????????????
??????????????????,
(vi)????????????
????????????
??????
????????????
=
ﬀ
????????????????????????????????????????????????????????????????????????. ﬀ
The main use of the Krein parameters is the fact that they are nonnegative, and that
the scheme satisﬁes additional regularity properties when some Krein parameter is
zero.
Theorem 1.3.9(Scott[638, 639])The Krein parameters of an association scheme
satisfy??????
??????
????????????
≥0for all??????, ??????, ??????∈{0,...,??????}. ﬀ
Theorem 1.3.10([123], Theorem 2.3.2)For given??????, ??????, ??????∈{0,...,??????}one has
??????
??????
????????????
=0if and only if
ň
??????∈??????
????????????(??????, ??????)?????? ??????(??????,??????)?????? ??????(??????, ??????)=0
for all??????, ??????, ??????∈??????. ﬀ

26 Graphs
The Krein parameters can be computed by use of equation (vi) above. In the case
of a strongly regular graph we obtain
??????
1
11
=
??????
2
??????
č
1+
??????
3
??????
2
−
(??????+1)
3
(??????−??????−1)
2
ă
≥0,
??????
2
22
=
??????
2
??????
č
1+
??????
3
??????
2
−
(??????+1)
3
(??????−??????−1)
2
ă
≥0
or, equivalently (assuming??????≠??????and??????≠−1),
(??????+1)(??????+??????+2????????????)≤(??????+??????)(??????+1)
2
,
(??????+1)(??????+??????+2????????????)≤(??????+??????)(??????+1)
2
(the other Krein conditions are trivially satisﬁed in this case).
History
L. L. Scott, jr. gave the Krein conditions in the case of ﬁnite groups with abelian
centralizer algebra, and credited C. Dunkl, who in turn quotedKre˘ın[502], p. 139.
See also [422].
Smith graphs and graphs with strongly regular subconstituents
A strongly regular graph is called aSmith graphwhen??????
2
22
=0, or, equivalently, when
??????=
??????
2
(2??????+1)−??????
2
??????
(??????+1)
2
−??????−1
.
Theorem 1.3.11(Cameron,Goethals&Seidel[178])LetΓbe a strongly regular
graph with??????
1
11
=0or??????
2
22
=0. Then for each vertex??????both subconstituents of??????are
themselves strongly regular or complete or edgeless.
Proof.Given three vertices??????, ??????, ??????, let??????
??????????????????(??????, ??????, ??????)be the number of vertices??????
at distances??????, ??????, ??????from??????, ??????, ??????, respectively. When one of??????, ??????, ??????is 0, the numbers
??????
??????????????????(??????, ??????, ??????)do not depend on??????, ??????, ??????but only on their mutual distances. E.g.,
??????
????????????0(??????, ??????, ??????)=1if??????(??????, ??????)=??????and??????(??????,??????)=??????, and?????? ????????????0(??????, ??????, ??????)=0 otherwise.
We also have identities like
ﬃ
??????????????????????????????(??????, ??????, ??????)=??????
ℎ
????????????
when??????(??????, ??????)=ℎ. It follows that
all??????
??????????????????(??????, ??????, ??????)can be expressed in the single value?????? 111(??????, ??????, ??????)(given the mutual
distances of??????, ??????, ??????). Since??????
??????=
1
??????
ﬃ
??????
ℎ????????????ℎ,wehave?????? ??????(??????, ??????)=
??????ℎ????????????
if??????(??????, ??????)=ℎ.
Now by Theorem 1.3.10, if??????
1
11
=0, then
ﬃ
??????, ??????,??????????????????????????????(??????, ??????, ??????)?????? ??????1????????????1????????????1=0.
One checks that this equation is independent of the previous identities for the
??????
??????????????????(??????, ??????, ??????)
‡
, so that all values?????? ??????????????????(??????, ??????, ??????)are determined. ﬃ
For example, there is no graph with parameters(2950,891,204,297)since it would have??????
2
22
=0 but
there is no feasible parameter set on 891 vertices with valency 204 ([88]). There are various generalizations
of this theorem to distance-regular graphs of small diameter. See, e.g., [224].
‡ After eliminating the?????? ??????????????????where some index is 0, the equations are of the form
ﬃ
?????? ??????????????????????????????????????????=0 with
??????
111+??????122+??????212+??????221=??????112+??????121+??????211+??????222. But the ﬁnal equation has?????? ??????????????????=????????????1????????????1????????????1
and is of this form only when?????? 11=??????21, impossible.

1.3 Association schemes and coherent conﬁgurations27
Conversely, the authors of [178] investigated in what cases both subconstituents of
a strongly regular graph are themselves strongly regular or complete or edgeless. The
primitive strongly regular graphs in question are the Smith graphs and their comple-
ments, and possibly graphs with Latin square or negative Latin square parameters
(cf. §8.4.2).
Examples of Smith graphs are the pentagon,????????????
2,????????????,??????, the complement of the
Clebsch graph (§10.7), the complement of the Schläﬂi graph (§10.10), the Higman-
Sims graph (§10.31), the McLaughlin graph (§10.61) and both of its subconstituents
(§10.34, §10.48). An inﬁnite family of examples is that of the strongly regular
graphs with the parameters of the collinearity graph of a generalized quadrangle of
order(??????, ??????
2
). It follows that these graphs are collinearity graphs of such generalized
quadrangles ([178], Theorem 7.9).
Graphs with negative Latin square parameters NL
??????(??????
2
+3??????)are Smith graphs
(with??????=0, cf. p. 214). All further known strongly regular graphs with parameters
LS
??????(??????)or NL??????(??????)and strongly regular subconstituents are the grids??????×??????or have
parameters LS
??????(2??????)or NL ??????(2??????)(that is,(??????,??????,??????)=(4??????
2
,??????(2??????±1),??????(??????±1)). The
authors of [178] conjecture that there are no further example parameters. Examples
are the graphs
????????????
??????
2??????
(2).
1.3.5 Euclidean representation
Let(??????,R)be an association scheme with??????classes. Fix a primitive idempotent??????
of the scheme. Let??????:=rk??????. Now the map??????↦→??????that maps??????∈??????to column
??????of??????maps??????into a system of vectors inR
??????
(namely, the column space of??????)
with the property that the inner product????????????,????????????only depends on the relation??????, ??????are
in, and not on the choice of??????, ??????. Indeed, if??????=
ﬀ
??????
??????????????????, and(??????, ??????)∈?????? ??????, then
????????????,????????????=(??????
??????
??????)????????????=??????????????????=????????????, since??????
??????
=??????and??????
2
=??????. This allows one to use
Euclidean geometry to study(??????,R).
In particular we ﬁnd, after scaling, that if??????is an eigenvalue≠??????of a primitive
strongly regular graphΓof multiplicity??????, then the vertices??????ofΓhave a represen-
tation inR
??????
by unit vectors ¯??????such that??????¯??????,¯????????????=
??????
??????
if??????∼??????and??????¯??????,¯????????????=
??????−1
????????????−1
if
??????ﬀ??????.
There are many applications.
1.3.6 Subschemes
An association scheme(??????,S)is called asubscheme(orfusion scheme)ofthe
association scheme(??????,R)(withR={??????
0,...,????????????}) when each??????∈Sis the
union of a subset ofR, that is, when the partitionRof??????×??????is a reﬁnement of
S. Equivalently, when the Bose-Mesner algebra of(??????,S)is a subalgebra of the
Bose-Mesner algebra of(??????,R).
Given the??????matrix of(??????,R)one can ﬁnd all subschemes with??????classes by
considering all possible partitionsΠof{0,...,??????}into??????+1 parts, one of which is{0}.

28 Graphs
Let??????be the(??????+1)×(??????+1)(0,1)-matrix with columns indexed byΠwith entries
??????
????????????=1if??????∈??????. (Then??????has row sums 1.) The partitionΠdeﬁnes a subscheme if
and only if the(??????+1)×(??????+1)matrix????????????has precisely??????+1 distinct rows.
For example, the??????matrix of??????(13,6)is
??????
??????
??????
??????
??????
??????
??????
??????
??????
??????
1 42 315 700 525 126 7
1 29 120 50 −125−69−6
118 21 −60−15 30 5
19 −15−15 30 −6−4
12 −15 20 −5−63
1−30 10 −15 9 −2
1−615 −20 15 −61
??????
??????
??????
??????
??????
??????
??????
??????
??????
??????
and withΠ={{0},{1,2,4},{3,5,6}}one ﬁnds the??????matrix of a subscheme by
taking the rows of????????????, deleting duplicates:
??????
??????
??????
??????
1 882 833
124 −25
1−18 17
??????
??????
??????
??????
.
WithΠ={{0},{1,6},{2,5},{3,4}}one ﬁnds
??????
??????
??????
??????
??????
??????
1 49 441 1225
123 51 −75
15 −21 15
1−59 −5
??????
??????
??????
??????
??????
??????
.
Subschemes of the Johnson scheme
Trivially,??????(2??????, ??????)has the subscheme withΠ={{0},{1, −1},{??????}}, where
??????
??????has valency 1. The scheme??????(2??????+1,??????)has the subscheme withΠ={{0},{1,??????},
{2,??????−1},...,{??????
??????+1
2
??????,??????
??????+1
2
??????}}isomorphic to the folded scheme
??????(2??????+2,??????+1).
Sporadic examples are due to Mathon and Klin: the distance 1-or-3 graphs of??????(10,3)
and??????(12,4), the distance 1-or-4 graph of??????(11,4), and the distance 1-or-2-or-4 graph
of??????(13,6)are strongly regular with parameters(??????,??????,??????,??????)=(120,56,28,24),
(495,256,136,128),(330,63,24,9), and(1716,882,456,450), respectively. For
??????=3,4, the distance 1-or-??????graph of??????(2??????+1,??????)is strongly regular with parameters
(??????,?????? )=(35,16,6,8)and(126,25,8,4), respectively.
Muzychuk[579] andUchida[707] showed that??????(??????, ??????)does not have a nontrivial
subscheme for??????≥??????(??????), where??????(3)=11,??????(4)=13,??????(5)=15,??????(6)=18 and
??????(??????)=3??????−1for??????≥7.
Subschemes of distance-regular graphs of diameter 3
Proposition 1.3.12LetΓbe a distance-regular graph of diameter 3. Then
(i) the distance-2graphΓ
2ofΓis strongly regular if and only if?????? 3(??????3+??????2−??????1)=
??????
1??????2, and
(ii) the distance-3graphΓ
3ofΓis strongly regular if and only ifΓhas eigenvalue
−1, that is, if and only if??????=??????
2+??????3−1.

1.3 Association schemes and coherent conﬁgurations29
Proof.See [123], 4.2.17. ﬀ
For example, the distance-3 graph of the collinearity graph of a generalized hexagon
of order??????is strongly regular.
1.3.7 Absolute bound and??????-bound
The absolute bound
The absolute bound expresses the fact that in a Euclidean representation the dimension
cannot be too small.
Proposition 1.3.13The multiplicities??????
??????(0≤??????≤??????)of a??????-class association
scheme satisfy
ň
??????
??????
????????????
≠0
????????????≤
??????
??????
?????????????????? if??????≠??????,
1
2
????????????(????????????+1)if??????=??????.
Proof.See [123], 2.3.3. ﬀ
In particular, one ﬁnds for strongly regular graphs:
Proposition 1.3.14(Absolute bound)The multiplicities??????,??????of a primitive strongly
regular graph satisfy??????≤
1
2
??????(??????+3)and??????≤
1
2
??????(??????+3).
Proof.See [132], 10.6.8. ﬀ
Proposition 1.3.13 implies ‘if??????
1
11
≠0 then??????≤
1
2
??????(??????+1)’. It follows that if
??????=
1
2
??????(??????+3)then??????
1
11
=0 and if??????=
12
??????(??????+3)then??????
2
22
=0.
This rules out, e.g.,(??????, ??????, ??????, ??????)=(841,200,87,35)with??????=40 and??????
1
11
≠0.
The??????-bound
For primitive strongly regular graphs with smallest eigenvalue??????=−??????, the value of
??????is bounded as a function of??????.
This was ﬁrst shown by Hoﬀman who developed a structure theory for families
of graphs with lower bounded smallest eigenvalue (cf. [433, 435]). An explicit (and
sharp) bound was given by Neumaier.
Theorem 1.3.15(Neumaier[587])LetΓbe a primitive strongly regular graph
with integral smallest eigenvalue??????=−??????. Then??????≤??????
3
(2??????−3). If equality holds,
then??????=??????(??????−1)(2??????−1), where??????=??????−??????. ﬀ
This bound is proved as a consequence of the Krein condition and the absolute
bound. It does not yield new feasibility conditions. Equality holds for the Schläﬂi
graph (??????=2) and the McLaughlin graph (??????=3).

30 Graphs
Equality in Krein condition or absolute bound
With the notation from Theorem 1.3.15, the three independent parameters of a
strongly regular graph can be taken to be??????, ??????, ??????.
Proposition 1.3.16For a primitive strongly regular graph:
(i) We have??????
1
11
=0if and only if
??????=
(??????+??????
2
−??????)(??????−??????)(??????−1)
??????−??????
2
+??????
.
(ii) We have??????=
1
2
??????(??????+3)if and only if??????has the value given in (i), and
??????=??????(??????−1)(2??????−1).Now??????=??????
3
(2??????−3).
(iii) We have??????
2
22
=0if and only if
??????=
(??????+1)(??????
2
+??????)??????
??????
2
+2??????−??????
.
(iv) We have??????=
1
2
??????(??????+3)if and only if??????has the value given in (iii), and
−??????=??????
2
(2??????+3).Now??????=??????
3
(2??????+3). ﬃ
If the graph does not have integral eigenvalues, then these conditions hold if and
only if the graph is the pentagon. The graphs from (iii) are the Smith graphs.
1.3.8 Coherent conﬁgurations
Above we gave the deﬁnition of a symmetric association scheme. It is the combinato-
rial analog of the permutation group-theoretical situation of a transitive permutation
group with only self-paired orbits. More general schemes are the analogs of more
general group actions.
Coherent conﬁgurations
Consider a permutation group??????acting on a ﬁnite set??????.For??????∈??????, let??????
??????be
the permutation matrix indexed by??????with entries(??????
??????)????????????=1if??????=????????????, so that
??????
????????????ℎ=????????????ℎ. Thecentralizer algebraAof??????is the algebra consisting of the matrices
??????such that??????
????????????=???????????? ??????for all??????∈??????. A basis forAis the set of 0-1 matrices
??????
??????, where??????is a??????-orbit on??????×??????, and?????? ??????is the 0-1 matrix with(?????? ??????)????????????=1if
(??????, ??????)∈??????.
The corresponding combinatorial analog is calledcoherent conﬁguration, see
Higman[423, 424]. Thus, a coherent conﬁguration is described by a collection
of 0-1 matrices{??????
0,...,????????????}that is a basis for an algebraAsuch that (i)
ﬃ
??????????????????=??????,
(ii)??????∈A, (iii) for each??????there is a??????such that??????
??????
??????
=????????????. As before, the?????? ??????are
viewed as adjacency matrices for relations. The fact thatAis an algebra means that
??????
??????????????????=
ﬃ
??????
??????
????????????
????????????for certain constants??????
??????
????????????
.
A coherent conﬁguration is calledSchurianif it is derived from a permutation
group as above.

1.3 Association schemes and coherent conﬁgurations31
Homogeneous coherent conﬁgurations
If??????is transitive, then the diagonal of??????×??????is a single relation, so that we can take
??????
0=??????. Now dimA=??????+1istherankof the permutation action.
A coherent conﬁguration with??????
0=??????is calledhomogeneous, or also a (general)
association scheme, followingDelsarte[276].
Commutative association schemes
For transitive??????, the action of??????on??????is isomorphic to the action of??????on??????/??????(by left
multiplication), where??????=??????
??????is a point stabilizer. The algebraAis commutative
precisely when this action is multiplicity-free, that is, when all irreducible constituents
of the permutation character??????=(1
??????)
??????
are distinct (see [729], §29). Now(??????, ??????)is
aGelfand pair.
An association scheme is calledcommutativewhenAis commutative. Now??????
??????
????????????
=
??????
??????
????????????
for all??????, ??????, ??????.
Symmetric association schemes
A permutation group??????is calledgenerously transitiveif for arbitrary elements??????, ??????∈
??????there is a??????∈??????with????????????=??????and????????????=??????. This happens if and only if??????is transitive
and all its suborbits are self-paired (Neumann[591]).
An association scheme is calledsymmetricwhen??????
??????
??????
=????????????for all??????, so that??????
??????
=??????
for all??????∈A. This was the original deﬁnition of association scheme (Bose&
Shimamoto[97]). A symmetric association scheme is commutative since????????????=
(????????????)
??????
=??????
??????
??????
??????
=????????????.
Linear programming bound
Hobart[431] proved an analog of Delsarte’s linear programming bound for general
coherent conﬁgurations.
The Weisfeiler-Leman algorithm
The??????-dimensional Weisfeiler-Leman algorithm is a procedure that given a graphΓ
with vertex set??????computes a canonical partition (coloring)Πof??????
??????
.
Compute forℎ≥0 partitionsΠ
ℎof??????
??????
by successive reﬁnement. Start withΠ 0,
the partition according to the ordered isomorphism type of the??????-tuples, so that??????, ??????
are in the same part if and only if the map??????
??????↦→????????????(1≤??????≤??????) preserves identity,
adjacency and nonadjacency.
For??????∈??????
??????
and??????∈??????and 1≤??????≤??????, let??????
??????
??????
(??????)be the??????-tuple??????with?????? ??????=??????and
??????
??????=????????????for??????≠??????.Forℎ≥0 and??????∈??????
??????
, let??????ℎ(??????)be the color of??????after stepℎ, that
is, the part ofΠ
ℎcontaining??????. GivenΠ ℎ, compute the reﬁnementΠ ℎ+1by splitting
each part according to the value of the map that assigns to the??????-tuple??????the multiset
{(??????
ℎ(??????
??????
1
(??????)),...,??????ℎ(??????
??????
??????
(??????))) |??????∈??????}of??????-tuples of colors of neighboring??????-tuples.
Repeat this step until no further splitting occurs. PutΠ=Π
ℎwhenΠ ℎ=Πℎ+1.

Another Random Document on
Scribd Without Any Related Topics

käsiäni, ei syleilemästä minua eikä katselemasta minua suuret silmät
kyynelissä. Sitten hän alkoi puhua äidistä, noista kahdesta
tuhannesta francista, Roberte'istaan, Camille'istaan, ja
Anastagille'istaan niin laveasti ja perinpohjaisesti, että olisimme
vieläkin — niinkuin on tapana sanoa — alhaalla puotissa häntä
kuuntelemassa, ellei Jacques olisi tokaissut kärsimättömällä äänellä:
»Entä kassanne, Pierrotte!»
Pierrotte vaikeni kuin naulaan. Hän oli hieman häpeissään paljosta
puhelustaan ja sanoi:
— Olette oikeassa, Jacques herra, minä vaan lörpöttelen … ja
tytön typykkä … niinkuin on tapana sanoa, tytön typykkä antaa
minulle kyytiä, kun viivyn täällä näin kauvan.
— Onko Camille tuolla ylhäällä? kysyi Jacques välinpitämättömällä
äänellä.
— On … on kyllä, Jacques herra … pikku typykkä on ylhäällä… Hän
halajaa … niinkuin on tapana sanoa… Hän halajaa koko sydämestään
tutustua Daniel herraan. Menkää siis kaikin mokomin häntä
tervehtimään … minä lasken vain kassani ja tulen heti perässä …
niinkuin on tapana sanoa.
Jäämättä enempää kuuntelemaan Jacques tarttui käsivarteeni ja
vei minua aika vauhtia puotin perälle sinne päin, mistä kuului huilun
soitto… Pierrotte'in puoti oli suuri ja hyvin varustettu.
Puolihämärässä saattoi erottaa kimaltelevat karahviinien kyljet,
himmeäksi hiotut lampunkuvut, suuret kristallimaljakot, upeat
böömiläislasit ja pulleat liemimaljat, ja kahden puolen suuret
lautaspinot, jotka ulottuvat kattoon saakka. Porsliinihaltijan palatsi
öiseen aikaan. Puotikamarissa oli puoleksi aukiväännetty kaasuliekki

vielä valveilla näyttäen ikävystyneenä kielensä kärkeä… Me
menimme kiireesti huoneen läpi. Siellä istui makuusohvan reunalla
kookas, vaalea nuorukainen, joka puhalsi surumielisiä säveleitä
huilustaan. Sivumennessään sanoi Jacques »hyvää iltaa», hyvin
kuivalla äänellä, johon vaalea mies vastasi kahdella myöskin hyvin
kuivalla puhalluksella huilustaan, jolla tavalla varmaankin kaksi
huilua, jotka ovat toisilleen vihoissaan, sanovat hyvää iltaa.
— Se oli puotipalvelija, sanoi Jacques, kun tulimme rappusille…
Tuo vaalea jätkä voi ottaa hengen ihmisestä ijankaikkisella
huiluttamisellaan… Pidätkö sinä huilun soitosta. Daniel?
Olisin kernaasti kysynyt: »Entä pitääkö pikku typykkä siitä?» Mutta
pelkäsin hänen pahastuvan ja vastasin hyvin vakavasti: »En,
Jacques, minä en pidä huilunsoitosta.»
Pierrotte'in huoneisto oli neljännessä kerroksessa samassa talossa
kuin puotikin. Camille neiti oli liian ylimyksellinen näyttäytyäkseen
puotin puolella, hän pysyi ylhäällä eikä tavannut isäänsä muuta kuin
ruoka-aikoina. »Saatpa nähdä!» sanoi Jacques rappuja ylös
noustessamme, »täällä eletään niinkuin hienossa talossa ainakin.
Camille'illa on seuranainen, eräs leskirouva Fribou, joka on aina
hänen mukanaan… En tiedä, mikä tämä rouva Fribou alkujaan on,
mutta Pierrotte tuntee hänet ja väittää, että hän on aivan
erinomainen nainen… Soita, Daniel, olemme perillä!» Minä soitin;
cévenniläistyttö, jolla oli korkea päähine, tuli avaamaan, hymyili
Jacques'ille kuin vanhalle tuttavalle ja vei meidät saliin.
Kun astuimme sisään, istui neiti Pierrotte pianon ääressä. Kaksi
vanhaa, lihavahkoa naista, rouva Lalouette ja rouva Fribou,
erinomainen nainen, istuivat ja pelasivat korttia yhdessä huoneen
nurkassa. Meidät nähdessään nousivat kaikki ylös. Syntyi hetkeksi

hälinää ja kolinaa; sitten kun oli tervehditty ja esittelemiset
suoritetut, Jacques pyysi Camille'in — hän kutsui häntä aivan
yksinkertaisesti Camille'ksi — istumaan jälleen pianon ääreen, jolloin
erinomainen nainen sai tilaisuuden jatkaa peliänsä rouva Lalouette'in
kanssa. Jacques ja minä olimme käyneet istumaan neiti Pierrotte'in
kahden puolen, joka puheli ja nauroi kanssamme samalla kun hänen
pikku sormensa liukuivat pianon koskettimilla. Katselin häntä, kun
hän puhui. Hän ei ollut kaunis. Valkoinen ja punainen, pienet korvat,
kaunis tukka, mutta posket olivat liian pulleat, liian hyvänvoivan
näköiset; lisäksi oli hänellä vielä punaiset kädet ja hiukan kulmikkaat
liikkeet, niinkuin lomalla olevalla koulutytöllä. Hän oli todellinen
Pierrotte'in tytär, vuoristokukka, joka oli kasvanut Saumon'in
kauppakujan lasikaapissa.
Sellainen oli ainakin ensi vaikutelmani hänestä; mutta yhtäkkiä,
kun sanoin jotain, neiti Pierrotte, joka tähän asti oli pitänyt silmiään
alasluotuina, nosti ne hitaasti ylös katsoen minuun, ja ikäänkuin
taikavoimasta pieni porvaristyttö katosi. En nähnyt muuta kuin
hänen silmänsä, kaksi suurta, häikäisevää silmää, jotka heti tunsin…
Ihmeitten ihme! Nehän olivat nuo samat mustat silmät, jotka
olivat minulle niin lempeästi loistaneet vanhan lyseon kolkkojen
muurien sisällä, lasisilmänoidan mustat silmät, sanalla sanoen:
mustat silmät… Luulin näkeväni unta. Olisin tahtonut huutaa niille:
»Kauniit mustat silmät, tekö täällä? Tapaanko teidät jälleen toisissa
kasvoissa?» Ja kuinka ne olivat aivan ne! Oli aivan mahdoton niissä
erehtyä. Samat ripset, sama loisto, sama tumma, hillitty tuli. Olisi
ollut hulluutta ajatellakaan, että maailmassa oli kaksi paria noita
silmiä! Ja parhaana todistuksena siitä, että ne olivat mustat silmät
itse eivätkä mitkään niiden näköiset mustat silmät, on se, että nekin
olivat tunteneet minut, ja me olisimme varmaankin taasen

aloittaneet tuommoisen entisen, mykän keskustelumme, kun kuulin
aivan lähelläni, melkein korvani juuressa, hiiren nakerrusta. Tämän
äänen kuullessani käänsin päätäni ja näin nojatuolissa pianon
nurkassa henkilön, jota en ollut tähän asti huomannut… Näin pitkän,
kuivan, kalpean vanhuksen, jolla oli linnun pää, taaksepäinluisuva
otsa, terävä nenä, pyöreät, elottomat silmät, jotka olivat liian
kaukana toisistaan melkein ohimoissa… Ellei olisi nähnyt
sokuripalasta, jota mies piti kädessään ja silloin tällöin nakerteli, olisi
voinut luulla hänen nukkuvan. Hämilläni tein syvän kumarruksen
tuon vanhan variksen edessä, mutta hän ei vastannut… »Ei hän näe
sinua», sanoi Jacques, »se on sokea herra Lalouette…»
Jottei minun enää tarvinnut nähdä tuota kauheata
linnunpäävanhusta, käännyin joutuun mustain silmäin puoleen;
mutta voi, lumous oli särkynyt, mustat silmät olivat kadonneet.
Heidän sijassaan oli vain pieni porvaristyttö, joka istui selkäkenossa
pianotuolillaan…
Samassa salin ovi aukeni, ja Pierrotte tuli touhuten sisään. Häntä
seurasi huilunpuhaltaja huilu kainalossa. Hänet nähdessään linkosi
Jacques häneen niin musertavan katseen, että se olisi voinut vaikka
puhvelihärän surmata; mutta luultavasti ei se osunut, sillä
huilunpuhaltaja ei ollut tietävinään.
— No typykkäni! sanoi cévenniläinen suudellen tytärtään
kummallekin poskelle, oletko nyt tyytyväinen? Nyt olet saanut
Danielisi… Mitä pidät hänestä? Eikö hän ole kaunis? Niinkuin on
tapana sanoa … aivan Neidin ilmi elävä kuva.
Ja nyt Pierrotte aloitti saman kohtauksen kuin alhaalla puotissa
alusta ja vei minut väkisin keskelle huonetta, että jokainen voisi
nähdä neidin silmät … neidin nenän, neidin kuoppaleuvan… Tämä

näytteillepano oli hirveä… Rouva Lalouette ja erinomainen nainen
keskeyttivät pelinsä ja ottaen oikein mukavan asennon
nojatuolissaan, tarkastelivat minua mitä kylmäverisimmin,
arvostellen tai kehuen kovalla äänellä milloin mitäkin palasta
minusta, aivan kuin olisin ollut torilla myytävä kananpoika. Meidän
kesken puhuen, näytti »erinomainen nainen» olevan jokseenkin hyvä
kananpoikain tuntija.
Onneksi teki Jacques lopun piinastani pyytämällä neiti Pierrotte'a
soittamaan jotain. »Niin juuri, soittakaamme jotakin», sanoi
huilunpuhaltaja innokkaasti, törmäten esiin huilu koholla. Mutta
Jacques kirkui: »Ei … ei … ei mitään duo'a eikä huilua!» Silloin
huilunsoittaja linkosi häneen nopean, vaaleansinisen katseen, joka
oli myrkyllinen kuin intiaanien nuolet, mutta toinen ei hievahduttanut
haiventakaan, huusi vain edelleen: »Ei huilua!…» Lopuksi Jacques
pääsi voitolle, ja neiti Pierrotte soitti meille ilman huilun
pihaustakaan yhden noista tunnetuista tremoloista, joita kutsutaan
Rosellen'in Haavelmiksi… Hänen soittaessaan itki Pierrotte
ihastuksesta, Jacques oli haltioissaan; hiljaisena kuin huilu
hampaissa löi huilunpuhaltaja olkapäillään tahtia ja puhalsi sisällisesti
huiluaan.
Kun Haavelma oli lopussa, kääntyi neiti Pierrotte minun puoleeni:
»Entä te, Daniel herra», sanoi hän luoden silmänsä alas, »emmekö
saa kuulla mitään teiltä? Tiedän, että olette runoilija.»
— Ja hyvä runoilija, tokasi Jacques, tuo hirveä Jacques… Minulla ei
juuri puolestani ollut halua lausua runojani noille amaleekkiläisille.
Jospa edes mustat silmät olisivat olleet saapuvilla. Mutta ei, ne olivat
olleet jo pitkän ajan sammuksissa: etsin niitä turhaan ympäriltäni…

Olisittepa ollut vain kuulemassa, millä huolettomalla äänellä vastasin
neiti Pierrotte'ille:
— Antakaa anteeksi, neiti, en ottanut tänä iltana lyyryä mukaani.
— Muistakaa tuoda se ensi kerralla, sanoi tuo kunnon Pierrotte,
joka ymmärsi minun kuvakieleni puustavillisesti. Mies rukka luuli
aivan tosissaan, että minulla oli lyyry ja että soitin sitä aivan kuin
hänen puotipalvelijansa soitti huiluaan… Aah, olihan Jacques tehnyt
minulle selväksi, minkälaiseen maailmaan hän minut vei!
Yhdentoista aikaan tarjottiin teetä. Neiti Pierrotte kulki
edestakaisin huoneessa tarjoten sokeria ja kaadellen kermaa,
hymyhuulin, pikkusormi kohollaan. Tähän aikaan illasta näin mustat
silmät uudelleen. Ne ilmestyivät yhtäkkiä eteeni loistavina ja
lempeinä, sitten taasen katosivat, ennenkuin ehdin niille mitään
sanoa… Mutta juuri silloin huomasin erään seikan, sen nimittäin, että
neiti Pierrotte'issa oli kaksi aivan erillaista olentoa: toinen
leveäjakauksinen neiti Pierrotte, porvaristyttö, joka oli aivan omiansa
hallitsemaan entisessä Lalouette'in kaupassa, ja sitten mustat silmät,
nuo suuret runolliset silmät, jotka aukesivat kuin pari
samettikukkasta ja ilmestyessään muuttivat koko tuon naurettavan
romukauppaympäristön toiseksi. Neiti Pierrotte'ista en olisi mistään
hinnasta välittänyt; mutta mustat silmät … ah, nuo mustat silmät!…
Vihdoin tuli lähdön hetki. Rouva Lalouette antoi siihen merkin. Hän
kietoi miehensä suureen huiviin ja vei hänet ulos kainalossaan,
niinkuin vanhan kääreisiin kiedotun muumion. Pierrotte pidätti meitä
loppumattomalla sanatulvallaan vielä kauvan rappusissa: »No, nyt
kai näemme teidät täällä usein, Daniel herra, kun olette kerran tien
löytänyt. Meillä ei ole milloinkaan paljon vieraita, vain valittu seura …
niinkuin on tapana sanoa… Ensinnäkin herra ja rouva Lalouette,

entinen isäntäväkeni; ja sitte, rouva Fribou, erinomainen nainen,
jonka kanssa voitte jutella ja sitte, puotiapulaiseni, kunnon poika,
joka toisinaan soittaa meille huilua … niinkuin on tapana sanoa… Te
voitte soittaa yhdessä… Se olisi oikein hauskaa.»
Huomautin kainosti, että minulla oli paljon työtä, niin etten ehkä
voinut tulla niin usein, kuin olisin tahtonut.
Sekös häntä nauratti.
— Vai paljon työtä, Daniel herra… Kyllä ne teikäläisten työt
tunnetaan, ne Quartier Latin'in hommat … niinkuin on tapana sanoa
… siellä mahtaa olla joku viehättäjätär.
— Eipä todellakaan, sanoi nyt Jacques nauraen, neiti Valkea Käki
ole ilman viehätystään.
Nytkös Pierrotte yltyi nauramaan:
— Kuinka te sanoitte, Jacques herra… Valkea Käki … ha, ha, ha,—
katsokaapas tuota veitikkaa … hänen ijällään… Hän vaikeni äkkiä,
kun huomasi tyttärensä kuuntelevan, mutta vielä rappusten
alapäässä kuulimme hänen naurun hohotuksensa, joka pani
rappuset tärisemään.
— No mitä pidät heistä? sanoi Jacques, ulos päästyämme.
— Pierrotte itse on kamala, mutta neiti Pierrotte on viehättävä.
— Eikös ole? sanoi rakastunut raukka niin innoissaan, etten voinut
olla nauramatta.

— Nytpä tuli salaisuus ilmi, Jacques, sanoin minä puristaen hänen
kättään.
Sinä iltana kävelimme hyvin myöhäiseen joen rantaa. Allamme
helmeili hiljainen, tumma joki tuhansina tähtinä. Suurten alusten
touvit natisivat. Suloista oli kävellä hiljalleen hämärissä ja kuulla
Jacques'n puhuvan rakkaudesta… Hän rakasti, koko sydämellään,
mutta hän ei saanut vastarakkautta, sen hän tiesi.
— Hän rakastaa siis toista, Jacques.
— Ei. rakas Daniel, luulen, ettei hän ennen tätä iltaa vielä ole
rakastanut ketään muuta.
— Ennen tätä iltaa! Mitä sinä sillä tarkoitat, Jacques?
— Sitä, että kaikki pitävät sinusta, Daniel … voisihan siis hänkin
pitää sinusta!
Rakas Jacques parka! Olisitte nähneet millä surullisella
kohtaloonsa alistuvalla ilmeellä hän sen sanoi. Rauhoittaakseni
häntä, remahdin kovaan nauruun, kovempaan kuin aijoinkaan.
— Voi veikkonen, kylläpä sinä teet nopeaan johtopäätöksiä…
Kylläpä minä olisin vastustamaton tai neiti Pierrotte helposti syttyvää
laatua… Joutavia, rakas Jacques äiti. Neiti Pierrotte on yhtä kaukana
minun ajatuksistani, kuin minä hänen. Minua ei sinun tarvitse
vähintäkään peljätä, usko se. Sanoin sen aivan rehellisestä
sydämestä. Neiti Pierrotte oli minulle aivan yhdentekevä… Mutta
mustat silmät olivat toista.

VII.
PUNAINEN RUUSU JA MUSTAT SILMÄT.
Ensimmäisen käyntini jälestä entisessä Lalouette'ien
kauppahuoneessa, en sinne pitkään aikaan palannut. Jacques sen
sijaan teki uskollisesti joka sunnuntaisen pyhiinvaellusretkensä ja
keksi joka kerta uuden viettelevän kaulaliinasolmun… Jacques'in
kaulahuivi oli kokonainen runoelma, hillityn, palavan rakkauden
hymni, tuollainen itämainen selam, se on syvämerkityksellisistä
kukista koottu kukkavihko, joita ylhäiset turkkilaiset antavat
lemmityilleen, tulkitakseen heille rakkautensa kaikki vivahdukset.
Jos minä olisin ollut nainen, olisi Jacques'in kaulahuivi tuhansine
solmuineen, joita hän vaihteli loppumattomiin, liikuttanut minua
enemmän kuin kaikki rakkaudentunnustukset… Mutta eiväthän
naiset semmoisista mitään ymmärrä, hyvät ystävät… Joka sunnuntai,
ennen kotoalähtöään, rakastaja raukka ei voinut olla kysymättä:
»Minä menen sinne, Daniel … tuletko mukaan?» Ja minä vastasin
aina samalla tavalla: »En, Jacques, jään tekemään työtä…» Silloin
hän lähti nopeasti, ja minä jäin yksin, aivan yksin runopöytäni
ääreen.

Olin puolestani päättänyt, vakavasti päättänyt, etten enää menisi
Pierrotte'ien luo. Mustat silmät peloittivat minua. Sanoin itsekseni:
»Jos näet ne vielä kerran, niin olet hukassa», ja minusta oli parasta
olla niitä näkemättä … toisin sanoen, en saanut niitä enää pois
päästäni, noita suuria, mustia, noiduttuja silmiä. Näin ne kaikkialla.
Ajattelin vain niitä niin nukkuessani kuin valvoessanikin. Kaikkiin
vihkoihini oli piirustettu suuria mustia silmiä tuon pituisine ripsineen.
Olin aivan lumottu.
Ah, kun Jacques loistavin silmin ja kepeänä lähti Saumon'in
kauppakujaan, kaulahuivi syvämerkityksellisessä solmussa, tunsin
hurjaa halua harpata alas portaita hänen jäljessään ja huutaa
hänelle: »Odota minua!» Mutta en tehnyt sitä. Jokin ääni sisälläni
varoitti minua sinne menemästä, ja minulla oli kuin olikin lujuutta
pysyä pöytäni ääressä … ja sanoa: »Ei, kiitos, Jacques, jään
tekemään työtä.»
Näin kului jonkun verran aikaa. Ajan pitkään olisi minun
varmaankin Runottaren avulla onnistunut karkoittaa mustat silmät
mielestäni. Pahaksi onneksi olin niin varomaton, että menin niitä
vielä kerran katsomaan. Ja silloin minun kävi hullusti: kadotin niin
sydämeni kuin päänikin. Se tapahtui näin:
Sitten kun Jacques joen rannalla oli avannut sydämensä minulle, ei
hän enää ollut puhunut sen enempää rakkaudestaan; mutta minä
näin kyllä, etteivät asiat käyneet hänen mielensä mukaan… Kun hän
sunnuntaisin palasi Pierrotte'ien luota, oli hän aina alakuloinen. Öisin
kuulin hänen huokailevan, yhä huokailevan… Jos kysyin häneltä:
»Mikä sinun on, Jacques?» niin hän vastasi minulle hätäisesti: »Ei
mikään.» Mutta minä ymmärsin, että jokin häntä vaivasi vain
äänestä, jolla hän sen sanoi. Hän, joka muuten oli niin hyvä ja

kärsivällinen, antoi minun joskus tuntea pahoja tuuliaan. Toisinaan
katseli hän minua aivan kuin olisi ollut vihainen minulle. Arvasin
tietenkin että kaiken tuon alla piili joku suuri sydänsuru, mutta kun
Jacques itsepäisesti vaikeni, niin en uskaltanut minäkään siitä puhua
mitään. Mutta eräänä sunnuntaina, kun hän tuli kotiin tavallista
alakuloisempana, tahdoin ottaa selvän asiasta.
— Kas niin, Jacques, mikä sinun on? kysyin tarttuen häntä käsiin…
Asiat eivät siis siellä luonnista?
— Ei, ne eivät luonnista … sanoi poika raukka masentuneena.
— No, mutta mikä siinä sitten on? Onko Pierrotte ehkä huomannut
jotain?
Paneeko hän esteitä teidän rakkaudellenne…?
— Ooh, ei suinkaan, Pierrotte ei ole meille esteeksi… Mutta Camille
ei rakasta minua eikä tule milloinkaan rakastamaan.
— Hullutuksia, Jacques! Mistä sinä voit tietää, ettei hän tule sinua
milloinkaan rakastamaan… Oletko edes sanonut hänelle, että
rakastat häntä?… Et, et tietenkään?… No! mutta siinä tapauksessa…
— Se, jota hän rakastaa, ei ole sanonut mitään, hänen ei ole
tarvinnut sanoa mitään ollakseen rakastettu…
— Luuletko todellakin, Jacques, että huilunsoittaja…?
Jacques ei näyttänyt kuulleen minun kysymystäni.
— Se, jota hän rakastaa, ei ole sanonut mitään, sanoi hän
toistamiseen.

Ja muuta en saanut tietää. Sinä yönä ei Saint-Germain'in
kellotornissa paljoakaan nukuttu.
Jacques vietti melkein koko yönsä akkunan ääressä ja katseli
huokaellen tähtitaivasta. Minä mietin. »Menisinkö sinne katsomaan
asioita lähempää… Voihan Jacques erehtyä. Neiti Pierrotte ei ole
varmaankaan ymmärtänyt sitä rakkauden ylenpalttisuutta, mikä
piilee kaulahuivin laskoksissa… Koska ei Jacques uskalla puhua
rakkaudestaan, niin ehkä olisi hyvä, jos minä puhuisin hänen
puolestaan… Juuri niin, se on päätetty, minä menen sinne ja puhun
tuolle pikku Philistine'ille Jacques'in puolesta ja sitten saamme
nähdä.»
Seuraavana päivänä panin Jacques'ille mitään sanomatta kauniin
päätökseni täytäntöön. Jumala on todistajani, ettei minulla sinne
mennessäni ollut pienintäkään itsekästä ajatusta. Menin sinne
Jacques'in takia, yksinomaan Jacques'in takia. Mutta kun Saumon'in
kauppakujan kulmassa näin entisen Lalouette'in kauppahuoneen
vihreine laudotuksineen ja Porsliini- ja kristallikyltteineen, tunsin
lievää sydämen tykytystä, jonka olisi pitänyt olla minulle
varoituksena… Astuin sisään. Puoti oli tyhjä. Huilunsoittaja oli
puotikamarissa syömähommissa; syödessäänkin oli hänellä huilu
vieressään pöydällä. »On aivan mahdotonta, että Camille olisi
epätietoinen tuon vaeltavan huilun ja minun Jacques äitini välillä»,
vakuuttelin itsekseni noustessani portaita ylös. »No saammehan
nähdä…»
Tapasin Pierrotte'in ruokapöydässä tyttärensä ja erinomaisen
naisen seurassa. Mustat silmät eivät kaikeksi onneksi olleet
saapuvilla. Kun astuin sisään, tervehdittiin minua hämmästyksen
huudoilla. »Tuossa hän nyt vihdoinkin on!» huudahti kunnon

Pierrotte jymyäänellään. »Niinkuin on tapana sanoa, hän tulee
paraiksi kahville.» Minulle tehtiin sijaa pöydässä. Erinomainen nainen
kävi hakemassa minulle kauniin kultareunaisen kahvikupin, ja minä
istuin neiti Pierrotte'in viereen.
Neiti Pierrotte oli sinä päivänä hyvin sievä. Hän oli pistänyt juuri
korvansa yläpuolelle — nykyään ei niitä enää pidetä siinä paikassa,
— pienen punaisen ruusun, niin, niin punaisen… Luulenpa, että tuo
punainen pikku ruusu oli noiduttu, kun se saattoi tehdä tuon pikku
korvanipukan niin sieväksi. »Vai niin. Daniel herra», sanoi Pierrotte
nauraen leveätä hyväntahtoista nauruaan; »te olette rikkonut välit
ettekä aijo tulla enää meitä tervehtimään!…» Koitin pyydellä anteeksi
ja puhua kirjallisista töistäni. »Niin, niin kyllä, minä tunnen Quartier
Latin'in!» kiusoitteli Pierrotte. Ja hän alkoi nauraa täyttä kurkkua
heittäen syrjäkatseita erinomaiseen naiseen, joka yski
merkitseväisesti ja polki minua jalalle pöydän alla. Näiden kunnon
ihmisten mielestä Quartier Latin merkitsi öillisiä hurjia kemuja,
viuluineen, naamioineen, raketteineen, särjettyine astioineen, ja ties
mitä. Ah, jos minä olisin kertonut heille erakkoelämästäni Saint-
Germain'in kellotornissa, niin kylläpä he olisivat hämmästyneet.
Mutta niinkuin tiedätte, nuorena ei ole lainkaan pahoillaan, jos
saakin hurjastelijan maineen. Pierrotte'in syytöksiä kuullessani koetin
näyttää varsin kainolta ja puolustauduin vain heikonlaisesti: »Ei
suinkaan, ei suinkaan, minä vakuutan … ei siinä ole mitään perää.»
Kylläpä Jacques olisi nauranut, jos olisi kuullut.
Juuri kun olimme juoneet kahvin, kuului pihalta pieni
huilunpuhallus. Se oli merkki, että Pierrotte'in oli mentävä puotiin.
Tuskin oli hän selkänsä kääntänyt, kun erinomainen nainen
vuorostaan meni kyökkiin pelaamaan korttia kyökkipiian kanssa.

Meidän kesken puhuen luulen puolestani, että erinomaisen naisen
ainoa erinomaisuus oli se, että hän osasi hyvin sekoittaa kortit.
Nähdessäni, että minut jätettiin yksin pienen punaisen ruusun
kanssa, ajattelin: »Nyt on otollinen hetki!» Ja Jacques'in nimi oli jo
huulillani, mutta neiti Pierrotte ei antanut minulle suun vuoroa, vaan
sanoi yhtäkkiä matalalla äänellä minuun katsomatta:
— Neiti Valkea Käkikö estää teidät tulemasta ystäviänne
tervehtimään?
Luulin ensin, että hän laski leikkiä, mutta ei, hän oli ihan tosissaan.
Näyttipä hän vielä varsin liikutetultakin, poskien heleästä punasta ja
povensa nopeasta kohonnasta päättäen. Hänen aikanaan oli
varmaankin puhuttu Valkeasta Käestä, ja hän luulotteli itselleen
aivan olemattomia. Olisin yhdellä ainoalla sanalla voinut valaista
hänelle asian, mutta en voi käsittää, mikä typerä turhamaisuus minut
siitä esti. Nähdessään, etten hänelle mitään vastannut, neiti Pierrotte
kääntyi minuun päin ja kohottaen pitkät silmäripsensä, jotka hän
tähän asti oli pitänyt alasluotuina, hän katsoi minuun… Ei, nyt en
puhu totta. Hän ei katsonut minuun, vaan mustat silmät, täynnä
kyyneleitä ja helliä nuhteita. Ah! rakkaat mustat silmät, sydämeni
sulo!
Se oli vain hetken ilmestys. Pitkät ripset painuivat melkein heti
paikalla alas, mustat silmät katosivat ja minun rinnallani oli vain neiti
Pierrotte. Joutuun, joutuun, odottamatta uutta ilmestystä, minä aloin
puhua Jacques'ista. Aloitin kertomalla, kuinka hyvä, kuinka
uskollinen, kuinka kunnollinen ja epäitsekäs hän oli. Minä kerroin
hänen ehtymättömästä rakkaudestaan, hänen hellästä
äidillisyydestään, jota moni oikea äiti olisi voinut häneltä kadehtia.
Jacques elätti minut, piti minut vaatteissa, hankki meidän

toimeentulomme, ties millä raatamisella ja uhrauksilla. Ilman häntä
olisin vielä ollut tuossa Sanlande'in synkässä vankilassa, jossa olin
niin hirveästi kärsinyt…
Tullessani tähän kohtaan kertomuksestani, neiti Pierrotte näytti
liikutetulta, ja minä näin suuren kyyneleen vierähtävän hänen
poskelleen. Luulin yksinkertaisuudessani, että se oli Jacques'in
tähden ja sanoin itsekseni: »Tämäpä alkaa käydä hyvin!» ja tulin
yhä kaunopuheisemmaksi. Kerroin Jacques'in alakuloisuudesta ja
tuosta syvästä, salaisesta rakkaudesta, joka kalvoi hänen sydäntään.
Ah! tuhatkertaa onnellinen se nainen, joka…
Tässä kohden se punainen pikku ruusu, joka oli neiti Pierrotte'in
tukassa, irtausi, en tiedä mitenkä, ja putosi jalkaini juureen. Juuri
silloin tuumin, miten hienolla tavalla voisin saada Camille'in
ymmärtämään, että hän oli se tuhansin kerroin onnellinen nainen,
johon Jacques oli ihastunut. Tuo pieni punainen ruusu tuli minulle
putoamisellaan avuksi. Johan olen teille sanonut, että tuo punainen
pikku ruusu oli noiduttu. — Otin sen hitaasti ylös, mutta en
antanutkaan sitä takaisin. »Annan sen Jacques'ille teidän
puolestanne», sanoin neiti Pierrotte'ille ymmärtäväisesti hymyillen.
— »Jacques'ille, jos tahdotte!» vastasi neitï Pierrotte huokaisten.
Mutta samassa hetkessä ilmestyivät mustat silmät ja katsoivat
minuun niin hellästi, ikäänkuin tahtoen sanoa: »Ei Jacques'ille, vaan
sinulle itsellesi!» Ja olisittepa nähneet, miten ne sen sanoivat, kuinka
luottavasti, millä kainolla, vastustamattomalla rakkaudella. Mutta
minä epäröin vielä, ja niiden oli pakko toistaa pari, kolme kertaa
peräkkäin: »Niin! … juuri sinulle … juuri sinulle.»
Silloin minä suutelin pientä punaista ruusua ja pistin sen poveeni.

Sinä iltana tapasi Jacques minut kotiin tullessaan, niinkuin
tavallisesti, runopöytäni ääressä, ja minä annoin hänen olla siinä
luulossa, etten koko päivänä ollut käynyt ulkona. Pahaksi onneksi
putosi pieni, punainen ruusu riisuessani povestani lattialle sängyn
jalkoihin: noidathan ovat aina täynnä kujeita. Jacques näki sen, otti
sen maasta ja katseli sitä kauvan. En tiedä, kumpi meistä oli
punaisempi, punainen ruusu vai minä.
— Minä tunnen sen, sanoi hän, se on siitä ruusupensaasta, joka
on heidän salinsa ikkunalla.
Sitten hän lisäsi antaissaan sen minulle:
— Minulle ei hän ole milloinkaan antanut ruusuja.
Hän sanoi sen niin surullisella äänellä, että kyyneleet nousivat
silmiini.
— Jacques, rakas Jacques, minä vannon, etten ennen tätä iltaa…
Hän keskeytti minut lempeästi: »Ei mitään anteeksipyyntöjä,
Daniel. Minä tiedän varmaan, ettet ole mitenkään vilpillisesti
menetellyt. Tiesin niin varmaan, että hän rakasti sinua. Muistatko,
mitä sinulle sanoin: Se, jota hän rakastaa, ei ole sanonut mitään,
hänen ei ole tarvis sanoa mitään ollakseen rakastettu.» Ja sitten
poika parka alkoi mitellä huoneemme lattiata. Ja minä katselin häntä
äänettömänä, pitäen punaista ruusua kädessäni. »Se mikä tapahtui,
sen piti tapahtuman», jatkoi hän hetken kuluttua. »Jo aikoja sitten
aavistin, että näin piti käymän. Tiesin, ettei hän välittäisi minusta
mitään, jos näkisi sinut… Siksi en tahtonut viedä sinua pitkiin
aikoihin sinne. Olin jo edeltäpäin mustasukkainen sinulle. Anna
anteeksi, olin niin kovin rakastunut häneen!… Mutta eräänä päivänä

halusin tehdä kokeen ja otin sinut mukaani. Sinä iltana minulle
selvisi, ettei minulla ollut pienintäkään toivoa. Tuskin oli kulunut viisi
minuuttia, kun hän jo katsoi sinuun, niinkuin en ollut nähnyt hänen
katsovan kehenkään muuhun. Kyllä sinäkin sen huomasit. Oh
myönnä vain, sinä huomasit sen. Sentähden pysyit sieltä poissa
enemmän kuin kuukauden, mutta se ei minua auttanut…
Hänenlaisensa olennot eivät unohda poissaolevia, päinvastoin. Joka
kerta kun menin sinne, hän ei puhunut muusta kuin sinusta, ja niin
teeskentelemättä, niin luottavaisesti ja hellästi… Se oli minulle
todellinen piina. Nyt se on ohi… Ja se on parempi.»
Näin puhui Jacques kauvan yhtä lempeästi ja samalla kohtaloonsa
alistuvalla hymyllä. Kaikki, mitä hän sanoi, tuotti minulle samalla
sekä tuskaa että riemua. Tuskaa, koska näin, että hän oli onneton;
riemua, koska jokaisen hänen sanansa takaa näin mustien silmien
loistavan minulle, ajattelevan vain minua. Kun hän oli lopettanut,
menin hänen luoksensa hiukan häpeilläni, mutta panematta pois
punaista ruusuani ja sanoin: »Etkö sinä tästälähin enää pidä
minusta?» Hän hymyili ja puristi minua rintaansa vasten, sanoen:
»Elä puhu joutavia, minä pidän sinusta vielä enemmän.»
Ja se oli totta, punainen ruusu ei tuottanut mitään muutosta
Jacques äidin hellyydessä minua kohtaan, eipä edes saattanut häntä
huonolle tuulelle. Luulen, että hän kärsi kovin, mutta hän ei antanut
sitä milloinkaan huomata. Ei huokausta, ei valitusta, ei niin mitään.
Niinkuin ennenkin, meni hän joka sunnuntai sinne ja oli ystävällinen
kaikille. Ainoastaan kaulahuivin solmut jäivät häneltä tekemättä.
Muuten raatoi hän työssään tyynenä ja ylevänä, pyrkien rohkeasti
elämässä yhtä ainoata päämäärää kohti, ja se oli uusi koti… Oi
Jacques! Minun Jacques äitini!

Mitä minuun tulee, antauduin kokonaan tunteelleni siitä päivin,
kun vapaasti ilman tunnonvaivoja sain rakastaa mustia silmiä. Olin
nyt kaiken päivää Pierrotte'ien luona. Olin valloittanut siellä kaikkien
sydämet; — mutta millä halpamaisilla keinoilla! Kantamalla sokeria
herra Lalouette'ille, pelaamalla korttia erinomaisen naisen kanssa —
en kammoksunut mitään… Liehakoitsija oli siihen aikaan minulle
sopivin nimi… Liehakoitsija ilmestyi tavallisesti taloon noin
keskipäivän tienoissa. Silloin oli Pierrotte puotissa ja Camille neiti
aivan yksin yläkerran salissa erinomaisen naisen kanssa. Heti kun
saavuin, ilmestyivät mustat silmät, ja melkein samalla erinomainen
nainen jätti meidät yksin. Tämä arvoisa nainen, jonka Pierrotte oli
ottanut tyttärensä seuraksi, katsoi olevansa kaikista velvollisuuksista
vapaa, heti kun minä ilmestyin. Silloin hän joutuun katosi kyökkiin
kyökkipiian luo, ja kortit vedettiin esiin. Se ei minua suinkaan
surettanut, sillä jäinhän mustien silmien kanssa kahdenkesken.
Oi, mitä ihania hetkiä olen viettänyt tuossa pienessä keltaisessa
salissa! Melkein aina toin mukanani jonkun kirjan, jonkun
lempikirjailijani ja luin siitä pitkiä otteita mustille silmille, jotka sulivat
kyyneleihin tai säihkyivät salamoina, aina sisällön mukaan. Sillä aikaa
neiti Pierrotte istui vieressämme ja ompeli tohvelia isälleen tai soitti
meille ikuisia Rosellen'in Haavelmiaan; mutta vähät me hänestä
välitimme. Toisinaan kuitenkin, kaikkein tunteellisimmissa kohdissa,
tuo pikku porvaristyttö, lausui kovalla äänellä ajatuksensa,
esimerkiksi: »Minun täytyy antaa virittää pianoni»: tai: »Olen
neulonut kaksi pistettä liikaa.» Silloin minä harmissani suljin kirjan
enkä aikonut jatkaa. Mutta mustilla silmillä oli oma omituinen
tapansa katsoa minuun, joka minut heti lepytti ja minä jatkoin
edelleen lukuani.

Oli epäilemättä hyvin varomatonta jättää meidät tuolla tavoin aina
kahdenkesken pieneen, keltaiseen saliin. Ajatelkaahan, etteivät
meidän ikämme, — mustien silmien ja Liehakoitsijan. — tehneet
yhteensä täyttä kolmeakymmentä neljää vuotta… Onneksi ei neiti
Pierrotte meitä milloinkaan jättänyt ja hän oli hyvin järkevä, hyvin
varova ja valpas vartija, juuri omiansa ruutikellaria vahtimaan…
Kerran; eräänä lämpöisenä iltapäivänä toukokuussa istuimme me,
mustat silmät ja minä, salin sohvalla. Akkuna oli puoleksi auki ja
akkunaverhot alaslaskettuina aina lattiaan asti. Sinä päivänä luimme
Faustia!… Kun olin lopettanut lukuni, liukui kirja kädestäni; me
nojauduimme hetkisen äänettöminä toisiimme puolihämärässä
hiljaisuudessa… Hänen päänsä lepäsi minun olkapäälläni. Hänen
kauluksensa aukeamasta näin pieniä hopeahelyjä, jotka kimaltelivat
hänen kaulansa ympärillä… Yhtäkkiä ilmaantui neiti Pierrotte meidän
väliimme. Olisittepa nähneet, miten sukkelaan hän lähetti minut
sohvan toiseen päähän, — ja minkä pitkän saarnan hän piti! »Te
teette hyvin pahoin, rakkaat lapset», sanoi hän meille… »Te käytätte
väärin sitä luottamusta, jota teille osoitetaan… Teidän täytyy puhua
isälle aikeistanne… Milloin aijotte puhua isälle, Daniel?» Lupasin
puhua Pierrotte'ille hyvin pian, heti kun olin saanut suuren
runoteokseni valmiiksi. Tämä lupaus rauhoitti jonkun verran
vartijaamme. Mutta siitä huolimatta ei mustilla silmillä siitä päivästä
lähtein ollut lupa istua sohvalla Liehakoitsija vieressä. Ooh, tuo neiti
Pierrotte oli hyvin ankara, nuori nainen. Ajatelkaahan, ettei hän ensi
aikoina tahtonut antaa mustien silmien kirjoittaa minulle. Lopuksi
hän kuitenkin siihen suostui, sillä nimenomaisella ehdolla, että hän
saisi kaikki kirjeet nähdäkseen. Pahaksi onneksi ei neiti Pierrotte
tyytynyt yksinään lukemaan noita hurmaavia, rakkautta uhkuvia
kirjeitä, joita mustat silmät minulle kirjoittivat, vaan pisti niihin usein
lauseita omasta päästään, niinkuin esimerkiksi tämmöisiä:

— … Tänä aamuna olen surullinen. Olen löytänyt hämähäkin
kaapistani.
Aamuhämähäkki tietää mielipahaa.
Tai myöskin:
— Ei tyhjällä taloksi ruveta… Ja sitten tuo ikuinen virsi:
— Sinun pitää puhuman isälle aikeistasi… Johon minä joka kerta
vastasin:
Heti kun olen saanut teokseni valmiiksi!…

VIII.
ERÄS ILTA SAUMON'IN KAUPPAKUJASSA.
Vihdoin viimmein sain kuuluisan runoelmani valmiiksi. Se oli neljän
kuukauden työn hedelmä, ja minä muistan, että töin tuskin voin
kirjoittaa viimmeisiä rivejä, niin kovin vapisivat käteni kuumeesta,
ylpeydestä, riemusta ja kärsimättömyydestä.
Se oli juhlahetki Saint-Germain'in kellotornissa. Jacques muuttui
siksi päiväksi jälleen tuoksi entiseksi Jacques'iksi, pahvilaatikko ja
liimakuppi Jacques'iksi. Hän sitoi minulle komean kirjan, johon hän
aikoi omakätisesti teokseni kirjoittaa puhtaaksi. Joka säe saattoi
hänet huudahtamaan ihailusta ja innostuksesta… Minä puolestani en
ollut yhtä varma teoksestani. Jacques ihaili minua liiaksi; en oikein
voinut luottaa hänen arvosteluunsa. Olisin tahtonut luettaa teokseni
jollain puolueettomalla, luotettavalla henkilöllä. Mutta kun en,
pakana vieköön, tuntenut ketään.
Ja kuitenkin olisi minulla ruokapaikassani ollut yllin kyllin tilaisuutta
tehdä tuttavuuksia. Nyt kun olimme rikkaita, söin perähuoneessa
salin takana. Siellä aterioi noin parikymmentä kirjailijaa, maalaria ja
arkkitehtiä tai oikeammin niiden aiheita. — Nyt ovat aiheet

valmistuneet: joistakuista noista nuorukaisista on tullut
kuuluisuuksia, ja kun näen heidän nimensä sanomalehdissä, niin
kirveltää minun sydäntäni, joka en mitään ole. Kun ensi kertaa tulin
heidän pöytäänsä, ottivat nuo nuorukaiset minut avosylin vastaan;
mutta kun olin liian ujo puuttuakseni keskusteluun, jouduin pian
unhotukseen ja olin yhtä yksin heidän keskellään, kuin olin ollut
pikku pöytäni ääressä yhteisessä salissa. Kuuntelin, mutta en
puhunut mitään.
Kerran viikossa söi pöydässämme eräs kuuluisa runoilija, jonka
nimeä en enää muista, mutta jota nuo toiset herrat kutsuivat
Baghavat'iksi, erään hänen runonsa mukaan. Niinä päivinä juotiin
bordeaux-viiniä, joka maksoi kahdeksantoista sous'ia pullo;
jälkiruokaa syötäessä lausui Baghavat jonkun intialaisen runonsa.
Intialaiset runot olivat hänen erikoisalansa. Yhdelle niistä oli hän
antanut nimen Lakçamana, toiselle Daçaratha, kolmannelle
Kalatçala, muuan oli Bhagiratha, muuan Cudra, muuan taasen
Cunosépa, Visvamitra… Mutta kaunein kaikista oli kuitenkin
Baghavat. Ah, kun runoilija lausui, Baghavat'insa, oli perähuone
aivan haltioissaan. Toiset ulvoivat, toiset takoivat jaloillaan lattiaa tai
hyppivät pöydälle seisomaan. Minun oikealla puolellani istui pieni
punanenäinen arkkitehti, joka heti ensimmäisessä värsyssä rupesi
itkemään ja koko ajan pyyhki silmiään minun salvettiini!
Minä kiljuin seuran vuoksi vielä kovempaa kuin muut, mutta
oikeastaan en ollut lainkaan ihastunut Baghavat'iin. Nuo intialaiset
runot olivat kaikki aivan samanlaisia. Niissä oli aina lotuskukka,
kondori, elefantti ja puhvelihärkä: joskus kutsuttiin lotusta vaihteen
vuoksi lotokseksi, mutta tätä vaihtelua lukuun ottamatta olivat hänen
kyhäyksensä aivan toistensa kaltaisia: kaikkea intohimoa, kaikkea
totuutta ja mielikuvitusta vailla. Pelkkää sanahelinää. Hämärää ja

epäselvää… Siinä minun mielipiteeni suuresta Baghavat'ista. Ehkä
olisin ollut lievempi arvostelussani, jos joku olisi pyytänyt minua
vuorostani lausumaan omia runojani, mutta se ei juontunut
kenenkään mieleen, ja se teki minun ylen ankaraksi mielipiteissäni.
Ja sitäpaitsi oli muitakin, jotka olivat samaa mieltä tuosta
hindurunoudesta. Minun vasemmanpuoleiseen vierustoveriini ei se
liioin pystynyt. Merkillinen mies, tuo minun vasemman käden
naapurini; kiiltäväksi kuluneeseen, rasvaiseen takkiin puettu,
korkeaotsainen rasvanaama, jolla oli pitkä musta parta ja siinä
melkein aina joku makaroonisäije ruuan jälkeen. Hän oli vanhin
joukosta ja ehdottomasti myöskin lahjakkain. Niinkuin suuret henget
ainakin, puhui hän hyvin vähän, ei suotta kuluttanut itseään. Kaikki
kunnioittivat häntä. Hänestä sanottiin: »Se mies pystyy … siinä on
ajattelija.» Nähdessäni hänen suunsa vetäytyvän ivalliseen hymyyn
suuren Baghavat'in lukiessa runojaan, kohosi vasemman käden
naapurini silmissäni varsin korkealle. Ajattelin: »Siinä on mies, jolla
on makua… Entäpä jos lukisin hänelle runoelmani!»
Eräänä iltana pöydästä noustaessa, tilasin pullon konjakkia ja
pyysin ajattelijan tyhjentämään lasin kanssani. Hän kiitti, minä tunsin
hänen heikkoutensa. Siinä ryypiskellessämme johdin puheen suureen
Baghavat'iin ja haukuin aluksi vahvasti lotusta, kondoreita,
elehvantteja ja puhvelihärkiä. — Se oli uskallettua, elehvantit ovat
hyvin salavihaisia!… Minun puhuissani, kaateli ajattelija itselleen
konjakkia sanaakaan sanomatta. Joskus hän hymyili ja nyökähytti
hyväksyvästi päätänsä murahtaen: »Mm, mm…» Saaden tästä ensi
menestyksestä rohkeutta, tunnustin hänelle, että olin minäkin
sepittänyt suuren runoelman ja halusin kuulla hänen mielipiteensä
siitä. »Mm, mm…» pani ajattelija taasen järkkymättömänä.
Nähdessäni miehen näin oikeassa mielentilassa, ajattelin: »Nyt on
otollinen hetki!» ja vedin runoni taskustani. Ajattelija kaatoi itselleen

liikkumattomana viidennen pikku lasin, levollisesti katsellen, kuinka
minä levitin käsikirjoitukseni, mutta ihan viime hetkellä laski hän
vanhan juopottelijan kätensä käsivarrelleni: »Sananen vain, nuori
mies, ennenkuin alotamme… Mikä on teidän kriteriuminne?»
Katselin häntä levottomana.
— Teidän kriteriuminne! … toisti kauhea ajattelija korottaen
äänensä… Mikä on teidän kriteriuminne, mittapuunne?
Herra Jumala! Minun kriteriumini! … eihän minulla sellaista ollut,
en ollut sellaista milloinkaan ajatellutkaan, ja se kyllä näkyi
punastumisestani ja ällistymisestäni.
Ajattelija nousi loukkaantuneena istuiltaan. »Kuinka, onneton nuori
mies, teillä ei ole kriteriumia!… Silloin on joutavaa, että luette
minulle runoelmanne … tiedän jo edeltäpäin, minkäarvoinen se on.»
Sitten hän kaasi itselleen vielä yhtä perää pari kolme lasia pullon
pohjasta, otti hattunsa ja lähti, pyöritellen uhkaavasti silmiään.
Kun illalla kerroin tuosta kohtauksesta Jacques'ille, vihastui hän
silmittömästi. Tuo sinun ajattelijasi on pässinpää, sanoi hän. »Vai
pitää olla kriteriumi?… Semmoinen on kai tarpeen Bengaliassa? …
kriteriumi! Mikä se on?… Missä semmoisia valmistetaan? Kuka
semmoisen on nähnyt? Kriteriumikauppias, juokse hiiteen!»…
Kunnon Jacques'illa oli kyyneleet silmissä ajatellessaan sitä
häväistystä, mikä oli tullut mestariteokseni ja minun osakseni.
»Kuuleppas. Daniel», sanoi hän hetken päästä, »jotakin juohtuu
mieleeni… Kun kerran tahdot lukea runosi jollekulle, etkö voisi tehdä
sitä Pierrotte'ien luona, jonain sunnuntaina?»…
— Pierrotte'eille… Mitä ajatteletkaan, Jacques!

— Ja miksikä et?… Peijakas! Pierrotte ei ole mikään kotka, mutta
ei pöllökään. Hänellä on hyvä ymmärrys ja selvä järki… Ja Camille
olisi oiva tuomari, joskin hiukan puolueellinen… Erinomainen nainen
on lukenut paljon… Eikä itse vanha Lalouettekaan ole niin mahdoton,
kuin hän näyttää… Ja lisäksi tuntee Pierrotte Pariisissa paljon hyvin
huomattavia henkilöitä, joita hän voisi kutsua siksi illaksi luokseen…
Mitä sanot? Tahdotko, että puhun siitä hänelle?…
Ei ollut juuri houkuttelevaa valita arvostelijansa Saumon'in
kauppakujasta, mutta kun olin melkein kipeä halusta saada lukea
jollekulle runoelmani, suostuin hiukan nenääni nyrpisteltyä
Jacques'in ehdotukseen. Heti seuraavana päivänä esitti hän asian
Pierrotte'ille. On varsin luultavaa, ettei kunnon Pierrotte täysin
tajunnut, mistä oli kysymys, mutta kun hän tässä huomasi hyvän
tilaisuuden olla neidin lapsille mieliksi, sanoi tuo kunnon mies
epäröimättä »olkoon menneeksi» ja heti lähetettiin kutsumakortit
kaikkialle.
En ollut milloinkaan ennen nähnyt pientä keltaista salia sellaisessa
juhla-asussa. Pierrotte oli minun kunniakseni kutsunut vieraikseen
porsliinimaailman parhaiston. Esityspäivän iltana oli siellä koolla
paitsi tavallista henkilökuntaa, herra ja rouva Passajon ja heidän
poikansa eläinlääkäri, Alfort'in eläinlääkäriopiston etevimpiä oppilaita,
Ferrouillat nuorempi, joka aivan äskettäin oli saavuttanut loistavan
menestyksen Suur-Looshissa, edelleen, herra ja rouva Fougeroux ja
heidän kuusi tytärtään, jotka istuivat pituuden mukaan rivissä kuin
urkujen piiput, ja lopuksi Ferrouillat vanhempi, erään kirjallisen
seuran jäsen ja illan kunniavieras. Voitte kuvitella vavistukseni
nähdessäni tämän mahtavan lautakunnan. Kun kaikille näille kunnon
ihmisille oli edeltäpäin annettu tietää, että heidät oli kutsuttu
lausumaan arvostelunsa runoteoksesta, katsoivat he

velvollisuudekseen esiintyä asian laadun mukaan juhlallisin, kylmin
naamoin, vetämättä suutaan kertaakaan nauruun. He juttelivat hiljaa
ja nyökkäsivät päätään kuin lakimiehet. Pierrotte, joka ei
ymmärtänyt olla mitenkään salaperäinen, katseli heitä kaikkia
ihmeissään. Kun kaikki vieraat olivat saapuneet, asetuttiin istumaan.
Minä istuin pianoa vasten, kuulijakunta puoliympyrässä edessäni,
paitsi vanha Lalouette, joka nakerteli sokeriaan tavallisella
paikallaan. Hetken hälinän jälkeen syntyi hiljaisuus, ja minä alotin
väräjävällä äänellä runoelmani luvun…
Se oli dramallinen runoelma, jonka olin suurenmoisesti ristinyt
Paimenlauluiksi. Vankeutensa ensi aikoina Sarlande'in lyseossa oli
Pikku Mies omaksi huvikseen kertonut oppilailleen
mielikuvitusjuttuja, jotka kuhisivat heinäsirkkoja, perhosia ja muita
itikoita. Paimenlaulut olivat syntyneet siten, että olin kolme näistä
pikku kertomuksista muodostanut vuoropuheluksi ja pannut
runomuotoon. Runoelmassani oli kolme osaa, mutta tuona iltana
Pierrotte'in luona luin niistä ainoastaan ensimmäisen osan. Pyydän
saada luvan jäljentää tässä tuon osan Paimenlauluista, en minään
valittuna kirjallisena tuotteena, vaan ainoastaan tarpeellisena lisänä
Pikku Miehen elämäntarinaan.
Kuvitelkaa hetkinen, rakkaat lukijani, että istutte puoliympyrässä
pienessä keltaisessa salissa, ja että Daniel Eyssette aivan väristen
lukee teille ääneen.
SINIPERHOSEN SEIKKAILUT.
(Näyttämö kuvaa maisemaa. On kello kuusi illalla; aurinko on
laskullaan. Esiripun noustessa sininen Perhonen sekä nuori
miespuolinen Leppäkerttu juttelevat istuen sanajalan varrella. He

Welcome to our website – the perfect destination for book lovers and
knowledge seekers. We believe that every book holds a new world,
offering opportunities for learning, discovery, and personal growth.
That’s why we are dedicated to bringing you a diverse collection of
books, ranging from classic literature and specialized publications to
self-development guides and children's books.
More than just a book-buying platform, we strive to be a bridge
connecting you with timeless cultural and intellectual values. With an
elegant, user-friendly interface and a smart search system, you can
quickly find the books that best suit your interests. Additionally,
our special promotions and home delivery services help you save time
and fully enjoy the joy of reading.
Join us on a journey of knowledge exploration, passion nurturing, and
personal growth every day!
ebookbell.com

Strongly Regular Graphs 1st Edition Andries E Brouwer H Van Maldeghem

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Strongly Regular Graphs 1st Edition Andries E Brouwer H Van Maldeghem

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 6

Slide 7

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77

Slide 78

Slide 79

Slide 80

Slide 81