ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 14 (2018) 397-413 https://doi.org/10.26493/1855-3974.938.1ae
(Also available at http://amc-journal.eu)
On t-fold covers of coherent configurations
Alyssa D. Sankey
Department of Mathematics & Statistics, University of New Brunswick, P.O. Box4400, Fredericton, N.B., E3B 5A3, Canada
Received 15 September 2015, accepted 27 June 2017, published online 29 Qctober2017
We introduce the covering configuration induced by a regular weight defined on a coherent configuration. This construction generalizes the well-known equivalence of regular two-graphs and antipodal double covers of complete graphs. It also recovers, as special cases, the rank 6 association schemes connected with regular 3-graphs, and certain extended Q-bipartite doubles of cometric association schemes. We articulate sufficient conditions on the parameters of a coherent configuration for it to arise as a covering configuration.
Keywords: Association scheme, coherent configuration, regular weight, double cover, two-graph, t-graph.
Math. Subj. Class.: 05C22, 05C50, 05E30
1 Introduction
The Seidel matrix of a graph r may be viewed as a weight on the complete graph: edges of r are weighted (-1) and non-edges (+1). If r is strongly regular with n = 2(2k - A - p), it lies in the switching class of a regular two-graph and we call the weight, analogously, regular on Kn. This condition on r is well known, and dates to 1977, in [25]. The same year, the equivalence of regular two-graphs and antipodal double covers of complete graphs was established in [26].
Martin, Muzychuk and Williford ([18]) defined the extended Q-bipartite double of a cometric association scheme, extending the notion of the bipartite double of a distance regular graph. This construction produces, as special cases, the antipodal double covers of complete graphs from the strongly regular graphs affording regular two-graphs.
In recent work, Kalmanovich ([16]) has also generalized the regular two-graph result, working from an unpublished draft of D. G. Higman's ([9]) on regular 3-graphs. As defined in [14], a t-graph weights the edges of Kn with elements of the group of roots of unity of
E-mail address: asankey@unb.ca (Alyssa D. Sankey)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
179
Ars Math. Contemp. 14 (2018) 267-284
order t, Ut. The regularity condition ensures that the matrix of edge weights has a quadratic minimal polynomial. The work of Kalmanovich-Higman establishes the equivalence of regular 3-graphs with cyclic antipodal 3-fold covers of Kn ([6]). Regular 3-graphs are shown to give rise to certain rank 6 association schemes, and the necessary conditions under which a rank 6 scheme arises in this way are given.
In this paper there are two main results. First, working with a regular weight with values in Ut, defined on a coherent configuration (CC), we show that there is always a covering configuration; that is, a CC constructed using a t-fold cover in a natural way, to convert the weight into a CC of higher rank (by a factor of t). As special cases, we recover the equivalence between regular two-graphs and antipodal double covers of complete graphs; some extended Q-bipartite doubles of cometric schemes; the rank 6 schemes associated with regular 3-graphs, and an extension of these to regular t-graphs.
A CC with a regular weight has two sets of parameters: the structure constants for the weighted adjacency algebra, {pk }, which lie in C or more specifically in the ring of integers with a primitive tth root of unity adjoined, and the non-negative integers {pk (v)} which count certain triangles with a specified weight. They are related by
Pj = E vPj(v).
veUt
The weighted adjacency algebra is in general not a coherent algebra, and may in fact have a coherent closure that is much higher in rank than the original CC. In the regular two-graph case, for instance, it is precisely when the (-1) edges form an SRG that we get a minimal closure: a natural fission of the edge set into (+1) and (-1) edges that yields a (rank 3) association scheme. The covering configuration is the realization of a CC whose structure constants are the Pj (v). Some properties, namely homogeneity and commutativity of a CC carry over to the covering configuration. Symmetry is preserved only if t = 2. Metric and cometric properties are not.
The second main result of this paper is the articulation of sufficient conditions for a CC to be the covering configuration of a regular weight.
In the final section, we describe a family of regular weights on the Hamming Scheme H(n, 2) with values in U4, due to Ada Chan. These weights all fuse to regular 4-graphs, providing an infinite family that may be of interest as complex Hadamard matrices. These regular weights, and their fusions, admit covering configurations of ranks 4(n + 1) and 8 respectively, on 2n+2 points.
2 Preliminaries
In this section, we give the definitions that are essential to what follows. Much more can be found in [17] and in the original developments of the area by Weisfeiler and Lehman in [28] and by D. G. Higman in [11, 12], and [14].
2.1 Coherent configurations
Definition 2.1. Let {Ai}0<i<r be a set of 01-matrices with rows and columns indexed by a finite set X. Let I := {0,1,..., r}. The linear span A := (A^c is a coherent algebra if:
(i)	£ieI Ai = J, where J is the all-ones matrix,
(ii)	£ ie£ Ai = I, for some subset £cI,
A. D. Sankey: On t-fold covers of coherent configurations
399
(iii)	for each i there exists i* el such that Af = A*,
(iv)	AiAj = £pkjAfc, pkj e Z+.
A coherent algebra (CA), is homogeneous if |L| = 1; symmetric if i* = i for all i, and commutative, clearly, if pj = j for all i, j, k. The homogeneous CAs are (possibly non-symmetric) association schemes. Commutative schemes which have the metric or P-polynomial property are synonymous with distance-regular graphs (DRGs); those of diameter 2 are the strongly regular graphs (SRGs). Some familiarity with these structures is assumed. References for readers lacking this background are [1, 2,4, 5, 19], and [27]. In the association scheme literature, a rank r scheme is often referred to as an (r - 1)-class scheme: 'rank' counts the trivial relation, while the number of 'classes' does not.
Every algebra of n by n matrices over C that is closed under transpose and entry-wise multiplication, and contains both I and J is a coherent algebra, and as such it has a basis of 01-matrices satisfying (i)-(iv). Each Aj in a CA is the adjacency matrix of a digraph r with vertex set X, which is simple for i e L and a graph when i* = i. Viewing these graphs as relations on X, define a coherent configuration (CC) to be a set of binary relations on X, indexed by l, with analogous properties to (i)-(iv) above. Denote it A := (X, {Ri}ieI).
The constant p j counts the number of i-j paths from a vertex x to a vertex z, given that (x, z) e Rk and this number is necessarily independent of the choice of edge in rk. It is convenient to denote each instance of an i-j path by a triangle (x, y, z) of type (i, j, k). That is, (x, y, z) e X3 is a triangle of type (i, j, k) if (x, y) e Rj, (y, z) e Rj, and (x, z) e Rk as indicated in Figure 1.
Figure 1: Triangle (x, y, z) of type (i,j, k).
Define the intersection matrices Mj of a CC by Mj := (pj), 0 < i,k < r thus the map
Y : Aj ^ Mj
is the right regular representation of A.
We treat CAs and CCs as equivalent structures and move freely between the notations of matrices, relations, and graphs. As {Aj} forms the standard basis of A, we refer to {Rj} and {rj as the basic relations and basic graphs of A respectively.
k
2.2 Fusion and fission
A fusion is a merging of relations in a CC according to a partition of I. A fusion will be deemed coherent if the resulting configuration is coherent. A coherent fission or refinement is a partition of each basic relation such that the resulting set of relations forms a CC.
181
Ars Math. Contemp. 14 (2018) 267-284
The rank 2 CC represented by Kn is the minimum element in the lattice of all CCs on a given vertex set X of size n ([12, Prop. 3]). The maximum element has rank n2, with the full matrix algebra MX (C) as its coherent algebra.
2.3 Regular weights
Let U = Ut be the group of complex tth roots of unity, and fix a primitive root Z as the generator of U.
Definition 2.2. A weight with values in U is a 2-cochain w: X2 ^ U. Viewed as a matrix, a weight is Hermitian with unit diagonal.
The coboundary of w is a function on triangles:
Sw(x, y, z) := w(y, z)w(x, z)w(x, y)
and we refer to this value as the weight of the triangle (x,y,z). Analogous to Seidel switching on a graph, switching a weight w at vertex xi by a factor of a e U multiplies the weight on (xH, y) edges by a and on (y, x4) edges by a for all y = x^ In matrix form, this is a similarity transform by the diagonal matrix diag(1,1,..., 1, a, 1,..., 1) with a in position i. We refer to two weights as switching equivalent if one is obtained from the other by some sequence of switches, and observe that Sw is invariant under switching.
Definition 2.3. A t-graph is Sw for some weight w. It is regular if
|{y 1 Sw(x,y,z) = a}|
is independent of x and z, for each value a e U.
This is one of a number of natural generalizations of the regular two-graph ([9, 16, 22, 23, 24, 25]). Since a 2-cochain is equivalent to a weight on the edges of a complete graph, the notion of regularity can be extended to weights on CAs.
The entry-wise product w o Ai gives a matrix with (x, y) entry equal to w(x, y) where
(x, y) e Ri. Denote this weighted adjacency matrix A".
Definition 2.4 ([14]). A weight w is regular on a CC if for (x, z) e Rk the number of triangles (x, y, z) of type (i, j, k) and weight a is independent of x and z. In this case, the number of such triangles depends on i, j, k, and a and we denote this parameter (a).
If w is regular on A, then J2a 0ij (a) = pj. By a straight-forward counting argument,
A? A? = £ fij A? where := £ a^ (a)
k	aeU
thus A? := (A?} is a self-adjoint matrix algebra containing I and we refer to the fikjj as the parameters or structure constants of the A?. Note that this weighted adjacency algebra is not necessarily closed under the entry-wise product, hence it is not, in general, a coherent algebra. The weighted intersection matrices are defined in the obvious way,
Mj := (pj) , 0 < i,k <r.
Switching equivalent weights have identical parameters and therefore identical intersection matrices.
A. D. Sankey: On t-fold covers of coherent configurations
399
2.4 The fission induced by a weight
The weighted CC (A, w) has a natural fission in which R is partitioned according to distinct values of w. Put
i1 if (A-)xy = a;
(A?)a
Some useful properties are: 1. A? o Af = SijSa,pA?;
0 otherwise.
2. Ai
Ea Af;
3. A- = Ea aAf.
Definition 2.5. (A, w) has minimal closure if the fission {Af } forms a CC.
The terminology draws on the notion of the coherent closure of a set of matrices as the smallest CA containing them (see [21, 28] for more). The coherent closure of (A, w) is the CC whose CA is the coherent closure of the matrix algebra A-. Clearly
E A! = I
ieL
and the Af sum to J. Furthermore, by the Hermitian property of the weight,
(A?r
A
but the fission is not in general coherent and may in particular generate a matrix algebra of dimension greater than rt.
A weighted CC may be represented in a natural way as a t-fold cover of the configuration. The main goal of this work is to characterize regular weights on CCs in this way, and to describe the construction of a CC of rank rt - the covering configuration - derived from the cover.
Let U = Ut with generator Z, let r be a graph or digraph with vertex set X, and w a weight on r. Following [14], we define the t-fold cover of r afforded by w as follows. The vertex set is X x {1, 2,..., t}. We abuse notation, denoting the t copies of each vertex x by {xi, x2,..., xt}. Assign adjacencies by xH ~ y- whenever x ~ y in r and w(x, y) = . The induced permutation of indices, i ^ j determines a permutation a of U, namely Zk ^ Zk+j-i which is simply multiplication by ZLet Za be the image of a € U in the left regular representation of U as a multiplicative group. Then {Za | a G U} is a cyclic group generated by Z^ and the element Z^ corresponds to the kth power of the cycle (1, 2,..., t) on indices. Observe that J2Za is the all-ones matrix J. Indeed, the Za are the adjacency matrices of a cyclic group scheme on t points.
Example 2.6. We construct a weight with values in U3 on the cycle C3, a DRG of diameter 3. The non-trivial basic graphs are shown in Figure 2. Define a weight w by:
A"
a	a
a a a a a a a a a	a
A"
a a a a a	a
a	a
a a a a
183
Ars Math. Contemp. 14 (2018) 267-284
xi
xi
Xi
X4
X4
Figure 2: Distance graphs of C3.
A3 =
1
Working out the products, we see that
(Aï )2 = 21 + A33,
(A33 )2 = 21 + A33,
M A2
A1
A3 A3 a2 a3
A3 A3 = A3 A3 = A3 , A1 a3 = a3 A1 = a2 ;
^ 2
2
A3 A3 a3 a2
(A3 )2
and therefore the weighted intersection matrices are
A33,
M3
	1						1			1
2 0	0 1	1 0	0 2	, M3 =	0 2	1 0	0 1	2 0	, M33 =	1 1
		1				1				1
Note. Merging the non-trivial relations or, equivalently, summing Ai; i = 0, and also the A3, we see that this weight fuses to a regular 3-graph.
3 Main theorem
Theorem 3.1. Let A= (X, |Rj}ieI) be a coherent configuration of rank r on n := |X| vertices and suppose w is a regular weight on A with values in U = Ut. Then w induces a rank tr coherent configuration on tn vertices with relations given by
aeu
A°a < Zaa (i G I, a G U)
and parameters [ftk (a)}.
Proof. Let T := {1,2,..., t} and let r be one of the basic graphs in A. The t-fold cover of r that is induced by w has vertex set Y := X x T, and adjacency matrix
£ A? ® Za.
aeU
1
1
1
1
1
1
3
A. D. Sankey: On t-fold covers of coherent configurations
399
Motivated by this, and looking to define the matrices of a CA on Y, we put
Ci,a := £ A? < ,	(3.1)
aeu
for i el and a e U, we claim that C := (Cia }C is the coherent algebra of a CC C.
We show that C satisfies (i)-(iv) of Definition 2.1. We have observed that J2aeu Za J. Since J2aeu A? = Ai for all i, and J2iei Ai = J, we see that
EE Ci,a = EEE A? < Za
A a -
iei aeu	iei aeu aeu
(3.2)
= EE A? < E Zaa
Kiel aeu J \aeu J
= (E A^ < Jt
= Jn < Jt
= Jnt.
Hence C satisfies (i).
Let £CI be the unique set of indices such that J2 ie£ Ai = In. (Assume, without loss of generality, that L = {0} if A is homogeneous.) We claim Int = J2ie_c Ci,i. Since w(x, x) = 1 for all x, Af = 0 if i e L and a = 1. Consequently, i e L implies Ai = Ai. Hence,
E Ci,i = EE a? ® za
ieL	ieL a
= E Ai < Zo
ieL
(3.3)
= ^E Aij < It
= In < It = Int.
This proves that C satisfies (ii).
The transpose of M < N is MT < NT. Since w(y, x) = w(x,y), (Af )T = (Ai» )a. The transpose of a permutation matrix is its matrix inverse, hence ZT = Z-1 = Za-i. Therefore,
CTa = E Aa ® Z(aa)-1 = E A" < Za a = C^
a	a
thus C satisfies (iii).
Finally, we obtain the structure constants as follows. We claim:
( E A? < Zaa] ( E Af < ZT^ I = EE Pij (V) E (AY ® ZaTVY) . (3.4)
\a.eu	J \peu	J keiveu	7eu
185
Ars Math. Contemp. 14 (2018) 267-284
The left hand side of equation (3.4) is equal to
E	< (ZaoZTp) = ^ AfA^ < ZaTap
a,?eU	a,?eU
£ A«A? I < ZŒT^
p,eU	J
combining terms with the same second tensorand. We now consider the (x, z) entry of each product A^A? for a fixed (x, z) G Rk, setting 7 := w(x, z). This equals the number of triangles (x, y, z) of type (i,j, k) with weight afiY. Since we are summing these products over all a and fi with a/3 = we account for all such triangles, and the number of these
is fik (afiY). Thus
E I E I ® z^ = E IE E 4 (my)ay ) ® zaT,
meu \af3=n j	^eu \-yeu hex	j	(3.5)
= EEE 4 (m7 ) (Ah ® z^m) .
^eu-yeu hex
Next, observe that fih (v) occurs exactly t times, once for each 7 with m = vj. Factoring gives
EE 4 (v) E Ah ® Z^	(3.6)
hex veu -yeu
which proves the claim. Hence (v) is the coefficient of ChjaTV in the product Ci<aCj,T.
' ' □
Remark 3.2. If A is an association scheme, then L = {0}, and C0ji = Int. Remark 3.3. The following are clear from the proof of Theorem 3.1.
(i)	C is homogeneous if and only if A is homogeneous.
(ii)	C is symmetric if and only if A is symmetric and w is real-valued, that is, t = 2. Ci1 is always symmetric if Ai is.
(iii)	C is commutative if and only if A is commutative.
(iv)	If the Aa form a CC, then we are in the case of minimal closure, and C is a fusion of a Kronecker product configuration.
(v)	The parameter fthj (v) in the proof of (iv) clearly does not depend on a or t. This means that each parameter of C is duplicated t2 times:
nhtrTv = phv ya t (Z TT Pia,jT = Pi1,j1 "a,T G Ut.
4 Discussion and analysis
Example 4.1. This example relates to r = SRG(112, 30 , 2 ,10) which is known by many names in the literature, including the collinearity graph of GQ(3 , 9), O-(6 , 3), and the
A. D. Sankey: On t-fold covers of coherent configurations
399
first sub-constituent of the McLaughlin graph, McLi to name just three. It has a strongly regular decomposition into two Gewirtz graphs (SRG(56,10,0,2)) [7].
Let A be the rank 3 scheme afforded by r. We construct a regular weight on A with values in U2, making use of the decomposition. Let X1 and X2 be the two sets of 56 vertices. Define w(x, y) for x = y to be —1 when x and y are in the same half of this partition, and +1 otherwise. Note that w restricted to either Gewirtz graph is a trivial weight with matrix 21 — J.
Xi	X2
Figure 3: Strongly regular decomposition of SRG(112,30,2,10).
In Figure 3, a solid line indicates adjacency in r, a dotted line non-adjacency. This weighted SRG has minimal closure, since the A® form a rank 5 scheme, in fact a strongly regular design or SRD ([13]). Since w(x, y) is determined by the parity of {x, y} n X1, the four non-trivial relations are given by the four combinations of attributes: adjacency/non-adjacency, and this parity. There are many related configurations. For example, another copy of the Gewirtz graph may be adjoined to construct an example of triality ([15]). These 112 vertices form the first subconstituent of the McLaughlin graph; the second subconstituent also admits a strongly regular decomposition ([3]).
Some interesting properties of this example:
1.	Minimal closure is rare (see [21]).
2.	The SRD is cometric, but not metric, which is also rare.
3.	The covering configuration C is also cometric, but not metric, having rank 6 on 224 points. This example arises as the Q-bipartite double of McL1 (see [18]).
The Gewirtz graph admits a non-trivial regular weight with values in U4, constructed via a monomial representation of 2.L3(4) ([20]). The covering configuration is neither metric nor cometric, has rank 12 on 224 vertices, and contains the doubled Gewirtz graph (DRG[10, 9,8,2,1; 1, 2,8,9,10]) as a quotient.
187
Ars Math. Contemp. 14 (2018) 267-284
4.1 Intersection matrices
Lemma 4.2. The intersection matrices of C have the form MjT = ^^ Mj < ZTV where
ML := $ (v).
Proof. We may assume the relations Ci( are ordered lexicographically, that is first by i and then by a G {1, Z,..., Zt-1} so that the intersection matrix MjT has (i, k) block given by aTv. By equation (3.6) this block has the value ^j (v) in position (a, arv) which
means that it has the form J2v Pij(v)ZTV. Hence MjT is the required sum of Kronecker products.	□
Lemma 4.3. Let w be a regular weight on the cc A, and let w be an equivalent weight obtained by switching w by a factor of t = Z1 at vertex x. Further let C = (Y, {Ci( }) and C = (Y, {Ci(}) be the covering configurations induced by w and w respectively. Then € is obtained from C by permuting {xi} according to the permutation (1, 2,..., t)1 resulting from multiplication by t on U.
Proof. Suppose w(x, y) = a. For some i and j, (x1,yj) G Ci1 of C, thus a = Zj-1. Now, w(x, y) = Ta by assumption, so we have (x1-1, yj) G (Ji1. But this implies that C is obtained from C by the permutation x ^ x1-1, which corresponds to multiplication by t on U.	□
4.2 Special cases
(i)	If w has minimal closure, C is a fusion of a tensor product of two CCs.
(ii)	If w is trivial in the sense that A® = 0 for all but one value of a, w has minimal closure, and C = A" < Z.
(iii)	If A has rank 2 (w is regular on Kn), C is a t-fold cover of Kn. It is not necessarily distance regular. This case encompasses the regular two-graphs (t = 2), and the regular 3-graphs (t = 3) of Higman [9] and Kalmanovich [16].
(iv)	If t = 2, A is a (symmetric) scheme, and A" has minimal closure (say B, where B = (X, {Bi})), then the covering configuration is isomorphic to the extended Q-bipartite double of B, when it exists, if the rank of B is odd ([18, 3.1]). Existence requires B to be cometric with an additional condition on the Krein parameters. For even rank, the covering configuration has a fusion (merging just two classes) that is isomorphic to the extended Q-bipartite double, provided that there is exactly one class of A on which w is constant. Note that a minimal closure of a weight with values in U2 has even rank only when the weight is constant on an odd number of classes of A. The isomorphism is M < N ^ N < M on the Ci( of the cover configuration.
4.2.1 Necessary conditions for a covering configuration
In the case of commutative CCs we extend [16, Prop. 5.4] in a natural way, as follows.
Let C = (X, {Rj}) be a commutative CC of rank tr such that the first t intersection matrices have the form Mj = Ir < Zj, for 0 < j < t, and let U = (Z} the group of roots of unity of order t. Index the relations according to the r blocks of size t, so that
Ci,Zk = Rit+k
A. D. Sankey: On t-fold covers of coherent configurations
399
and suppose that for any i, j, k and v:
Pia,jr pi1,j1
for all a and t in U. We intend to show that under these conditions, C must arise as the covering configuration of a regular weight on a quotient of C.
Lemma 4.4. If j < t and pk _ 0, then k _ i + j (mod t); in particular, i and k lie in the same block of Mj.
Proof. This follows from Mj = I <g> ZC3.	□
Observe that E := ujis a parabolic in the sense of [10]. Indeed, M0 = Irt implies that R0 is the identity relation of C. Further, E is symmetric, since (x, y) G R for i < t implies that p0, j = 0, so i* is in the same block of Mj as 0. That is, (y, x) G E. Given (x, y) G Rj and (y, z) G Rj with 0 < i, j < t, we see that (x, z) G Rk for some k < t, because k must lie in the same block of Mj as i, since all non-diagonal blocks are zero. Hence, E is a transitive relation.
As a parabolic, E induces an equivalence relation on the indices: If there exist x, x', y, y' G X such that (x, x') G E, (y, y') G E, (x,y) G Rj and (x',y') G Rj, then i ~ j. Write [i] for the equivalence class of i. In addition, the parabolic affords a quotient (homogeneous) configuration A := (X, {R[j]}) with an associated partition of the vertex set X into fibres of size t. The fibre containing x is
[x] = {y | (x, y) G E}.
We will henceforth suppress the bracket notation for fibres, writing x = {xi, x2,... xt}.
For j G [0], Lemma 4.4 implies that pkj = 0 for j = 0. But then Rk restricted to x x y has valency at most 1. We conclude that the number of relations occurring between any two fibres is t. We have: For k G I and x G X,
|[k]| = |x| = t.
Denoting the graph of Rj by rj, we have proved the following:
Lemma 4.5. For all j G [0], rj is a t-fold cover of r^.
Corollary 4.6. The natural partition of I according to blocks of Mj, for 0 < j < t is the same as that determined by the equivalence classes of the parabolic. That is,
[mt] = {mt, mt + 1,. .., mt + t — 1}.
Proof. Suppose j G [i] so that there exist xi,x2,yi,y2 G X with (xi,yi) G Rj and (x2,y2) G Rj. Then, by the discussion above, (xi,y3) G Rj for some y3 G y and therefore pjk = 0 for some k < t.
But then j = i + k (mod t) by Lemma 4.4.	□
Recall that C0jzfc = Rk for k < t, C0jCT has intersection matrix Ir<g>ZCT, and Cmji = Rmt for 0 < m < r. Fix a fibre a (from here on), and order it so that (aj, aj+i) G , for each i, with addition modulo t. This ensures that the perfect matching induced on a corresponds
189
Ars Math. Contemp. 14 (2018) 267-284
to the permutation (1,2,...,t) on indices, which in turn corresponds to the permutation of U induced by multiplication by Z.
For each x G X, (a, x) G R[mt] for some m. Order x so that (aj, Xj) G Cm i. In what follows, we mix the notations regarding indexation of the relations of C. Where two indices are given, we refer to as above; where one index is given we refer to the original numbering of the relations.
Lemma 4.7. With notation as above, (x», xi+i) G for all x G X.
Proof. For some a, (xj, xj+i) e C0jCT; (a», xj+i) G R; for some l, and (a», xj) G Rmi for some m. Note that l G [m]. Since a», aj+1, and xj+1 form a triangle of type (0Z, ml, l),
we see that p0z m1 = 0. Since C is commutative, R; = by Lemma 4.4. Now observe that a», x», and xj+1 form a triangle of type (ml, 0a, mZ), and therefore a = Z.	□
Next, following [16] we show that all matchings are cyclic.
Lemma 4.8. With notation as above, all matchings between fibres of C are cyclic.
Proof. Suppose that (x», yj) G Rk and (x»+1, y;) G Rk. We must show that l = j + 1. The triangle (x», x»+1, yj) has type (1, m, k) for some m, indicating that pkm = 0. As in the previous lemma, this implies that k = m + 1. On the other hand, the triangle (x»+1, y;-1, y;) has type (b, 1, k) for some b, hence k = b +1. But then m = 6, and by Lemma 4.5, y;-1 = yj as desired.	□
Corollary 4.9. For all x G X, (x», x.j+k) G Rk, thus Rk induces on each fibre the perfect matching corresponding to the kth power of the cycle (1, 2,..., t).
Proof. The result follows by Lemma 4.7 and induction (on k) applied to the triangles
(x» —fc^x»^) .	□
Lemma 4.10. For x G X, (a^x^) G Rmt+fc for 0 < k < t.
Proof. The case k = 0 holds by choice of ordering of x. Induction applied to the triangles
(aj, ^^k —^ ) gives the desired result.	□
We now define a weight on A by means of . Let x, y G X and suppose (x, y) G Rj. Then Cj,1 provides a cyclic matching between x and y corresponding to, say, a G U. Set w(x, y) := a. Observe that w(a, x) = 1 for all x.
The next lemma shows how to determine the weight of an edge in r^] from any edge in r».
a» l x»+1
a» l x»+1
Figure 4: Triangles (a», a»+1, x»+1) and (a», x», x»+1).
A. D. Sankey: On t-fold covers of coherent configurations
399
Lemma 4.11. If (xi; yj) G Cka, then w(x, y) = aÇj i.
Proof. Consider (xi;yj) G CkjCT. Let l be such that (xi;y;) G Ck1 and note that the triangle (xi; y;, yj) has type (kl, 0Zj—ka). By Proposition 4.6, a = Zj-;. This implies that (xj, y;+m) G Cfcjzm. We conclude that the matching between x and y in CkjCT is aa, where a = w(x, y).	□
We now prove the second main result which is the extension of [16, Prop. 5.4].
Theorem 4.12. Let C = (X, {Rj}) be a commutative CC of rank rt with the first t intersection matrices given by
Mj = Ir <g) Zj 0 < j < t,
where U = Ut = (C} is the group of roots of unity of order t. Label the relations according to the blocking of Mj :
Cj^fc := Rit+k 0 < i < r, 0 < k < t and suppose that the CC parameters satisfy, for any i, j, k and v:
karv _ pkv
Pia,jr Pi 1 ,j 1
for all a and t in U. Then C arises as the covering configuration (in the sense of Theorem 3.1) from a regular weight w on the quotient scheme A = C/E.
Proof. From the discussion and lemmas above, what remains to be shown is that w is regular on the quotient configuration C = (X, {R[i]}). Let (x, z) G R[k]. We consider all y such that (x, y, z) has type (i, j, k) and weight v. Let l be such that (x1, z;) G Ckv. If (x, y) G R[i] and (y, z) G Rj], then (x1,ym) G Ci1 for some m, and this determines (exactly one) t with (ym, z;) G CjT. By Lemma 4.11,
Jw(x, y, z) = w(x, y)w(y, z)w(x, z)
= Cm-1TC;-mvC1-;
from which we see that triangles of weight v occur exactly when t = 1. These triangles are counted by the parameter pkj which is independent of the choice of x1 and z;. □
Note that in the proof above we are counting distinct y, and that for each y there is exactly one ym as indicated. Thus we may use Ci1 without loss of generality, since (x1, ym) G Cia would yield the same result. In fact triangles of type (ia, jT, kv) will have weight v exactly when aT =1, which is expected as in that case pkj = Pa,j1
5 Examples
5.1 A rank 12 scheme on 18 points
The covering configuration of Example 2.6 has rank 12 (= 4 • 3) on 18 (= 6 • 3) points. It is isomorphic to as18[88] on Hanaki and Izumi's list ([8]).
397
Ars Math. Contemp. 14 (2018) 267-284
5.2 A family of CCs from regular weights on H(n, 2) with values in U4
This construction is due to Ada Chan (personal communication). We define a regular weight on the Hamming Scheme H(n, 2) with values in U4 with generator i. Let t be
0 1"
an indeterminate, and K the 2 by 2 matrix ^ ^ in t with coefficients in the ring of matrices M2,2(
. Form (1 + tK)0n, a polynomial


Now let A" be
the coefficient of t , scaled by a factor of ik G U4. We claim this is a regular weight on the Hamming scheme. Indeed, replacing i with 1 and K with J - 1 in this process yields the adjacency matrices of the Hamming scheme, with the standard P-polynomial ordering. Noting that K2 = -1 it is straight-forward to see that Span(A" ) is coherent. For regularity, we note that p j is nonzero only when i + j + k is even, and this implies ^ j (±i) = 0 for all i, j, k. Proposition 1 of [21] applies, and we conclude that w is regular.
The covering configuration induced by this weight is a rank 4(n +1) CC on 2n+2 vertices. There is a fusion to regular 4-graph, which is easily seen: replace t by i, setting
W := (1 + iK)0n,
then verify directly that W2 = 2nW thus W is the matrix of a regular 4-graph. The covering configuration of W has rank 8 and is symmetric, but not necessarily distance regular. For n = 2, the weight is given by:
A" =
0	i i	0
-i	0	0	i
-i	0	0	i
0	-i	-i	0
and A"
0 0	0	1
0 0	-10
0	-1	0 0
1 0	0	0
The rank 12 covering configuration has color matrix (^ iAj) below.
0	1	2	3	7	4	5	6	7	4	5	6	8	9	10	11
3	0	1	2	6	7	4	5	6	7	4	5	11	8	9	10
2	3	0	1	5	6	7	4	5	6	7	4	10	11	8	9
1	2	3	0	4	5	6	7	4	5	6	7	9	10	11	8
5	6	7	4	0	1	2	3	10	11	8	9	7	4	5	6
4	5	6	7	3	0	1	2	9	10	11	8	6	7	4	5
7	4	5	6	2	3	0	1	8	9	10	11	5	6	7	4
6	7	4	5	1	2	3	0	11	8	9	10	4	5	6	7
5	6	7	4	10	11	8	9	0	1	2	3	7	4	5	6
4	5	6	7	9	10	11	8	3	0	1	2	6	7	4	5
7	4	5	6	8	9	10	11	2	3	0	1	5	6	7	4
6	7	4	5	11	8	9	10	1	2	3	0	4	5	6	7
8	9	10	11	5	6	7	4	5	6	7	4	0	1	2	3
11	8	9	10	4	5	6	7	4	5	6	7	3	0	1	2
10	11	8	9	7	4	5	6	7	4	5	6	2	3	0	1
9	10	11	8	6	7	4	5	6	7	4	5	1	2	3	0
The regular 4-graph W := 1 + A" + A" satisfies W2 = 41. The covering configuration of W has rank 8 and may also be obtained through fusion of the rank 12 above.
In summary, this construction gives regular weights with values in U4 on the Hamming Schemes H(n, 2). These have rank n +1 on 2n vertices. The covering configurations thus
A. D. Sankey: On t-fold covers of coherent configurations
399
have rank 4(n +1) on 2n+2 vertices. These weights fuse to regular 4-graphs always, and the covering configurations of those have rank 8. In examples constructed to date, the covering configurations are not metric, nor are their symmetrizations, and they are not cometric.
5.3 CCs afforded by groups
A CC may have relations determined by the orbitals of a group G acting on a set X, in which the centralizer algebra of the natural permutation representation is the coherent algebra A. In this case, a regular weight may exist such that A" is the centralizer algebra of a monomial representation of G, induced from a linear representation of a point stabilizer ([14]).
For example, the rank 3 scheme containing the Petersen graph is afforded by the action of A5 on 2-sets from {1,2,3,4, 5}. The stabilizer of {1, 2} is a group H ~ S3, containing A := (3,4, 5} as a subgroup of index 2. This index determines that the monomial representation will afford a weight with values in U2. Defining the linear representation
t: H ^ C2 by ¿(<7)=^ g £ A
[-1 g £ A,
i G
the induced representation M := is a monomial representation of G. The M(g) for g G G are signed permutation matrices. The centralizer algebra of M, A", defines a regular weight on the Petersen graph.
This construction can be done in general when the point stabilizer H has a normal subgroup A of index t, such that H/A ~ Ct. The monomial representation induced may or may not afford a nontrivial regular weight on the underlying CC.
In this example, the covering configuration C is a rank 6 scheme on 20 points, in fact the unique (antipodal, non-bipartite) distance-regular graph DRG{3,2,1,1,1; 1,1,1, 2,3}, that is the dodecahedron graph. (It is not the bipartite double of the Petersen graph, which is DRG{3, 2, 2,1,1; 1,1, 2, 2, 3}.)
We obtain a permutation representation from M, via
M(g) ^ M +(g) <g> Zi + M-(g) <g> Z2
where M +, MZ1 and Z2 are defined as in Section 2. It is natural to ask whether C is the centralizer algebra of this permutation representation. In fact, C is properly contained in this centralizer algebra. It affords a CC with valencies 1, 1, 3, 3, 3, 3, 3, 3 which has a fusion to C. The group affording C is A5 x C2, an extension of our group G by the cyclic C2, the latter generated by the even permutation interchanging each x1 and x2. This is of course the symmetry group of the dodecahedron and is not isomorphic to S5.
References
[1]	E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, The Ben-jamin/Cummings Publishing Company, Menlo Park, California, 1984.
[2]	A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, volume 18 of Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer-Verlag, Berlin, 1989, doi: 10.1007/978-3-642-74341-2.
[3]	P. J. Cameron, J. M. Goethals and J. J. Seidel, Strongly regular graphs having strongly regular subconstituents, J. Algebra 55 (1978), 257-280, doi:10.1016/0021-8693(78)90220-x.
413
Ars Math. Contemp. 14 (2018) 267-284
[4]	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, doi:10.1017/cbo9780511623714.
[5]	C. D. Godsil, Algebraic Combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993.
[6]	C. D. Godsil and A. D. Hensel, Distance regular covers of the complete graph, J. Combin. Theory Ser. B 56 (1992), 205-238, doi:10.1016/0095-8956(92)90019-t.
[7]	W. H. Haemers and D. G. Higman, Strongly regular graphs with strongly regular decomposition, Linear Algebra Appl. 114-115 (1989), 379-398, doi:10.1016/0024-3795(89)90471-0.
[8]	A. Hanaki and I. Miyamoto, Classification of association schemes with small vertices, http: //math.shinshu-u.ac.jp/~hanaki/as/ (accessed in August 2015).
[9]	D. G. Higman, A note on regular 3-graphs, unpublished draft (7 pages).
[10]	D. G. Higman, The parabolics of a semi-coherent configuration, unpublished draft (18 pages).
[11]	D. G. Higman, Coherent configurations I: Ordinary representation theory, Geometriae Dedicata 4 (1975), 1-32, doi:10.1007/bf00147398.
[12]	D. G. Higman, Coherent algebras, Linear Algebra Appl. 93 (1987), 209-239, doi:10.1016/ s0024-3795(87)90326-0.
"3 2"
[13]	D. G. Higman, Strongly regular designs and coherent configurations of type 3 , Eur. J. Combin. 9 (1988), 411-422, doi:10.1016/s0195-6698(88)80072-6.
[14]	D. G. Higman, Weights and t-graphs, Bull. Soc. Math. Belg. Ser. a 42 (1990), 501-521.
[15]	D. G. Higman, Rank 5 association schemes and triality, Linear Algebra Appl. 226-228 (1995), 197-222, doi:10.1016/0024-3795(95)00102-w.
[16]	D. Kalmanovich, On D. G. Higman's note on regular 3-graphs, Ars Math. Contemp. 6 (2013), 99-115,http://amc-journal.eu/index.php/amc/article/view/2 4 3.
[17]	M. Klin, A. Munemasa, M. Muzychuk and P.-H. Zieschang, Directed strongly regular graphs obtained from coherent algebras, Linear Algebra Appl. 377 (2004), 83-109, doi:10.1016/j.laa. 2003.06.020.
[18]	W. J. Martin, M. Muzychuk and J. Williford, Imprimitive cometric association schemes: Constructions and analysis, J. Algebraic Combin. 25 (2007), 399-415, doi:10.1007/ s10801-006-0043-2.
[19]	W. J. Martin and H. Tanaka, Commutative association schemes, Eur. J. Combin. 30 (2009), 1497-1525, doi:10.1016/j.ejc.2008.11.001.
[20]	A. D. Sankey, Regular weights of full rank on strongly regular graphs, Israel J. Math. 95 (1996), 1-23, doi:10.1007/bf02761032.
[21]	A. D. Sankey, Weighted association schemes, fusions, and minimal coherent closures, J. Algebraic Combin. 41 (2015), 785-815, doi:10.1007/s10801-014-0553-2.
[22]	J. J. Seidel, A survey of two-graphs, in: Colloquio Internazionale sulle Teorie Combinatorie (Rome, Italy, 1973), Tomo I, Accademia Nazionale dei Lincei, Rome, volume 17 of Atti dei Convegni Lincei, pp. 481-511, 1976.
[23]	J. J. Seidel, More about two-graphs, in: J. Nesetril and M. Fiedler (eds.), Fourth Czechoslo-vakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990), North-Holland, Amsterdam, volume 51 of Annals of Discrete Mathematics, pp. 297-308, 1992, doi: 10.1016/s0167-5060(08)70646-0.
A. D. Sankey: On t-fold covers of coherent configurations
399
[24]	J. J. Seidel and D. E. Taylor, Two-graphs, a second survey, in: L. Lovasz and V. T. S6s (eds.), Algebraic Methods in Graph Theory, Volume II, North-Holland, Amsterdam, volume 25 of Colloquia Mathematica Societatis Jdnos Bolyai, pp. 689-711, 1981.
[25]	D. E. Taylor, Regular 2-graphs, Proc. London Math. Soc. 35 (1977), 257-274, doi:10.1112/ plms/s3-35.2.257.
[26]	D. E. Taylor and R. Levingston, Distance-regular graphs, in: D. A. Holton and J. Seberry (eds.), Combinatorial Mathematics, Springer, Berlin, volume 686 of Lecture Notes in Mathematics, 1978 pp. 313-323, proceedings of the International Conference on Combinatorial Theory (Australian National University, Canberra, 16-27 August 1977).
[27]	E. R. van Dam, J. H. Koolen and H. Tanaka, Distance-regular graphs, 2016, arXiv:1410.6294 [math.CO].
[28]	B. Yu. Weisfeiler and A. A. Lehman, Reduction of a graph to a canonical form and an algebra which appears in the process, Nauchno-Tekhnicheskaya Informatsiya Ser. 2 9 (1968), 12-16.