Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 3 (2010) 237–258
Examples of computer experimentation in
algebraic combinatorics
Mikhail Klin
Department of Mathematics, Ben-Gurion University of the Negev, Beer Sheva, Israel
Christian Pech ∗
Lößnitzgrundstraße 47, 01445 Radebeul, Germany
Sven Reichard †
Via Scatale 640, 23852 Carlate (LC), Italy
Andrew Woldar
Department of Mathematical Sciences, Villanova University, Villanova, PA 19085 USA
Matan Ziv-Av
Department of Mathematics, Ben-Gurion University of the Negev, Beer Sheva, Israel
Received 29 September 2009, accepted 27 November 2010, published online 29 December 2010
Abstract
We introduce certain paradigms for procuring computer-free explanations from data
acquired via computer algebra experimentation. Our established context is the field of
algebraic combinatorics, with special focus on coherent configurations and association
schemes. All results presented here were obtained by the authors with the aid of com-
puter algebra systems, especially COCO and GAP. A number of examples are explored,
in particular of objects on 28, 50, 63, and 210 points. In a few cases, initial experimental
data pointed to appropriate theoretical generalizations that yielded an infinite class of re-
lated combinatorial structures. Special attention is paid to algebraic automorphisms (of a
coherent algebra), a fairly new concept that has already proved to have far-reaching conse-
quences. Finally, we focus on the Doyle-Holt graph on 27 vertices, and some of its related
structures.
∗Supported by the Skirball postdoctoral fellowship of the Center of Advanced Studies in Mathematics at the
Mathematics Department of Ben-Gurion University.
†Funded by ARC Discovery Projects Grant No. 35400300.
E-mail addresses: klin@cs.bgu.ac.il (Mikhail Klin), cpech@freenet.de (Christian Pech),
sven.reichard@yahoo.com (Sven Reichard), andrew.woldar@villanova.edu (Andrew Woldar),
matan@svgalib.org (Matan Ziv-Av)
Copyright c© 2010 DMFA Slovenije
238 Ars Math. Contemp. 3 (2010) 237–258
Keywords: Computer algebra system, GAP, COCO, coherent configuration, association scheme,
strongly regular graph, algebraic automorphism, total graph, Moore graph, Doyle-Holt graph, Gray
configuration, generalized quadrangle.
Math. Subj. Class.: 05EXX, 05E30, 05–04
1 Introduction
Coherent configurations, and in particular association schemes, form one of the central
concepts in algebraic combinatorics, as defined in the seminal book of E. Bannai and T. Ito
[3]. The aim of this paper is to elaborate to a wide mathematical audience with interdisci-
plinary interests how computer algebra tools can be applied effectively for the enumeration
and investigation of various structures that arise in algebraic combinatorics.
Special attention is paid to the spirit of computer-aided activity, specifically to com-
puter packages and their algorithmic tools, to technical data, successful ad hoc tricks, and
computer-free interpretations of obtained results. Our methodology can be traced to tradi-
tions developed by the Moscow school, a group led by V.L. Arlazarov and I.A. Faradžev
during the latter part of the twentieth century. (See [25] and [26] for first early attempts to
apply this methodology in a reasonably systematic manner.)
Our paper is intentionally written in the genre of a digest, amalgamating a number of
our previous publications with reports on several works in progress. Our aim here is to
expose the reader to numerous prototypes through the use of striking and relatively self-
contained examples, which we supplement with detailed references. Each such example
has been chosen to illustrate a particular facet of computer-aided manipulation with com-
binatorial and algebraic objects, as well as subsequent theoretical computer-free interpre-
tation of the achieved results.
An additional goal, by no means secondary, is to share with the reader a sense of the
pleasure and fulfillment we experienced in transforming routine computer output into suit-
able combinatorial models. Indeed, it is this procedure that sheds light on the connection
between structural properties of the investigated objects and their various abstract algebraic
manifestations.
Before beginning, we detail our vision of the principal objectives of computer experi-
mentation:
• constructing new objects (distance regular graphs, incidence structures, association
schemes);
• exhaustively enumerating such objects with given parameters;
• understanding and formulating an explanation of their symmetry properties;
• formulating theoretical generalizations of such objects and their properties.
Finally, we stress that esthetic criteria play an essential role in our investigations.
2 Preliminaries
Let (G,Ω) be a permutation group. Interpreting each element ofG as a permutation matrix
X of order n = |Ω|, we define
V (G,Ω) := {A ∈Mn×n(C) | AX = XA for all X ∈ G},
M. Klin et al.: Examples of computer experimentation in algebraic combinatorics 239
where Mn×n(C) denotes the algebra of all matrices of order n = |Ω| over C. It is easy to
see that V (G,Ω) is a matrix algebra having a standard basis consisting of (0, 1)-matrices.
In addition, it contains the unit matrix I , the all-ones matrix J , and is closed with respect to
complex conjugation and Schur-Hadamard (elementwise) multiplication. We call V (G,Ω)
the centralizer algebra of (G,Ω).
The centralizer algebra has a nice relational formulation in terms of binary relations
(arc sets of graphs) that are invariant with respect to (G,Ω). An axiomatic formulation
of the most significant properties of centralizer algebras leads to the definition of coherent
algebras (coherent configurations, in relational terminology), which is one of the central
concepts in algebraic combinatorics. A particular case of coherent configurations, called
association schemes, arises in this manner when (G,Ω) is assumed to be transitive.
A most important class of association schemes is comprised of those which have the
form (Ω, 2-orb(G,Ω)) where 2-orb(G,Ω) is the set of all 2-orbits of a suitable transitive
permutation group (G,Ω) (that is, orbits of the induced group (G,Ω2)). Such schemes are
called Schurian [66, 26]. Schurian schemes may be described in purely group theoretic
terms via the language of double cosets.
It is easy to see that the intersection of any number of coherent algebras is again a
coherent algebra. Thus, for a given set M of matrices of order n there exists a unique
smallest coherent algebra 〈〈M〉〉 which contains M , commonly referred to as the coherent
closure of M . Many significant coherent configurations and association schemes appear
as coherent closures of certain matrices that represent graphs or incidence structures, see
e.g. [36, 37]. Another robust source of such structures arises if we consider the coherent
subalgebras of a given coherent algebra. Here an equivalent relational name is merging
configuration, in particular merging association scheme, or simply fusion.
We assume a certain familiarity of the reader with the jargon in this area. We further
mention that it is very convenient to be able to jump back and forth between the algebraic
and relational languages of such objects. If, for example, |Ω| = n, we may speak either
of a coherent configuration on n points or a coherent algebra of order n. The number of
basic relations is referred to as the rank of the configuration, which equals the dimension
of the algebra as a vector space. In the case of an association scheme, we refer to the basic
non-reflexive relations as classes, in which case an association scheme of rank d+ 1 has d
classes. A fiber of a coherent configuration is the combinatorial analogue of an orbit of a
permutation group.
Metric association schemes with d classes are canonically generated by distance reg-
ular graphs (DRGs) of diameter d. The seminal book [14] is an encyclopedic source of
information about such objects. Distance regular graphs of diameter 2 are called strongly
regular graphs (SRGs). Interest in SRGs stems from various links between algebraic com-
binatorics and such diverse areas as permutation groups, design of statistical experiments,
coding theory, and finite geometries.
To each coherent configuration M we may attribute a number of groups: Aut(M),
which consists of usual automorphisms, CAut(M), consisting of color automorphisms,
and AAut(M), comprised of algebraic automorphisms, see e.g. [45]. Note that CAut(M)/
Aut(M) embeds canonically in AAut(M). Those elements of AAut(M) that do not arise
via this embedding are called proper algebraic automorphisms of M. (See also [45], for
details on the concepts of algebraic twins and algebraic fusion.) The full significance of
proper algebraic automorphisms became obvious only recently by virtue of a number of
computer algebra experiments fulfilled by the authors.
240 Ars Math. Contemp. 3 (2010) 237–258
We refer the reader to [35, 3, 14, 26, 45] as sources of additional information about all
combinatorial structures we consider in this paper.
3 Computer tools
Nowadays, the computer is an extremely important tool in algebraic combinatorics. We
use it in order to enumerate all combinatorial objects with prescribed properties, to identify
those objects up to isomorphism, to describe the automorphism groups of such objects, and
to investigate various algebraic properties of the obtained groups. In this manner, we obtain
additional knowledge about the structure of a given combinatorial object.
Below, we briefly discuss the most significant computer packages we use.
3.1 COCO
COCO is a system of programs designed to deal with coherent configurations. It was
developed in 1990-2, Moscow, USSR, mainly by Faradžev and Klin [25, 26]. A UNIX
version, developed by A.E. Brouwer, is available from Brouwer’s homepage [12].
The COCO system includes:
ind: a program for calculating induced action of a permutation group on a combinatorial
structure;
cgr: a program to calculate the centralizer algebra of a permutation group;
inm: a program to calculate the intersection numbers (also known as structure constants)
of a coherent configuration;
sub: a program to find fusions (aka merging association schemes) of a coherent configu-
ration given by its structure constants;
aut: a program to calculate the automorphism group of a coherent configuration, as well
as the automorphism groups of its fusions.
Usually, these programs are fulfilled in the above order. This provides a computerized
way to find all association schemes invariant under a given permutation group, plus their
automorphism groups.
One of the significant methodological advantages of COCO is related to the program
ind. Suppose we are given a permutation group (G,X), and assume S is a combinatorial
structure defined on the subset X ′ ⊆ X . Let H be the stabilizer in (G,X) of S (in
most simple cases, one has H = Aut(S)). Let Ω be the set of cosets of H in G. Then
(G,Ω) is isomorphic to (G, Ω̃), where Ω̃ is the set of all images of S obtained with the
aid of permutations from G. Typically, we do not distinguish between Ω and Ω̃ in our
considerations.
3.2 WL-stabilization
The polynomial time Weisfeiler-Leman algorithm for the computation of the coherent clo-
sure of a given set of matrices (briefly WL-stabilization) was suggested in [70, 69]. The
first efficient implementations of this algorithm were presented in [2].
In exceptional cases, such as when the order or rank of a coherent closure turns out
to be too large, it may be more efficient to use certain ad hoc computational tricks, for
example those based on the Schur-Wielandt principle, see [52]. The use of such tricks, in
M. Klin et al.: Examples of computer experimentation in algebraic combinatorics 241
conjunction with theoretically obtained bounds for the rank, may allow one to reach the
desired closure after only a few iterations.
Note that coherent closure typically applies to sets of matrices, however we may equally
well apply it to the corresponding sets of graphs (i.e., relations). In such case, our output is
a coherent configuration as opposed to a coherent algebra.
3.3 GAP
GAP [28, 65] is an acronym for “Groups, Algorithms and Programming.” It is a system for
computation in discrete abstract algebra. The system supports easy addition of extensions
(“packages” in GAP nomenclature) that are written in the GAP programming language,
and thus can add new features to the GAP system.
One such package that is very useful in algebraic combinatorics is GRAPE [67]. It is
designed for the construction and analysis of finite graphs. GRAPE itself is dependent on
an external program, nauty [60], which is used to calculate the automorphism group of a
graph.
In the course of investigations in algebraic combinatorics, one uses GAP to:
• construct incidence structures (graphs, block designs, geometries, coherent configu-
rations, etc);
• calculate automorphism groups of such structures;
• check regularity properties and parameters of structures;
• find cliques in graphs, and substructures of given structures in general;
• find the abstract structure of a group, as well as identifying it as a permutation group;
• find conjugacy classes and subgroups of a group.
3.4 DISCRETA
The package DISCRETA was created in Bayreuth, see [7]. As a rule, the main function
of DISCRETA is to obtain computer-aided proof of the existence of new t-designs with
a prescribed set of parameters. The input of DISCRETA consists of such a prescribed
parameter set, together with a permutation group (H,Ω). The output is the complete set of
all t-designs that have said parameters, and are invariant with respect to (H,Ω).
3.5 COCO v.2
The COCO v.2 initiative aims to reimplement the algorithms in COCO, together with other
packages such as WL-stabilization and DISCRETA, as a GAP package. In addition, a num-
ber of new functions are being developed that are based on new theoretical results obtained
since the original COCO package had been written. Kernel steps in this development have
been fulfilled by the author SR. A number of his colleagues continue to contribute to this
activity.
4 From computer experiment to computer-free interpretation
New striking examples are the main goal of each round of computer algebra experimenta-
tion. As a rule, an initial description of an object or property being investigated is limited
solely to available computer output. From here, one performs a posteriori reasoning in an
242 Ars Math. Contemp. 3 (2010) 237–258
effort to obtain descriptions of greater clarity and simplicity. We distinguish between two
such levels of description as follows.
Suppose we obtain a computer-generated description of, say, an incidence structure
S = (P,B). By an explanation of S, we mean a lucid computer-free description of P ,
B, and the incidence between them. Essential use of a computer, or of additional hand
calculations, is not required in this case.
By an interpretation of S, we mean that in addition to an explanation we have a self-
contained proof that S indeed has its purported structure or properties. Ideally, an interpre-
tation should be reasonably short and methodologically clear.
The following two examples are chosen to illustrate these notions. In each case, the
relevant incidence structure is an SRG.
Example 4.1. We recall an investigation initiated by I.A. Faradžev (e.g., see [25]). Con-
sider the intransitive action of G = PGL(3, 3) on the set Ω = Ω1 ∪ Ω2 of cardinality 247,
where Ω1 is the point set of the projective plane Π of order 3, and Ω2 is the set of all ovals
in Π.
With the aid of COCO, it was determined that (G,Ω) has rank 26. Additionally, COCO
revealed an SRG Γ with parameter set (247, 54, 21, 9) as a fusion in the coherent configu-
ration (Ω, 2-orb(G,Ω)). As this parameter set is pseudo-geometric (more explicitly, corre-
sponding to that of the block graph of a Steiner triple system STS(39)), it is natural to ask
whether or not it is geometric, that is, isomorphic to the point graph of a suitable partial
geometry.
This problem remained open for several years until SR, while testing his new program
for the construction of partial geometries with a given point graph, reexamined Γ. The pro-
gram confirmed that Γ is indeed geometric. Below we give an interpretation as suggested
in [63]. (Note that we use language dual to that in [25].)
Start with the projective plane Π = (Ω1,L) of order 3. Consider a new incidence
structure I = (P,B), where P consists of 39 partitions of a suitable line in L to two
point subsets of size 2. Define B = L ∪ S, where S consists of all quadrangles (dual
ovals) in Π. There are 234 quadrangles, each consisting of four lines, no three of which are
concurrent. Pairs of lines in a given quadrangle Q intersect in six distinct points which we
call intersection points. There are three additional lines which join two intersection points
of Q, not collinear in Q. Each such additional line may be partitioned into two parts: its
two intersection points and two remaining points. Such a partition forms an element of P .
This partition is incident to quadrangle Q in the above consideration. Also each line in L
is incident to its three partitions in P .
A short proof that I is indeed an STS(39) is presented in [63]. 
The distinction between explanation and interpretation can be both subtle and subjec-
tive, cf. [50]. Typically the word explanation is used. One of the most fruitful approaches
to elaborate a reasonably good explanation is to start from a suitable auxiliary structure –
the plane Π of order 3 was used in this role in the above example. We refer to [32, 33],
where a few helpful explanations of graphs with 36 and 196 vertices allowed us to describe
a new infinite series of proper loops of order 2p, p a prime, having a regular collineation
group of order 4p2 (see also [44]).
During the last decade, a number of new interesting SRGs discovered with the aid of
COCO were described by us in the literature, e.g. see [27, 42, 15, 49].
M. Klin et al.: Examples of computer experimentation in algebraic combinatorics 243
Ri valency g
R5 24 (0, 1, 3, 4, 5, 6)
R7 24 (0, 3, 4, 5, 6, 2)
R9 12 (0, 1, 4, 3, 5, 6)
R10 24 (0, 3, 1, 4, 5, 6)
R12 6 (0, 2, 4, 3, 5, 6)
R14 8 (0, 3, 2, 4, 5, 1)
R15 1 (0, 2, 4, 3, 5, 1)
Table 1: Representatives of 2-orbits merged to Γ
In the following example, we consider one such SRG which was the subject of a talk
given by the author MK at the 1995 conference BCC15. This SRG has imprimitive auto-
morphism group S7 of degree 210 and the parameters (210, 99, 48, 45). Most significantly,
it is the first discovered graph with these parameters, see [13]. At present, a description
of this graph does not appear in the literature. We now fill this gap, describing below the
entire pattern of our methodology based on the use of COCO.
Example 4.2. We considered all transitive actions of the group S7 of degree 210. As
a first step, we described up to conjugacy all subgroups of order 24 in S7. It turns out
that there are 14 conjugacy classes of such subgroups. For each subgroup H , COCO was
employed to construct the action of S7 on the set Ω of cosets of H , compute the centralizer
algebra of each corresponding permutation group (S7,Ω), and enumerate all fusions of
(Ω, 2-orb(S7,Ω)). Our goal was to produce a primitive rank 3 association scheme. For all
classes but one the result was negative.
Let us now direct our attention to a particular choice of H , namely H = 〈(0, 1, 2, 3,
4, 5), (0, 3)〉, which is isomorphic to both Z3 o Z2 and Z2 × A4. In the internal framework
of COCO, it is convenient to represent H as the automorphism group of a directed graph Σ
with vertex set [0, 6] and two connected components: the isolated vertex 6, and the Cayley
graph ∆ = Cay(〈g1〉, {1, 4}), where g1 = (0, 1, 2, 3, 4, 5). (Note that here we are using
COCO’s literal coding for a circulant graph: {1, 4} replaces {g1, g41} for the connection
set of the Cayley graph ∆ over the cyclic group 〈g1〉 of order 6.) Then we may consider
a new transitive permutation group (S7, Ω̃), where Ω̃ is the orbit of Σ with respect to S7.
Identifying Ω̃ with Ω, COCO returns that the group (S7,Ω) has rank 16 with subdegrees
12, 62, 82, 125, 245.
There are 14 fusions, two of which are primitive. Both primitive fusions are non-
Schurian schemes with 2 classes, which define two isomorphic strongly regular graphs
with the parameters (210, 99, 48, 45).
We describe one of these graphs Γ as an explicit fusion of certain 2-orbits of (S7,Ω).
Each such 2-orbit Ri is represented with the aid of a representative (0, ri), where 0 is
notation for the canonical graph Σ and ri ∈ Ω is a label of an element of Ω. Note that each
ri is nothing more than a suitable isomorphic copy of the Cayley graph ∆, together with
an isolated vertex. To describe this copy, it suffices to indicate a cycle g which replaces g1
in our definition of ∆. All required information is presented in Table 1. 
Remark: Our description of graph Γ in Example 4.2 is largely predicated on the form of
available computer data, and falls short of even being an explanation in our terminology,
244 Ars Math. Contemp. 3 (2010) 237–258
as it would be difficult to construct this graph via hand computations. In fact, some nice
geometrical ideas were expressed a long time ago by G. Jones and K. Lloyd as to how
to produce an interpretation of the constructed graph Γ. We intend to realize such an
interpretation in the context of a future project.
The construction of new examples of SRGs was one of our original goals, even prior to
conception of the computer package COCO.
The paper [26] contains detailed information about a number of SRGs constructed by
MK, in particular ones on 120, 126, 330, 495, 1716 vertices invariant with respect to a
suitable action of the symmetric group Sn (n = 10, 9, 11, 12, 13, respectively). It seems
that some interesting links between these graphs still require special clarification. Another
family of striking examples was described in [41], see also [26]. These are graphs on 144,
280, 280, 280, 560 vertices with primitive automorphism groups PSL(3, 3), Aut(J2), S9,
Aut(J2), Aut(Sz(8)), respectively. The graph on 280 vertices with group S9 was also
independently discovered by R. Mathon and A. Rosa (see [59]).
All these results were originally presented in preprints in Russian, not readily accessi-
ble to a Western audience. As a consequence, proper attribution of authorship was never
indicated in catalogues of known SRGs. This is why we take this opportunity to recall once
more our old discoveries.
5 Total graph coherent configurations
Let Σ = (V,E) be a graph. The total graph T (Σ) is the graph with vertex set V ∪ E, in
which two vertices are adjacent in T (Σ) if they are either adjacent or incident in graph Σ.
(Edges of Σ are said to be adjacent if they have a common vertex.) The concept of a total
graph was suggested in [6], see also [5].
Observe that in some exceptional cases the total graph T (Σ) may have a more ro-
bust automorphism group than the original graph Σ. For example, for n ≥ 2 one has
Aut(Kn) = Sn and Aut(T (Kn)) ∼= Sn+1, see [6].
We call the coherent closureW (T (Σ)) of the total graph T (Σ) the total graph coherent
configuration of Σ. We also wish to consider the Schurian coherent closure S(T (Σ)) of
T (Σ). Here S(T (Σ)) = (Ω, 2-orb(G,Ω)), where Ω is the vertex set of T (Σ) and G =
Aut(T (Σ)). It is clear that in general W (T (Σ)) is a suitable subalgebra (merging, in
relational language) of S(T (Σ)). In our eyes, the question as to when S(T (Σ)) coincides
with W (T (Σ)) is one of significant theoretical interest. This question was considered in
[53, 74] for two classes of classical strongly regular graphs, namely the triangular graphs
Tn and the lattice square graphs L2(n). For both classes of graphs it was proved that
W (T (Σ)) = S(T (Σ)).
Another motivation of our interest in total graph configurations is of a more concrete
nature. In the course of proving W (T (Tn)) = S(T (Tn)), we investigated all association
schemes which appear as mergings of I(n) = W (T (Tn)). It turns out that for sufficiently
large n, the configuration I(n) has just two easily predictable imprimitive mergings of
respective ranks 3 and 4. Pleasant surprises appear only for n = 5, 7.
In the case n = 5, we get a very interesting Schurian rank 5 association scheme of
order 40 with automorphism group of order 1920, see [47]. For n = 7, we get a nontrivial
merging which is of an independent interest. It corresponds to an embedding of the sym-
metric group S7 in the group U(4, 3).22 of order 13063680, and provides a new model for
the unique Zara graph on 126 vertices. This case will be considered in a forthcoming paper
M. Klin et al.: Examples of computer experimentation in algebraic combinatorics 245
by MK and MZ-A, along with L. Jørgensen.
Remark: The motivation behind the introduction of WL-stabilization in [70] was its appar-
ent link to the graph isomorphism problem. Indeed, the coherent closure 〈〈Γ〉〉 of a given
graph Γ may serve as a source of various algebraic invariants of Γ. Moreover, 〈〈Γ〉〉 may
be computed in polynomial time on the number of vertices of Γ. This is why the notion
of coherent algebra is especially useful in the theory of complexity of algorithms, e.g. see
[52, 24].
A new attempt to solve the graph isomorphism problem was initiated in [64]. The
invariants formulated in that paper seemed to indicate that the total graph coherent config-
uration would play a promising role in systematically identifying the major difficulties of
the problem. However, the paper [4] appears to have suppressed part of such hopes.
6 Coherent configurations and the Hoffman-Singleton graph
It is well known (e.g., see [18]) that if a Moore graph of diameter 2 has valency k then
k ∈ {2, 3, 7, 57}. The unique examples with k = 2 and k = 3 are the pentagon and the
Petersen graph, respectively. Below we consider from diverse points of view the unique
Moore graph of valency 7 on 50 vertices, that is, the Hoffman-Singleton graph HoSi [39].
The existence of a Moore graph of valency 57 is an open problem.
Our first goal is to provide a new model of HoSi. First we need an auxiliary proposi-
tion, cf. [18].
Proposition 6.1. There are six distinct, pairwise isomorphic, 1-factorizations of the graph
K6. Each of these has automorphism group S5, acting 3-transitively on six points.
In what follows we consider a representative 1-factorization F of K6 with vertex set
[0, 5], namely
F ={{{0, 1}, {2, 4}, {3, 5}}, {{0, 2}, {1, 5}, {3, 4}}, {{0, 3}, {1, 2}, {4, 5}},
{{0, 4}, {1, 3}, {2, 5}}, {{0, 5}, {1, 4}, {2, 3}}}.
It is convenient to regard the considered copy of K6 as a subgraph of K7 with isolated
vertex 6.
Example 6.2. Let Ω1 = {∅}, Ω2 = [0, 6] and Ω3 = FS7 , where FS7 is the orbit of F
under action of S7 = Aut(K7). Denote Ω = Ω1 ∪Ω2 ∪Ω3. Clearly, the symmetric group
S7 = S([0, 6]) acts naturally on Ω with orbits Ω1, Ω2, Ω3. Thus we may consider the
coherent configurationH = (Ω, 2-orb(S7,Ω)). Using COCO, we obtain that:
a) H is a rank 15 configuration with three fibers of size 1, 7, 42. Its type is
1 1 11 2 2
1 2 4

with valencies
1 7 421 (1, 6) (36, 3)
1 (6, 1) (1, 30, 5, 6)
.
b) Merging of the relations 1, 3, 7, 10, 14 of respective valencies 7, 1, 6, 1, 6 provides a
copy of the graph HoSi. 
246 Ars Math. Contemp. 3 (2010) 237–258
In (a) above, the labeling of relations is lexicographic: first down columns, then across
rows. For example, the second column in the matrix of valencies indicates that the relations
R3, R4, R5, R6, R7 have respective valencies 7, 1, 6, 6, 1.
We mention that we were able to achieve a rather nice computer-free interpretation of
HoSi, however the exposition is quite lengthy. Two additional models of HoSi, which
we briefly describe in Example 6.3 below, will also be presented in detail elsewhere. In a
sense, these latter two models may be interpreted as information accumulated from diverse
sources (in particular, due to N. Robertson, P. Hafner, L. O. James, G. Fan & A.J. Schwenk,
R. H. Jeurissen, and others) transformed into the language of coherent configurations.
Example 6.3. Model A: Consider the group D = D5 × AGL(1, 5) of order 200 acting
intransitively on a set of cardinality 50. It defines a coherent configuration XD of rank 29
with three fibers of size 5, 25, 20. Two Schurian fusions of XD correspond to the rank 3
association scheme coming from the graph HoSi. In fact, configuration XD corresponds
to the stabilizer of an arbitrary pentagon in HoSi.
Model B: Consider the stabilizer G in Aut(HoSi) of a Petersen subgraph P in HoSi.
There are 525 copies of P in HoSi, all belonging to the same orbit of Aut(HoSi). We
obtain that G is a group of order 480, specifically an extension of Z4 with the aid of S5
(see [47] for details). We associate to G a coherent configuration XG of rank 16 with two
fibers of size 40 and 10. Configuration XG has a unique rank 3 fusion which corresponds
to HoSi. 
We conclude this section with an example which shows how the notion of total graph
coherent configuration may be applied to shed additional light on the Hoffman-Singleton
graph.
Example 6.4. Consider the complement graph HoSi of HoSi, and let T (HoSi) denote
its total graph. With the aid of COCO we obtained the total graph coherent configuration,
and detected in it a very interesting primitive fusion with four classes on 1100 points. As
the automorphism group of T (HoSi) coincides with the automorphism group HS : 2 of
the Higman-Sims graph, this fusion provides new insight into the classical embedding of
Aut(HoSi) into HS :2. Again, details will appear elsewhere. 
Remarks:
1. The second constituent ofHoSi is a distance transitive graph of valency 6 on 42 vertices
which is an antipodal cover of K7, see [14]. One of the additional functions of Example
6.2 is its direct construction in terms of 42 1-factorizations of K6 inside of K7.
2. It is well known that if there exists a Moore graph of valency 57, then it cannot have a
transitive automorphism group (e.g., see [55], and the references therein). Thus, the result-
ing association scheme may arise as a fusion within a suitable coherent configuration with
at least two fibers. In this context, the coherent configurations of Example 6.3 may provide
an excellent training ground for deciding which structures would be promising initial can-
didates from which a Moore graph on 3250 vertices may be constructed.
3. Example 6.4 illustrates one of the most successful paradigms in algebraic combinatorics
for attaining a better understanding of a given combinatorial structure I. Namely, we em-
bed I into a larger structure Î for which Aut(Î) is a proper overgroup of Aut(I). Here the
roles of I and Î were played by HoSi and T (HoSi), respectively, and the resulting over-
group turned out to be the automorphism group of the Higman-Sims graph. Speculating
M. Klin et al.: Examples of computer experimentation in algebraic combinatorics 247
once more on possible ways to attempt a construction of a Moore graph Γ of valency 57,
one may expect that it is possible to embed Γ into a suitable merging of W (T (Γ)) which
has larger group than Aut(Γ).
7 Some association schemes on 28 points
In [45], a number of interesting combinatorial objects on 28 points were investigated. Start-
ing with the regular group E8, the authors considered its induced intransitive action on the
set Ω =
{
[0,7]
2
}
of all 2-element subsets of [0, 7]. It turns out that the corresponding coher-
ent configuration W provides an example of a so-called Wallis-Fon-Der-Flaas (or briefly
WFDF) coherent configuration. In terms of W , we were able to give a new uniform inter-
pretation of a number of classical objects on 28 points, as well as other association schemes
that had formerly been presented only at the level of strict computer output. Below we pro-
vide a representative case, in which we also add new detail to the presentation given in
[45].
Example 7.1. Recall from Section 2 the notion of a proper algebraic automorphism. We
call two association schemes A, A′ twins with respect to the coherent configuration W if
they are fusions in W , and there exists a proper ρ ∈ AAut(W ) for which Aρ = A′. One
of many pairs of such twins found in [45] is described presently. Here the role of W is
fulfilled by the WFDF configuration described above.
Preserving the notation of [45], #109 and #110 form a pair of twins. In fact, #109 and
#110 are not combinatorially isomorphic. Indeed, scheme #109 is Schurian with automor-
phism group isomorphic to AΓL(1, 8), while #110 is non-Schurian with group H of index
7 inside AΓL(1, 8). As an abstract group, H is isomorphic to the group considered in Ex-
ample 4.2, however in our current context it behooves us to represent this group in terms of
the set [0, 7]. For this purpose, an old construction due to L. E. Dickson and F. H. Safford
[20] becomes quite relevant. Namely, we consider a copy of the 3-cube Q3 with vertex set
V = [0, 7], and having 12 edges as follows: {0, 2}, {0, 6}, {0, 7}, {1, 3}, {1, 4}, {1, 5},
{2, 3}, {2, 4}, {3, 7}, {4, 6}, {5, 6}, {5, 7}.
We now produce seven disjoint 1-factors of K8. The first of these is the set of space
diagonals of Q3: d = {{0, 1}, {2, 5}, {3, 6}, {4, 7}}. Our six remaining 1-factors are:
a = {{0, 4}, {2, 6}, {1, 5}, {3, 4}}, b = {{0, 7}, {2, 3}, {1, 6}, {4, 5}},
c = {{0, 2}, {1, 7}, {3, 5}, {4, 6}}, e = {{0, 6}, {1, 2}, {3, 4}, {5, 7}},
f = {{0, 5}, {1, 3}, {2, 4}, {6, 7}}, g = {{0, 3}, {1, 4}, {2, 7}, {5, 6}}.
It is easy to check by hand that
H = 〈(1, 2, 6)(3, 0, 5), (2, 6, 7)(3, 4, 5), (1, 3)(2, 4)(5, 7)(0, 6)〉
is the full automorphism group of this 1-factorization, here denoted by F .
The advantage of our model is that each element of Ω appears exactly once in F . Thus
the induced action of H = Aut(F) on Ω, as well as its 2-orbits, are quite visible in terms
of F . In fact, H has rank 38 with three orbits on Ω of lengths 12, 12 and 4. These orbits
correspond to unordered pairs of vertices of respective distance 1, 2 and 3 in the graph Q3.
The coherent configuration M = (Ω, 2-orb(H,Ω)) has very interesting properties. Indeed,
CAut(M)/Aut(M) ∼= Z2×D4 is a group of order 16, while AAut(M) ∼= Z2×Z2×D4
has order 32. Thus M has many algebraic fusions as well as twins. In particular, the above
schemes #109 and #110 appear as twins in M. 
248 Ars Math. Contemp. 3 (2010) 237–258
Remark: As discussed in [45], a striking feature of WFDF configurations is that they
tend to have a large number of proper algebraic automorphisms. Moreover, it is rare to
find this feature in coherent configurations of non-WFDF type. From this point of view,
configuration M is of definite independent interest.
8 The simple group of order 504
The simple group L = PSL(2, 8) of order 504 has many intriguing links to diverse com-
binatorial and geometrical structures. Here we mention only a few: overlarge sets of Fano
planes, overlarge sets of affine designs S(3, 4, 8), partial geometries pg(8, 9, 4), partial ge-
ometries pg(5, 7, 3), a number of coherent configurations and association schemes. All
these structures will be described in a unified manner in [51], based on a lecture given by
the author AW at the 2004 conference ICIG, Belgium.
As usual, our initial investigations made extensive use of computer algebra tools, fol-
lowed by computer-free interpretations in most cases. We present only a small fragment of
these sans details.
Example 8.1. Denote by N the group Aut(L) ∼= PΓL(2, 8) of order 1512. We consider
the natural 3-transitive action of N on the points of Ω = PG(1, 8). Group N is not geo-
metric in the sense of D. Betten [8], that is, one cannot realize N as the full automorphism
group of a suitable incidence structure with PG(1, 8) as point set. For this reason, we first
show that N is geometrical of second order, in other words N is the automorphism group
of a suitable set of incidence structures, namely in our case an overlarge set O of affine
designs (cf. [11]).
Starting with the set O, we provide a interpretation of one of two partial geometries
pg(5, 7, 3) discovered by R. Mathon [58]. For this purpose, we define an incidence struc-
ture M = (P,L) with point set P = Ω ∪
(
Ω
2
)
(i.e., all singletons and unordered pairs of
elements from Ω) and line set L consisting of all partitions of Ω into four classes of size 2
and one class of size 1 which satisfy a special requirement formulated in terms of O. Fi-
nally, incidence is ordinary containment. In this manner, we obtain an incidence structure
M with 45 points and 63 lines which we were able to prove is a pg(5, 7, 3). Moreover, we
showed that Aut(M) = Aut(O) ∼= PΓL(2, 8).
An alternative interpretation may be arranged in terms of the set X of 63 cosets of the
subgroup H = Z2 × A4 in N . The association scheme H = (X, 2-orb(N,X)) has rank
6 with subdegrees 1, 3, 3, 8, 24, 24. All 2-orbits have a natural geometrical explanation. It
turns out that CAut(H) = Aut(H) = N , while AAut(H) has order 2. The unique proper
algebraic automorphism defines two pairs of twins: two non-Schurian association schemes
with 3 classes and two strongly regular graphs with the parameters (63, 30, 13, 15). One
SRG is a rank 3 graph, while the second is non-Schurian with automorphism groupN . The
latter graph turns out to be the block graph of the constructed geometry pg(5, 7, 3).
Remark: A nice feature of our presentation is that we are able to consider in parallel two
non-isomorphic overlarge sets in a unified manner. From each we obtain a pg(5, 7, 3). The
second geometry has smaller automorphism group, specifically ASL(2, 3) of order 216.
9 Doyle-Holt graph and related structures
We come now to our final example of computer experimentation in service of algebraic
combinatorics. Our investigation begins with the Doyle-Holt graph (aka Doyle graph, aka
M. Klin et al.: Examples of computer experimentation in algebraic combinatorics 249
Holt graph), which has an interesting history. In [68] W. Tutte posed a question about the
existence of a graph that is vertex-transitive, edge-transitive but not arc-transitive. The first
actual examples were provided by I.Z. Bouwer in [10], specifically an infinite series of such
graphs of valency 2n, n ≥ 2, with smallest member being on 54 vertices. In 1981, D.F.
Holt [40] provided an example on 27 vertices, however it was later discovered that Holt’s
example had appeared earlier in the 1976 senior thesis of P.G. Doyle, e.g., see [21]. In [73]
M.Y. Xu proved that the Doyle-Holt graph is the unique graph on 27 vertices having the
requested properties, while in [1] it was established that no graph on fewer vertices could
be of such type.
It turns out that the Doyle-Holt graph is related to many other diverse combinatorial
structures such as the Gray configuration, generalized quadrangle on 27 points, generalized
octagons on 80 and 160 points, etc. In what follows we provide a fresh context for this
famous graph, based on strict use of group theoretic arguments framed in the language of
association schemes. We start with a description of its automorphism group.
9.1 Automorphism group
In [40], Holt computed the automorphism group H by hand, divulging that it has or-
der 54 and possesses a regular nonabelian subgroup. In fact, group H is abstractly the
holomorph Hol(Z9), and one concrete realization of it is given by H = 〈g1, g2〉 where
g1 = (0, 1, 2, 3, 4, 5, 6, 7, 8) and g2 = (1, 2, 4, 8, 7, 5)(3, 6). Thus H is the full normalizer
of 〈g1〉 in S9.
Consider the three undirected 9-cycles with common vertex set [0, 8] given by consec-
utive vertices as follows:
C9,1 : 012345678 C9,2 : 024681357 C9,3 : 048372615
It is immediate that Aut(C9,i) = 〈g1, g32〉 ∼= D9 for all i, while g22 permutes C9,1, C9,2,
C9,3 cyclically.
Form the sum graph Σ = C9,1 + C9,2 + C9,3, that is V (Σ) = [0, 8] and E(Σ) =
E(C9,1) ∪E(C9,2) ∪E(C9,3). Note that H acts transitively on vertices, edges and arcs of
Σ, and that Σ = 3 ◦K3. Denote by Ω and Ω the edge sets of graphs Σ, Σ respectively.
9.2 Induced action and association scheme
Consider now the induced action of H on Ω = E(Σ), as well as the resulting association
scheme X = (Ω, 2-orb(H,Ω)). The following facts about X are easily obtained through
the aid of COCO.
Proposition 9.1. (i) X has 14 classes, exactly four of which are symmetric;
(ii) (H,Ω) is 2-closed;
(iii) the color group of X has order 162;
(iv) X has exactly 49 fusion schemes;
(v) three of its fusions are isomorphic, and correspond to a strongly regular graph with
parameters (ν, k, λ, µ) = (27, 10, 1, 5) with group of order 51840;
(vi) among its 17 rank 4 fusions, there are three isomorphic non-Schurian fusions with
group of order 324, and three isomorphic Schurian fusions with group of order 1296;
(vii) all six rank 4 fusions from (vi) (both Schurian and non-Schurian) are metric associa-
tion schemes generated by an antipodal DRG of valency 8.
250 Ars Math. Contemp. 3 (2010) 237–258
0 2
6
13
24
17
20
22
26
25
15
18
23
1619
14
8
10
7
9
21
3
4
11
1
5
12
Figure 1: Factorization of ∆ into two Hamiltonian cycles. Note: The second cycle is
(0, 24, 18, 1, 2, 26, 3, 5, 17, 7, 4, 6, 14, 9, 12, 23, 8, 11, 25, 16, 21, 20, 15, 10, 13, 22, 19).
9.3 Model of Doyle-Holt graph
Analyzing the lattice of fusions of X, one immediately identifies three copies of an undi-
rected regular graph of valency 4 whose coherent closure coincides with X. Each such
graph is obtained as the union of two paired non-symmetric (connected) 2-orbits of (H,Ω).
This implies the existence of a graph on 27 vertices that is both vertex- and edge-transitive
but not arc-transitive.
Such considerations led us to a new interpretative model of the Doyle-Holt graph ∆, as
well as a computer-free independent confirmation that its automorphism group is H . (We
alert the reader that Aut(∆) = H is already a simple consequence of Proposition 9.1. Our
text below is aimed at providing a nice alternative justification of this fact.)
Our graphical representation was greatly aided by certain bits of established informa-
tion about the Doyle-Holt graph (e.g., see [71]), in particular, that it can be factorized into
two disjoint Hamiltonian cycles each invariant under a cyclic subgroup ofH of order 9, see
Figure 1. In fact, there are exactly three such factorizations possible.
Let us write x̃ to denote the induced action of x ∈ H on the edge set E = E(∆). The
following result is easily proved.
M. Klin et al.: Examples of computer experimentation in algebraic combinatorics 251
0 24
18
15
12
23
172
Figure 2: Three pairs of pentagons providing the same noble hexagon.
Proposition 9.2. (i) The element g̃1 ∈ H of order 9 preserves both Hamiltonian cycles C1,
C2 in a given factorization;
(ii) 〈g̃1〉 has six orbits on E, three comprising C1 and the others C2;
(iii) Element g̃2 ∈ H of order 6 cyclically permutes these six orbits on E;
(iv) D9 := 〈g̃1, g̃23〉 stabilizes the Hamiltonian factorization {C1, C2};
(v) 〈g̃22〉 acts regularly on the three Hamiltonian factorizations of ∆;
(vi) H = 〈g̃1, g̃2〉 is a subgroup of Aut(∆).
The new proof that |Aut(∆)| = 54 (and hence thatH = Aut(∆)) proceeds roughly as
follows. Graph ∆ is easily seen to contain 54 pentagons (use edge-transitivity and the fact
that there are five pentagons on a fixed edge). Next observe that two distinct pentagons can
intersect in at most two edges (since ∆ has girth 5). Moreover, given a fixed pentagon P
there is exactly one pentagon P ′ for which |E(P ) ∩ E(P ′)| = 2. Call P, P ′ mates if they
have this property. Clearly, the symmetric difference of any pair of mates yields a hexagon,
called by us a noble hexagon. It is not hard to see that every noble hexagon arises in this
manner from exactly three distinct pairs of mates, e.g., see Figure 2.
Proposition 9.3. (i) The edge set E of ∆ partitions into nine noble hexagons;
(ii) this partition is invariant with respect to Aut(∆) and forms a single orbit under the
action of H;
(iii) Aut(∆) acts faithfully on the set of noble hexagons;
(iv) the stabilizer in H of a noble hexagon is a cyclic group of order 6.
So it remains only to show that the stabilzer in Aut(∆) of a noble hexagon has order
6. Clearly, the only other possibility is that this order is 12, which arises if the stabilizer is
the full automorphism group of the hexagon, i.e., the dihedral group D6. To refute this it
suffices to exhibit a single reflection in a single noble hexagon that cannot be extended to
an automorphism of ∆. This gives the following.
252 Ars Math. Contemp. 3 (2010) 237–258
Corollary 9.4. (i) Graph ∆ has automorphism group H;
(ii) ∆ is vertex-transitive and edge-transitive, but not arc-transitive;
(iii) ∆ is isomorphic to the Doyle-Holt graph.
Remarks:
1. Alternatively, one may prove Corollary 9.4 by WL-stabilization, as discussed in Sec-
tion 3.2. Here, one inputs the graph ∆ and obtains as output the association scheme X
introduced in Section 9.2. Scheme X is quasithin in the sense of [38], whence it is im-
plied by Theorem 3.7(iv) of that paper that a point stabilizer in Aut(∆) has order 2. Thus
|Aut(∆)| = 2 · |Ω| = 54.
2. We may also establish Corollary 9.4 by using results from the catalogue [17]. Indeed,
from the list of transitive permutation groups of degree 9 we are able to quickly rule out
any candidate for Aut(∆) as a prospective overgroup ofH in S9. Note also that part (iii) of
Corollary 9.4 follows at once from the properties of the partition of ∆ into noble hexagons.
3. The smallest Bouwer graph on 54 vertices (cf. [10]) may be obtained from the Doyle-
Holt graph via the process of standard bipartite doubling. This immediately identifies the
automorphism group of this Bouwer graph as H × Z2.
4. Implicit in our investigations is a realization of the Doyle-Holt graph as a Cayley graph
over the non-abelian group R = 〈g1, g22〉 with connection set {g1, g−11 , g22 , g
−2
2 }.
5. Last but not least, we wish to emphasize an evident split of the edge set E into two
pairs of non-symmetric relations of valency 2. In fact, these relations are both H-orbits,
specifically
−→
E = (0, 2)H and
←−
E = (2, 0)H . Figure 1 provides an especially nice way to
view each such relation depending on the orientation chosen. For example, consider the
clockwise orientation of the “external” Hamiltonian cycle starting from the arc (0, 2), and
similarly do this for the clockwise “internal” Hamiltonian cycle starting from (0, 24). In
total, the 54 arcs so transversed comprise the relation
−→
E .
9.4 From Doyle-Holt graph to Gray graph
Let us return to the auxiliary graph Σ of Section 9.1. As before, let Ω denote its edge set,
and let B be the set of triangles in Σ. Recalling that Σ = 3 ◦K3, it is easy to deduce that
|B| = 27, and that each edge of Σ is contained in exactly three triangles. Now form the
design S = (Ω,B) where incidence is given by inclusion. Clearly S is a configuration,
that is a uniform, regular partial linear space. Further, S is symmetric (because |Ω| = |B|),
though it is not self-dual.
The incidence graph I(S) of this configuration first appeared in [9], though Bouwer
accredits its discovery to M.C. Gray (unpublished work, 1932). Thus one now refers to S
as the Gray configuration, and to I(S) as the Gray graph.
Let us start with the same group H (automorphism group of the Doyle-Holt graph)
acting on the initial set [0, 8], and consider the 2-closure (H(2), [0, 8]). This latter group
turns out to be the automorphism group of each of the graphs Σ and Σ = 3 ◦ K3. As an
abstract group, H(2) is the familiar wreath product S3 o S3, however its concrete action
on the set B coincides with the slightly less familiar product action of S3 o S3 (coined
“exponentiation” by F. Harary, and denoted by S3 ↑ S3). In fact, as an abstract group H(2)
is isomorphic to the authomorphism group of the Gray graph. Note further, that while the
action (H(2),B) is well known to be primitive, the action (H(2),Ω) is imprimitive.
The Gray graph has received much attention over the years, and has been the subject
M. Klin et al.: Examples of computer experimentation in algebraic combinatorics 253
of diverse investigations, e.g., see [56, 57, 62]. Especially noteworthy is the fact that it is
regular and edge-transitive but not vertex-transitive. Following [43] we call such a graph
semisymmetric. See [54, 22, 72, 61] for constructions of infinite series of semisymmetric
graphs in which the Gray graph appears as an initial member.
9.5 From Gray configuration to generalized quadrangle
The generalized quadrangle GQ(2, 4) has 27 points and 45 lines. Its point graph is the
unique SRG with parameters (27, 10, 1, 5), hence we may identify it as the graph which
arises in connection with three separate fusions of X, see Proposition 9.1(v). Traditionally,
one refers to this SRG (though more often to its complement) as the Schläfli graph, e.g.,
see [18, 29]. Thus we shall denote it by Sch.
In a sense, Sch is the most symmetric of all nontrivial graphs. More precisely, it is 4-
homogeneous, which means that each isomorphism between any two of its k-vertex induced
subgraphs, k ≤ 4, may be extended to an automorphism of the entire graph, see [30, 48].
In fact, Sch is the only strictly 4-homogeneous graph (i.e., 4- but not 5-homogeneous), as
can be verified by applying the major classification theorem CFSG.
Natural constructions of GQ(2, 4) (and hence, Sch) most often occur in the context of
finite geometries and Coxeter systems. However, the model we wish to here describe has
the advantage of visibly extending the Gray configuration. Currently, this model appears
only in the Ph.D. thesis of A. Heinze [31], so this marks its first presentation in the formal
literature.
Once again we start from the auxiliary graph Σ with edge set Ω. Denote by V1, V2, V3
the vertex sets of the three disjoint triangles which form the graph Σ. For each 1 ≤ i <
j ≤ 3, denote by Fij the set of all perfect 1-factors of the induced subgraph Σ[Vi ∪ Vj ] of
Σ. Finally set F = F12 ∪F13 ∪F23. Clearly, F consists of 18 = 3 · 3! partial 1-factors of
the graph Σ.
Now set L = B ∪F , where B is the earlier defined block set of the Gray configuration.
(Note that |L| = |B|+|F| = 27+18 = 45.) We consider the incidence system Π = (Ω,L),
where once again the incidence relation is inclusion.
We leave to the reader verification that Π is indeed a model of GQ(2, 4). One clear
advantage of our model is that it exploits the Gray configuration in evident form.
Recall that a spread of a generalized quadrangle is a subset of lines that partitions its
point set. It turns out that up to isomorphism GQ(2, 4) has two classes of spreads, e.g., see
[16]. An additional advantage of our model is that both types of spreads are quite visible in
the developed framework. Indeed, one may choose suitable non-isomorphic spreads S1, S2
for which S1∪S2 = F . Note that the stabilizers in Aut(GQ(2, 4)) ∼= PΓU(4, 2) of S1 and
S2 have respective orders 324 and 1296, and are in fact the groups appearing in Proposition
9.1(vi). The group of order 324 is the normalizer in S9 of the semiregular group 〈g31〉 of
order 3, while the group of order 1296 is a non-split extension of N by S4, where N is the
transitive group #12 (so denoted in [17]) of degree 9 and order 54.
Recall that deletion of a spread from the point graph of a generalized quadrangle yields
an antipodal DRG of diameter 3, see [14]. In this context, the DRGs so arising from the
spreads S1 and S2 are non-isomorphic, in fact only one such graph is distance transitive.
The non-distance transitive graph has a celebrated property however: it satisfies the 5-
vertex condition for DRGs (a natural generalization of the t-vertex condition for SRGs, see
[34] for precise definitions). This newly described property of the latter DRG complements
quite nicely the discovery in [23] that Levi graphs of projective planes satisfy the 6-vertex
254 Ars Math. Contemp. 3 (2010) 237–258
condition for DRGs.
9.6 On an observation of Pisanski
Let W(3) denote the generalized quadrangle of order (3,3) (symplectic type), having 40
points and 40 lines. Denote its incidence graph by Θ. Note that Θ is semisymmetric
because W(3) is not self-dual.
We refer now to the closing portion of [62], where one learns that the Gray graph can
be detected as an induced subgraph of Θ (e.g., induce on the 54 vertices at distance 4 from
a fixed edge of Θ). It is further mentioned in [62], though without details, that there are
exactly 160 embeddings of the Gray graph in Θ. Our goal is to shed some additional light
on these embeddings.
It is known (though not widely, cf. p. 305 of [19]) that the incidence graph Θ is simul-
taneously the point graph of the generalized octagon GO(1, 3). As W(3) and GQ(2, 4)
have isomorphic automorphism groups, namely PΓU(4, 2), we see that the stabilizer of an
edge in Θ has order 51840160 = 324. We summarize our findings below.
Proposition 9.5. (i) The stabilizer of an edge in Θ coincides with the earlier encountered
stabilizer of a representative spread S1 of GQ(2, 4);
(ii) the transitive action of Aut(GQ(2, 4)) on the 160 spreads of type S1 is permutation
isomorphic to the action of Aut(GO(1, 3)) on the lines of the octagon;
(iii) the 160 embeddings of the Gray graph in the incidence graph of W(3) correspond to
points of the dual octagon GO(3, 1).
All results in Proposition 9.5 were initially obtained and/or confirmed with the aid of
GAP and COCO. Independent computer-free proofs and interpretations have since been
supplied by us. However, being technically cumbersome they have been relegated to a
future paper.
Acknowledgements
We thank Leif Jørgensen and Mikhail Muzychuk for helpful collaboration on a number
of projects connected with this paper. We further extend our gratitude to two anonymous
referees for their valuable comments and suggestions.
References
[1] B. Alspach, D. Marušič and L. Nowitz, Constructing graphs which are 1/2-transitive, J.
Austral. Math. Soc. Ser. A 56 (1994), 391–402.
[2] L. Babel, I. V. Chuvaeva, M. Klin, and D. V. Pasechnik, Algebraic combinatorics in math-
ematical chemistry II, Program implementation of the Weisfeiler-Leman algorithm, Preprint
TUM-M9701, TU-München, 1997, arXiv:1002.1921v1 [math.CO] 9 Feb 2010.
[3] E. Bannai and T. Ito, Algebraic combinatorics, I. Association schemes, The Benjamin Cum-
mings Publishing Co. Inc., Menlo Park, CA, 1984.
[4] A. Barghi and I. Ponomarenko, Non-isomorphic graphs with cospectral symmetric powers,
Electron. J. Combin. 16 (2009), #120.
[5] M. Behzad, A characterization of total graphs, Proc. Amer. Math. Soc. 26 (1970), 383–389.
[6] M. Behzad, G. Chartrand and E. A. Nordhaus, Triangles in line-graphs and total graphs, Indian
J. Math. 10 (1968), 109–120.
M. Klin et al.: Examples of computer experimentation in algebraic combinatorics 255
[7] A. Betten, R. Laue and A. Wasserman, DISCRETA – A tool for constructing t-designs,
Lehrstuhl II für Mathematik, Universität Bayreuth, 1996,
http://www.mathe2.uni-bayreuth.de/discreta/.
[8] D. Betten, Geometrische Permutationsgruppen, Mitt. Math. Gesellsch. Hamburg, 10 (1977),
317–324.
[9] I. Z. Bouwer, An edge but not vertex transitive cubic graph, Canad. Math. Bull. 11 (1968),
533–535.
[10] I. Z. Bouwer, Vertex and edge transitive but not 1-vertex transitive graphs, Canad. Math. Bull.
13 (1970), 231–237.
[11] D. R. Breach and A. P. Street, Partitioning sets of quadruples into designs, II, J. Combin. Math.
Combin. Comput. 3 (1988), 41–48.
[12] A. E. Brouwer, http://www.win.tue.nl/˜aeb/.
[13] A. E. Brouwer, Strongly regular graphs, in C. Colbourn and J. Dinitz (eds.), Handbook of
Combinatorial Designs, Discrete Mathematics and its Applications, chapter VII.11, pages 852–
867, CRC-Press, 2006.
[14] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-regular graphs, Springer-Verlag,
Berlin, 1989.
[15] A. E. Brouwer, J. H. Koolen and M. H. Klin, A root graph that is locally the line graph of the
Petersen graph. Discrete Math. 264 (2003), 13–24.
[16] A. E. Brouwer and H. A. Wilbrink, Ovoids and fans in the generalized quadrangle GQ(4, 2),
Meth. Centr. Report ZN 102, October 1981, Eindhoven.
[17] G. Butler and J. McKay, The transitive groups of degree up to 11, Comm. Algebra 11 (1983),
863–911.
[18] P. J. Cameron and J. H. van Lint, Designs, graphs, codes and their links, volume 22 of London
Mathematical Society Student Texts, Cambridge University Press, Cambridge, 1991.
[19] P. Dembowski, Finite Geometries, Reprint of the 1968 original, Classics in Mathematics,
Springer-Verlag, Berlin, 1997.
[20] L. E. Dickson and F. H. Safford, Solutions of Problems: Group Theory: 8, Amer. Math.
Monthly 13 (1906), 150–151.
[21] P. G. Doyle, A 27-vertex graph that is vertex-transitive and edge-transitive but not 1-transitive,
arxiv:math/0703861v1, 29 Mar 2007.
[22] S. Du, F. Wang and L. Zhang, An infinite family of semisymmetric graphs constructed from
affine geometries, Europ. J. Combin. 24 (2003), 897–902.
[23] S. A. Evdokimov and I. N. Ponomarenko, Rings associated to finite projective planes and their
isomorphisms, Zap. Nauchn. Sem. POMI 289 (2002), 207-213 (in Russian), English translation
in J. Math. Sci. (N. Y.) 124 (2004), 4792–4795.
[24] S. Evdokimov, I. Ponomarenko and G. Tinhofer, Forestal algebras and algebraic forests (on a
new class of weakly compact graphs), Discrete Math. 225 (2000), 149–172.
[25] I. A. Faradžev and M. H. Klin, Computer package for computations with coherent configura-
tions, in Proc. ISSAC-91, ACM Press, Bonn, 1991, pages 219–223.
[26] I. A. Faradžev, M. H. Klin and M. E. Muzichuk, Cellular rings and groups of automorphisms
of graphs, in I. Faradžev, A. Ivanov, M. Klin and A. Woldar (eds), Investigations in algebraic
theory of combinatorial objects, volume 84 of Math. Appl. (Soviet Ser.), pages 1–152, Kluwer
Acad. Publ., Dordrecht, 1994.
256 Ars Math. Contemp. 3 (2010) 237–258
[27] F. Fiedler and M. Klin, A strongly regular graph with the parameters (512, 73, 438, 12, 10)
and its dual graph, Preprint MATH-AL-7-1998, Technische Universität Dresden, July 1998.
[28] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.4.12, 2008,
http://www.gap-system.org.
[29] C. Godsil and G. Royle, Algebraic Graph Theory, Springer, Berlin Heidelberg New York,
2001.
[30] Ja. Ju. Gol’fand and M. H. Klin, On k-homogeneous graphs (Russian), Algorithmic Investiga-
tions in Combinatorics Moscow, Nauka, 1978, 76–85.
[31] A. Heinze, Applications of Schur rings in algebraic combinatorics: graphs, partial difference
sets and cyclotomic schemes, Ph.D. thesis, BIS C. v. O. Universität Oldenburg, 2001.
[32] A. Heinze and M. Klin, Links between Latin squares, nets, graphs and groups: work inspired
by a paper of A. Barlotti and K. Strambach, in: Workshop on Graph Asymmetries, volume 23
of Electron. Notes Discrete Math., Elsevier, Amsterdam, 2005, pages 13–21.
[33] A. Heinze and M. Klin, Loops, Latin squares and strongly regular graphs: An algorithmic
approach via algebraic combinatorics, in: M. Klin et al., Algorithmic Algebraic Combinatorics
and Gröbner Bases, Springer Verlag, Berlin Heidelberg, 2009, 3–65.
[34] M. D. Hestenes and D. G. Higman, Rank 3 groups and strongly regular graphs, Siam-AMS
Proe. IV (1971), 141–59.
[35] D. G. Higman, Coherent configurations, I, Rend. Sem. Mat. Univ. Padova 44 (1970), 1–25.
[36] D. G. Higman, Partial geometries, generalized quadrangles and strongly regular graphs, in Atti
del Convegno di Geometria Combinatoria e sue Applicazioni (Univ. Perugia, Perugia, 1970),
Ist. Mat., Univ. Perugia, Perugia, 1971, pages 263–293.
[37] D. G. Higman, Strongly regular designs and coherent configurations of type, [ 3 2
3
], Europ. J.
Combin. 9 (1988), 411–422.
[38] M. Hirasaka and M. Muzychuk, Association schemes generated by a non-symmetric relation
of valency 2, Discrete Math. 244 (2002), 109–135.
[39] A. J. Hoffman and R. R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. Res.
Develop., 4 (1960), 497–504.
[40] D. F. Holt, A graph which is edge transitive but not arc transitive, J. Graph Theory, 5 (1981),
201–204.
[41] A. A. Ivanov, I. A. Faradžev and M. H. Klin, The primitive representations of the non-abelian
simple groups of order less than 106, Part 2, Preprint, Inst. System Studies, Moscow, 1984
(Russian).
[42] L. K. Jørgensen and M. Klin, Switching of edges in strongly regular graphs, I, A family of
partial difference sets on 100 vertices, Electron. J. Combin. 10 (2003), #17.
[43] M. H. Klin, On edge but not vertex transitive graphs, Algebraic methods in graph theory,
Vol. I, II, Szeged, 1978, pages 399–403, Colloq. Math. Soc. Janos Bolyai 25, North-Holland,
Amsterdam-New York, 1981.
[44] M. Klin, N. Kriger and A. Woldar, Classification of highly symmetrical loops of order 2p, p a
prime, preprint.
[45] M. Klin, M. Muzychuk, C. Pech, A. Woldar and P.-H. Zieschang, Association schemes on
28 points as mergings of a half-homogeneous coherent configuration, Europ. J. Combin. 28
(2007), 1994–2025.
[46] M. Klin, M. Muzychuk and M. Ziv-Av, Computer algebra experimentation with Higmanian
rank 5 association schemes and related combinatorial objects, Technical Report, 92 pp.,
http://www.math.bgu.ac.il/˜zivav/math/
M. Klin et al.: Examples of computer experimentation in algebraic combinatorics 257
[47] M. Klin, M. Muzychuk and M. Ziv-Av. Higmanian rank-5 association schemes on 40 points,
Mich. Math. J. 58 (2009), 255–284.
[48] M. Ch. Klin, R. Pöschel and K. Rosenbaum, Angewandte Algebra für Mathematiker und
Informatiker, Einführung in gruppentheoretisch-kombinatorische Methoden (German), VEB
Deutscher Verlag der Wissenschaften, Berlin, 1988.
[49] M. Klin and S. Reichard, A partial linear space on 96 points, the icosahedron, and other related
combinatorial structures, Congr. Numer., 161 (2003), 195–209.
[50] M. Klin, S. Reichard and A. Woldar, Siamese combinatorial objects via computer algebra
experimentation, in: M. Klin et al. (eds), Algorithmic Algebraic Combinatorics and Gröbner
Bases, Springer, 2009, pp. 67–112.
[51] M. Klin, S. Reichard and A. Woldar, On a simple group of order 504, its automorphism group,
and related combinatorial structures, preprint.
[52] M. Klin, C. Rücker, G. Rücker and G. Tinhofer, Algebraic combinatorics in mathematical
chemistry, Methods and algorithms, I, Permutation groups and coherent (cellular) algebras,
Match 40 (1999), 7–138.
[53] M. Klin and M. Ziv-Av, A family of Higmanian association schemes on 40 points: A computer
algebra approach, in Algebraic Combinatorics. Proceedings of an International Conference in
Honor of Eiichi Bannai’s 60th Birthday, pp. 190–203, Sendai, Japan, June 26–30, 2006.
[54] F. Lazebnik and R. Viglione, An infinite series of regular edge- but not vertex-transitive graphs,
J. Graph Theory 41 (2002), 249–258.
[55] M. Mačaj and J. Širáň, Search for properties of the missing Moore graph, Linear Algebra Appl.
432 (2009), 2381–2398.
[56] D. Marušič and T. Pisanski, The Gray graph revisited, J. Graph Theory, 35 (2000), 1–7.
[57] D. Marušič, T. Pisanski and S. Wilson, The genus of the Gray graph is 7, Europ. J. Combin.
26 (2005), 377–385.
[58] R. Mathon, The partial geometries pg(5, 7, 3), Congr. Numer. 31 (1981), 129–139.
[59] R. Mathon and A. Rosa, A new strongly regular graph, J. Combin. Theory Ser. A 38 (1985),
84–86.
[60] B. D. McKay, nauty User’s Guide (Version 1.5), Department of Computer Science, Australian
National University, Canberra, 1990, http://cs.anu.edu.au/˜bdm/nauty/.
[61] B. Monson, T. Pisanski, E. Shulte and A. I. Weiss, Semisymmetric graphs from polytopes, J.
Combin. Theory A 114 (2007), 421–435.
[62] T. Pisanski, Yet another look at the Gray graph, New Zealand J. Math. 26 (2007), 85–92.
[63] S. Reichard, An algorithm for the construction of partial geometries with given point graphs,
Preprint MATH-AL-12-1997, Technische Universität Dresden, October 1997.
[64] T. Rudolph, Constructing physically intuitive graph invariants, Eprint, 2002,
http://arxiv.org/quant-ph/0206068.
[65] M. Schönert et al., GAP – Groups, Algorithms, and Programming – version 3 release 4 patch-
level 4, Lehrstuhl D für Mathematik, Rheinisch Westfälische Technische Hochschule, Aachen,
1997.
[66] I. Schur, Zur Theorie der einfach transitiven Permutationsgruppen, Sitzungsber. Preuss. Akad.
Wiss., Phys.-Math. Kl. (1933), 598–623.
[67] L. H. Soicher, The GRAPE package for GAP, Version 4.3, 2006,
http://www.maths.qmul.ac.uk/˜leonard/grape/.
258 Ars Math. Contemp. 3 (2010) 237–258
[68] W. T. Tutte, Connectivity in Graphs, Univ. Toronto Press, Toronto, 1966.
[69] B. Weisfeiler (ed.), On construction and identification of graphs, volume 558 of Lecture Notes
in Math., Springer, Berlin, 1976.
[70] B. J. Weisfeiler and A. A. Leman, A reduction of a graph to a canonical form and an algebra
arising during this reduction, Nauchno – Technicheskaja Informatsia, 9 (1968), 12–16, in
Russian.
[71] E. W. Weisstein, Doyle graph, Math World – A Wolfram Web Resource,
http://mathworld.wolfram.com/DoyleGraph.html/.
[72] S. Wilson, A worthy family of semisymmetric graphs, Discrete Math. 271 (2003), 283–294.
[73] M. Y. Xu, Half-transitive graphs of prime cube order, J. Algeb. Combin. 1 (1992), 275–282.
[74] M. Ziv-Av, Computer aided investigation of total graph coherent configurations for two infinite
families of classical strongly regular graphs, in: M. Klin et al. (eds), Algorithmic Algebraic
Combinatorics and Gröbner Bases, Springer, 2009, 297–311.