On small world non-Sunada twins and cellular Voronoi diagrams
Special infinite families of regular graphs of unbounded degree and of bounded diameter (small world graphs) are considered. Two families of small world graphs Gi and Hi form a family of non-Sunada twins if Gi and Hi are isospectral of bounded diameter but groups Aut(Gi) and Aut(Hi) are nonisomorphi...
Gespeichert in:
| Datum: | 2020 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2020
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/188557 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | On small world non-Sunada twins and cellular Voronoi diagrams / V. Ustimenko // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 1. — С. 118–142. — Бібліогр.: 37 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188557 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1885572023-03-06T01:27:24Z On small world non-Sunada twins and cellular Voronoi diagrams Ustimenko, V. Special infinite families of regular graphs of unbounded degree and of bounded diameter (small world graphs) are considered. Two families of small world graphs Gi and Hi form a family of non-Sunada twins if Gi and Hi are isospectral of bounded diameter but groups Aut(Gi) and Aut(Hi) are nonisomorphic. We say that a family of non-Sunada twins is unbalanced if each Gi is edge-transitive but each Hi is edge-intransitive. If all Gi and Hi are edge-transitive we have a balanced family of small world non-Sunada twins. We say that a family of non-Sunada twins is strongly unbalanced if each Gi is edge-transitive but each Hi is edge-intransitive. We use term edge disbalanced for the family of non-Sunada twins such that all graphs Gi and Hi are edge-intransitive. We present explicit constructions of the above defined families. Two new families of distance-regular—but not distance-transitive—graphs will be introduced. 2020 Article On small world non-Sunada twins and cellular Voronoi diagrams / V. Ustimenko // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 1. — С. 118–142. — Бібліогр.: 37 назв. — англ. 1726-3255 DOI:10.12958/adm1343 2010 MSC: 05C50, 05C82, 51E24 http://dspace.nbuv.gov.ua/handle/123456789/188557 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
Special infinite families of regular graphs of unbounded degree and of bounded diameter (small world graphs) are considered. Two families of small world graphs Gi and Hi form a family of non-Sunada twins if Gi and Hi are isospectral of bounded diameter but groups Aut(Gi) and Aut(Hi) are nonisomorphic. We say that a family of non-Sunada twins is unbalanced if each Gi is edge-transitive but each Hi is edge-intransitive. If all Gi and Hi are edge-transitive we have a balanced family of small world non-Sunada twins. We say that a family of non-Sunada twins is strongly unbalanced if each Gi is edge-transitive but each Hi is edge-intransitive. We use term edge disbalanced for the family of non-Sunada twins such that all graphs Gi and Hi are edge-intransitive. We present explicit constructions of the above defined families. Two new families of distance-regular—but not distance-transitive—graphs will be introduced. |
| format |
Article |
| author |
Ustimenko, V. |
| spellingShingle |
Ustimenko, V. On small world non-Sunada twins and cellular Voronoi diagrams Algebra and Discrete Mathematics |
| author_facet |
Ustimenko, V. |
| author_sort |
Ustimenko, V. |
| title |
On small world non-Sunada twins and cellular Voronoi diagrams |
| title_short |
On small world non-Sunada twins and cellular Voronoi diagrams |
| title_full |
On small world non-Sunada twins and cellular Voronoi diagrams |
| title_fullStr |
On small world non-Sunada twins and cellular Voronoi diagrams |
| title_full_unstemmed |
On small world non-Sunada twins and cellular Voronoi diagrams |
| title_sort |
on small world non-sunada twins and cellular voronoi diagrams |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2020 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188557 |
| citation_txt |
On small world non-Sunada twins and cellular Voronoi diagrams / V. Ustimenko // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 1. — С. 118–142. — Бібліогр.: 37 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT ustimenkov onsmallworldnonsunadatwinsandcellularvoronoidiagrams |
| first_indexed |
2025-07-16T10:39:47Z |
| last_indexed |
2025-07-16T10:39:47Z |
| _version_ |
1837799716956405760 |
| fulltext |
“adm-n3” — 2021/1/4 — 9:14 — page 118 — #124
© Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 30 (2020). Number 1, pp. 118–142
DOI:10.12958/adm1343
On small world non-Sunada twins
and cellular Voronoi diagrams
V. Ustimenko
Communicated by V. M. Futorny
Abstract. Special infinite families of regular graphs of
unbounded degree and of bounded diameter (small world graphs)
are considered. Two families of small world graphs Gi and Hi form a
family of non-Sunada twins if Gi and Hi are isospectral of bounded
diameter but groups Aut(Gi) and Aut(Hi) are nonisomorphic.
We say that a family of non-Sunada twins is unbalanced if each
Gi is edge-transitive but each Hi is edge-intransitive. If all Gi and
Hi are edge-transitive we have a balanced family of small world
non-Sunada twins. We say that a family of non-Sunada twins is
strongly unbalanced if each Gi is edge-transitive but each Hi is
edge-intransitive.
We use term edge disbalanced for the family of non-Sunada twins
such that all graphs Gi and Hi are edge-intransitive. We present
explicit constructions of the above defined families. Two new families
of distance-regular—but not distance-transitive—graphs will be
introduced.
Introduction
As everybody knows, the answer to the famous question, “Can you
hear the shape of a graph?” is negative. In this paper we would like to
stress that in fact we are so deaf that we are unable to recognise orchestras
2010 MSC: 05C50, 05C82, 51E24.
Key words and phrases: Laplacians, isospectral graphs, small world graphs,
distance-regular graphs, non-Sunada constructions, graph Voronoi diagram, thin Voronoi
cells.
https://doi.org/10.12958/adm1343
“adm-n3” — 2021/1/4 — 9:14 — page 119 — #125
V. Ustimenko 119
of large families of small world graphs. Two nonisomorphic families can
produce the same symphony in absolutely identical manner.
In [1] Sunada presented a method of constructing pairs of nonisometric
manifolds {M1,M2} such that the eigenvalues of the Laplace operator
satisfy λi(M1) = λi(M2) for all i. His method was based on interpreting
the isospectral condition in terms of finite group theory: if G is a finite
group acting freely on a manifold MG, with M1 and M2 quotients of MG
by subgroups H1 and H2 respectively, then M1 and M2 will be isospectral
if the induced representations (1H1
)G and (1H2
)G are equivalent (here
1X denotes the trivial representation of the group X). If Γ1 and Γ2 are
two graphs, then one may define a Laplacian on them and ask whether
they are isospectral. As it is written in [2] “There are many constructions
of isospectral graphs which appear to have little to do with the Sunada
construction, see [3] for survey. However if we imposed the condition that
Γ1 and Γ2 are k-regular, which is a natural condition to impose from
the point of view of geometry, then most of these constructions do not
apply. An exception to this is the construction of Seidel switching ([3]).”
In fact, some other constructions of isospectral distance-regular graphs of
non-Sunada nature were already known and presented in [4]. In particular,
Hemmeter’s [5] and Ustimenko’s [6] examples of distance-regular, but not
distance-transitive, graphs via new constructions of infinite families of
isospectral pairs of graphs were reflected in [4]. In fact, we now have other
examples of isospectral graphs due to recent progress in Distance-Regular
Graph Theory (see [7]).
The purpose of this paper is to draw attention of specialists in applied
graph theory to the fact that the theory of Tits geometries over Dynkin-
Coxeter diagrams Bn and Cn provides remarkable examples of infinite
sequences of non-Sunada isospectral pairs of graphs which form families of
small world graphs. Note that a similar situation has occurred in Extremal
Graph Theory; no earlier than seven years after Tits’ initial formulation
of finite regular generalised polygons [9] would Benson [8] come to observe
that these objects achieve the upper bound in the Even Circuit Theorem
of Erdős.
We conjecture that many other families of small world non-Sunada
twins can be defined via Borel subgroups and partitions of largest Schubert
cells into special “medium” Schubert cells.
Two new families of distance-regular, but not distance-transitive, graphs
are here introduced.
Finally we introduce the concept of a thin Voronoi cell connected
with the notion of a Voronoi graph diagram. Nice examples of Voronoi
“adm-n3” — 2021/1/4 — 9:14 — page 120 — #126
120 On small world non-Sunada twins
cells of geometric nature are thin Schubert cells. It is interesting that
isospectrality of small world graphs described in this paper can be easily
explained via similarity of cellular Voronoi diagrams.
Two families of distance-transitive graphs defined in terms of Lie
geometry form pairs of non-Sunada twins. Let Γ(Bn(q))i and Γ(Cn(q))i be
the totalities of elements of the respective geometries of Chevalley groups
Bn(q) and Cn(q), where the subscript i (type) corresponds to the node i
of the Coxeter Dynkin diagram, i = 1, 2, . . . , n.
Consider the binary relations φ(Bn(q)) and φ(Cn(q)) whereby two
distinct elements of type n are incident to a common element of type n−1.
When q is odd, the graphs Γn(Bn(q)) and Γn(Cn(q)) are nonisomorphic
but isospectral. For n > 3, φ(Bn(q)) and φ(Cn(q)) are families of small
world graphs. Their diameter is n, however their degrees are tending with
q toward infinity.
Each family can be embedded in a larger family of small world graphs
via the following scheme:
(1) Take the universal geometry of type Bn (or Cn) defined over the com-
mutative ring K defined in section 9, compute its specialisation S which
is an incidence system with partition sets Γ1(Xn),Γ
2(Xn), . . . ,Γ
n(Xn).
(2) Consider the graphs φS(Xn,K) of the binary relation of incidence of
two distinct elements of Γn(Xn) to some element of Γn−1(Xn).
Note that new families of small world graphs φS(Xn,K) depend on
the ring K and specialisation S. Graphs φS(K) for the chosen ring K and
various S have the same sets of vertices.
So the following problem appears naturally.
Find a ring K and a pair of representations S1 and S2 such that
nonisomorphic graphs φS1(Bn,K) and φS2(Cn,K) are isospectral. In the
case of finite fields Fq of odd prime-power order q, such a pair S1, S2
actually exists.
We can consider families of distance-regular graphs φ(Dn+1(q)) (two
vertices of Γn(Dn+1(q)) are incident to some element of type n− 1) and
φ′(Xn(q)) (two vertices of Γn(Xn(q)) are incident to some element of type
n− 2) where X = B or X = C and n > 3.
Note that the graphs φ(Dn+1(q)) and φ′(Bn(q)) are isomorphic,
whereas φ′(Cn(q)) are the Ustimenko graphs (see subject index of [4]).
One can take the universal geometries of Xn over a finite commutative
ring K for X = B, X = C and X = D, and their specialisations.
The search for nonisomorphic isospectal pairs of graphs from the
disjoint union of φS1(Dn+1,K), φ′
S2(Bn,K) and φ′
S3(Cn,K) makes sense
“adm-n3” — 2021/1/4 — 9:14 — page 121 — #127
V. Ustimenko 121
because of isospectrality of φ(Dn+1(q)) and Ustimenko graphs for odd q
and n > 3.
We may consider the restrictions of φ(D4(q)) and φ(X3(q)) for X = B
orX = C on the largest Schubert cells of the corresponding geometry which
are also distance-regular graphs (see section 6), and investigate restrictions
of φS1(D4,K), φ′
S2(B3,K) and φ′
S3(B3,K) on the corresponding largest
Voronoi–Schubert cells (see section 9).
The interpretation of the geometry Γ(n, q) of the Chevalley group Xn(q)
as a special interpretation of the universal geometry U(Xn,K) allows one
to generate this object in computer memory in time O(|Γ(n, q)|) with fast
algorithm (O(n2)) to check whether or not two elements of the geometry
are incident. Notice that the incidence systems US(Xn,K) where K is a
finite commutative ring are “computationally equivalent” to Γ(n, q).
The interpretation of Γ(n, q) as US(Xn,K) for specialisation S allows
one to effectively generate small world graphs corresponding to double
cosets of the form PigPi and more general graphs corresponding to PigPj
such as the Double Grassman graphs of geometry A2k+1(q) considered in
section 4 (see [31]).
The concept of Voronoi orbitals allows us to define new small world
graphs in terms of specialisations of U(Xn,K) which are analogues of
double coset graphs.
An important geometric object is the partition of the elements of a
geometry of a Chevalley group into thin Schubert cells. In the case of
Projective Geometry this was investigated by D. Hilbert. We conjecture
that this is a partition of vertices of incidence graphs into Voronoi cells
with respect to the natural embedding of the Weyl geometry into the
geometry of its corresponding Chevalley group. In the case of projective
geometry over the field of complex numbers, this fact was proved by I. M.
Gelfand and R. MacPherson (see [16] and further references).
For each specialisation S of the universal geometry U(Xn,K), one
can find the naturally embedded geometry of the Weyl group W (Xn).
So Voronoi–Schubert cells can be considered for each incidence graph of
US(Xn,K). We believe that properties of this partition are important for
spectrum investigation of small world graph defined in terms of U(Xn,K).
“adm-n3” — 2021/1/4 — 9:14 — page 122 — #128
122 On small world non-Sunada twins
1. Some basic definitions from Graph Theory and
Algebraic Combinatorics
1.1. On distance in graphs and related constructions
Let G be a finite simple graph. For vertices x and y of G, we denote
by d(x, y) the length of the shortest path from x to y, and set Gi(x) =
{y : d(x, y) = i}. We sometimes write G(x) for G1(x). Also x ∼ y is used
to denote that x ∈ G(y). Now fix x and y in V (G) with y ∈ Gi(x). Define
ai = |Gi(x) ∩ G1(y)|, bi = |Gi+1(x) ∩ G1(y)|, ci = |Gi−1(x) ∩ G1(y)|. If
these parameters never depend on x and y, but only on i, then G is called
a distance-regular graph.
One source of examples of distance-regular graphs is provided by
distance-transitive graphs: a graph G is distance-transitive if for all
x1, y1, x2, y2 ∈ V (G) with d(x1, y1) = d(x2, y2), there exists an auto-
morphism σ of G with σ(x1) = x2 and σ(x2) = y2.
Let G be any graph. We define a bipartite graph G∗ (called the
extended bipartite double of G, cf. [4], p. 261) as follows. Let F1 and F2
be disjoint sets of the same size as V (G), with fi : V (G) → Fi bijections,
for i = 1, 2. The vertex set of G∗ is defined to be F1∪F2. For u, v ∈ V (G),
f1(u) ∼ f2(v) in G∗ if and only if either u = v or u ∼ v in G. For
x, y ∈ V (G∗) we will write d∗(x, y) for the distance from x to y. We also
define φ : V (G∗) → V (G) by φ|Fi = fi
−1.
Lemma 1. Let x, y ∈ V (G∗) with d∗(x, y) = i. Suppose that u = φ(x)
and v = φ(y) with d(u, v) = j. Then j is either i or i− 1. The diameter
of G∗ is greater by one than that of G.
If a regular graph G is bipartite, it is associated with another regular
graph G′, defined as follows. Suppose that V (G) = X∪Y is the bipartition
of G. We let V (G′) = X, and for xl, x2 ∈ X we define x1 ∈ G′(x2) provided
x1 ∈ G2(x2). G
′ is called a halved graph of G. More information on halved
graphs may be found in [4].
1.2. On Coxeter groups, Tits systems and their geometries
An incidence system is a triple (Γ, I, t) where I is a symmetric antire-
flexive relation (simple graph) on the vertex set Γ, and t : Γ → N is a type
function onto the set of types N such that αIβ and t(α) = t(β) together
imply α = β. A flag F is a nonempty subset of Γ such that α, β ∈ F
implies αIβ. We define t(F ) = {t(x)|x ∈ F} (see [16]).
“adm-n3” — 2021/1/4 — 9:14 — page 123 — #129
V. Ustimenko 123
An important example of an incidence system as described above is
the so-called group incidence system Γ(G,Gs)s∈S . Here G is the abstract
group and {Gs}s∈S is the family of distinct subgroups of G. The objects
of Γ(G,Gs)s∈S are the left cosets of Gs in G for all possible s ∈ S. Cosets
α and β are incident precisely when α ∩ β 6= ∅. The type function is
defined by t(α) = s where α = gGs for some s ∈ S.
Let (W,S) be a Coxeter system, i.e. W is a group with a set of
distinguished generators given by S = {s1, s2, . . . , sn} and generic relations
(sisj)
mij = 1 for all 1 6 i, j 6 n. Here M = (mij) is a symmetric n× n
matrix with mii = 1 and off-diagonal entries satisfying mij > 2 (allowing
mij = ∞ as a possibility, in which case the relation (sisj)
mij = 1 is
omitted). Letting Wi = 〈S−{si}〉, 1 6 i 6 n, we obtain a group incidence
system Γ(W ) = Γ(W,Wi)16i6n which is called the Coxeter geometry of W .
The subgroups Wi here are referred to as the maximal standard subgroups
of W (see [32] or [16]).
Let T be the totality of all reflections, i.e. elements of the form gsig
−1
where g ∈ W , i = 1, 2, . . . , n. We assume that elements of W and T
are listed in the standard lexicographical order with respect to basis
{s1, s2, . . . , sn}.
Let l(g) be the length of a minimal irreducible decomposition of g
into elements of S. For α ∈ Γ(W ), we define l(α) as the minimal length
of a representative of this coset. We introduce the set ∆(α) = {s ∈ T |
l(sα) < l(α)}.
Let G be a group, B and N subgroups of G, and S the collection of
cosets of B ∩N in N . We call (G,B,N, S) a Tits system (or we say that
G has a BN -pair) provided
(i) G = 〈B,N〉 and B ∩N is normal in N ,
(ii) S is a set of involutions which generates W = N/(B ∩N),
(iii) sBw is a subset of BwB ∪BswB for any s ∈ S and w ∈ W ,
(iv) sBs 6= B for all s ∈ S.
Properties (i)-(iv) imply that (W,S) is a Coxeter system (see [32] or
[16]). Whenever (G,B,N, S) is a Tits system, we call W the Weyl group of
the system, or simply the Weyl group of G. The subgroups Pi of G defined
by BWiB are called the standard maximal parabolic subgroups of G. The
group incidence system Γ(G) = Γ(G,Pi)16i6n is commonly referred to
as the Lie geometry of G (see [16], [32]). Note that the Lie geometry of
G and the Coxeter geometry of the corresponding Weyl group W have
the same rank n. In fact, there is a type-preserving morphism from Γ(G)
onto Γ(W ) given by Retr : gPi → wWi, where w is determined from the
equality BgPi = BwPi. This morphism Retr is called a retraction.
“adm-n3” — 2021/1/4 — 9:14 — page 124 — #130
124 On small world non-Sunada twins
Let us consider the totality F of conjugates of Borel subgroup B
of the form Bn = nBn−1 where n ∈ N , and their respective orbits on
Γ(G). These orbits give rise to a natural equivalence relation τ where
xτy provided x and y lie in the same orbit of each subgroup from F . The
equivalence classes are known as thin Schubert cells (see [16] and further
references with descriptions of various applications of these equivalence
classes).
1.3. On association schemes, permutation groups and hyper-
groups
The notion of an association scheme is one of the most important in
all of Algebraic Combinatorics.
An association scheme Ω consists of a finite set X and a collection of
binary relations R0, R1, . . . , Rd that partitions X ×X, such that
1) R0 = {(x, x) | x ∈ X},
2) for each i = 1, 2, . . . , d, the inverse relation
Ri
−1 = {(x, y) | (y, x) ∈ Ri}
coincides with some Rj from the collection,
3) for i, j, k ∈ {0, 1, 2, . . . , d}, the number
pki,j = pki,j(a, b) = |{x ∈ X | (a, x) ∈ Ri, (x, b) ∈ Rj}|
does not depend on the choice of the pair (a, b) ∈ Rk.
Let (G,X) be a transitive permutation group acting on the set X.
Orbitals of (G,X), i.e. orbits of the induced action of G on the set X×X,
are binary relations of an association scheme. Let a ∈ X, and define
H = {g ∈ G | g(a) = a}.
Then orbitals of (G,X) are in one-to-one correspondence with double
cosets of the form HgH, g ∈ G.
For each directed graph Ri of an associative scheme we consider its
adjacency matrix Ai of size |X| × |X| with entries a(x, y) ∈ {0, 1} such
that a(x, y) = 1 if and only if (x, y) ∈ Ri. It follows from the definition
of matrix product that AiAj =
∑
pki,jAk. So the vector subspace A(Ω) =
〈A0, A1, A2, . . . , Ad〉 in Mn(C), n = |X| (i.e. the matrix algebra over the
field C of complex numbers) is closed under matrix multiplication.
Such algebras have appeared in different areas of mathematics under
different names such as Bose-Mesner algebra, cellular algebra, centraliser
“adm-n3” — 2021/1/4 — 9:14 — page 125 — #131
V. Ustimenko 125
algebra, V -Shur ring (see [33], [34]). In the case of an association schemes
of orbitals for a permutation group (G,X), we will reserve the term Hecke
algebra (see [32]) for this algebra. The Hecke algebra H = H(G,X) may
be identified as the centralizer of the totality of all permutations from
(G,X):
H = {M ∈ Mn(C) | AπM = MAπ for all π ∈ G}
where Aπ is the n× n permutation matrix corresponding to the permuta-
tion π.
We also consider the totality H[G] of formal linear combinations of
the symbols a0, a1, . . . , ad such that the relations
ai × aj =
∑
zki,jak
give us the definition of an associative algebra with unity a0. This object
is known in Functional Analysis as a hypergroup (see, [35], [36]). Note that
a hypergroup is an abstract algebra with fixed basis {a0, a1, . . . , ad} and
integer structure constants pki,j > 0.
We will refer to nonisomorphic Bose-Mesner matrix algebras with the
same hypergroups as hyper-equivalent BM algebras .
2. Two Cartan matrices with the same Coxeter group
and large families of isospectral graphs
Let us consider the Coxeter-Dynkin diagrams Xn with n nodes, where
X stands for one of the letters B, C and D with n > 3. For each Xn we
denote by W (Xn) and Xn(q) the Weyl group and Chevalley group over
the finite field Fq, respectively.
Let {s1, s2, . . . , sn} be a set of Coxeter generators of W = W (Xn)
with X = B or X = C, and let sn correspond to the extreme right node
of the diagram Xn. Let us consider the action of the group W (Xn) on
its left cosets by its standard subgroup Wn generated by the elements
s1, s2, . . . , sn−1. One can identify the variety (W : Wn) with a vector
space F2
n. The permutation group (W, (W :Wn)) coincides with the affine
transformations TA,b of the kind x 7→ xA+ b, where A is a permutation
matrix, and x and b are row vectors from F2
n. Thus W is a semidirect
product of the symmetric group Sn with the additive group of the vector
space F2
n.
Let T be the linear map on F2
n defined by
T : (x1, x2, . . . , xn) 7→ (x1 + x2 + · · ·+ xn, x2, x3, . . . , xn).
“adm-n3” — 2021/1/4 — 9:14 — page 126 — #132
126 On small world non-Sunada twins
Then the group 〈T, s1, s2, . . . , sn−1〉 is isomorphic to Sn+1. Observe that
the group W ′ = 〈W,T 〉 is isomorphic to Weyl group W (Dn+1). It is known
that W (Xn) preserves Hamming distance d on F2
n defined by the rule
d((x1, x2, . . . , xn), (y1, y2, . . . , yn)) = |{i | xi 6= yi}|.
Hence, orbitals of the transitive permutation group W (Xn) are binary
relations φi = {(x, y) | d(x, y) = i}, i = 0, 1, . . . , n. One can see that
the orbitals of W ′ are φ0 (equality relation) and φ1 ∪ φ2, φ3 ∪ φ4, . . . ,
φn−1 ∪ φn in the case of even n, and φ1 ∪ φ2, φ3 ∪ φ4, . . . , φn−2 ∪ φn−1,
φn in the case of odd n.
Let us consider the Chevalley group Xn(q) with Borel subgroup B
acting on the totality of left cosets (Xn(q) :Pn) by its standard parabolic
subgroup Pn = BWnB corresponding to the extreme right node of the
Coxeter-Dynkin diagram. There is a natural one-to-one correspondence
between orbitals of (Xn(q), (Xn(q) : Pn)) and orbitals of (W (Xn), (W :
Wn)) (see [14]).
Let φ′
i be the orbital of Xn(q) corresponding to the orbital φi of
Weyl group W . Let S(Ω) be the symmetric group acting on the totality
of left cosets Ω = (Xn(q) : Pn). All proper subgroups G of S(Ω) such
that Xn(q) 6 G are described in ([10], [11]). The proof does not use the
classification of finite simple groups.
If X = C then Xn(q) < G < N(Xn(q)), where the normaliser in S(Ω)
is simply an extension of Xn(q) via automorphisms of the ground field Fq.
So orbitals of N(Cn(q)) and Cn(q) are the same.
If X = B, then Bn(q) < G < N(Bn(q)) or Dn+1(q)<G<N(Dn+1(q)).
The orbitals of groups Bn(q) and Dn+1(q) coincide with orbitals of their
respective normalisers, which are extensions of the corresponding Chevalley
groups by automorphisms of the ground field Fq (see [12] for the details).
We can describe orbitals of Dn+1(q) via special subsets of N =
{1, 2, . . . , n}. In the case of even n, we refer to {i, i+ 1} (1 6 i 6 n/2) as
generic subsets. In the case of odd n, our generic subsets are {i, i + 1}
(1 6 i 6 (n− 1)/2) and {n}. Orbitals of Dn+1(q) are unions of φ′
i where i
belongs to a single generic subset.
Let J be a proper subset of N = {1, 2, . . . , n}, and let CJ = CJ(n, q),
BJ = BJ(n, q) be graphs of binary invariant relations
⋃
i∈J φ
′
i of the
respective permutation groups (Cn(q), (Cn(q) :Pn)) and (Bn(q), (Bn(q) :
Pn)). Hecke algebras of (Bn(q), (Bn(q) : Pn)) and (Cn(q), (Cn(q) : Pn))
have the same intersectional indices (see [13] for closed formulae). This
fact follows also from distance regularity of φ′. In fact, structure constants
“adm-n3” — 2021/1/4 — 9:14 — page 127 — #133
V. Ustimenko 127
of the Hecke algebras of groups Bn(q) and Cn(q) acting on left cosets of a
maximal parabolic subgroup corresponding to any node of the Coxeter
diagram are also the same. This fact can be easily deduced from the
relations in the definition of the Tits generic algebra of the Coxeter
group Bn.
Theorem 1. Let J be a proper subset of N = {1, 2, . . . , n}. For each n > 3,
the graphs CJ(n, q) and BJ(n, q), where q ranges over various odd prime
powers, form a family of non-Sunada twins for which Aut(CJ(n, q)) =
N(Cn(q)), and Aut(BJ(n, q)) = N(Dn+1(q)) if J is a union of generic
subsets and Aut(BJ (n, q)) = N(BJ (n+1, q)) in all other cases. Moreover,
if J is generic set of cardinality 2 then for each n > 3 the graphs CJ (n, q)
and BJ(n, q) form a family of unbalanced non-Sunada twins.
Corollary. Let n > 3 be odd. If J is a singleton different from {n}, then
the graphs CJ(n, q) and BJ(n, q) form a balanced family of non-Sunada
small world twins with respective automorphism groups N(Cn(q)) and
N(Bn(q)). If J = {n} then the graphs CJ(n, q) and BJ(n, q) form a
balanced family of small world non-Sunada twins with respective automor-
phism groups N(Cn(q)) and N(Dn+1(q)).
J. Hemmeter observed that D′(n + 1, q) is isomorphic to B1,2(n, q),
and introduced the graphs H(n, q) = C1,2(n, q)
∗ [5] which are nowadays
referred to as Hemmeter graphs (see [4]).
Theorem 2. Let J be a proper subset of N = {1, 2, . . . , n}. For each n > 3
the graphs CJ(n, q)
∗ and BJ(n, q)
∗, where q ranges over various prime
powers, form a family of non-Sunada twins with automorphism groups
Aut(CJ (n, q))
∗ = N(Cn(q))×Z2, and Aut(BJ (n, q))
∗ = N(Dn+1(q))×Z2
if J is union of generic subsets and Aut(BJ (n, q)) = N(Bn+1(q))× Z2 in
all other cases. Moreover, if J is a generic set of cardinality 2, then for
each n > 3 the graphs CJ (n, q)
∗ and BJ (n, q)
∗ form a family of unbalanced
non-Sunada twins.
3. Case of other nodes
We introduce orbitals of the Coxeter group W of type Bn (or Cn) acting
on left cosets by its maximal standard subgroup Wi = 〈s1, s2, . . . , si−1,
si+1, si+2, . . . , sn〉 for i = 1, 2, . . . , n. The Coxeter geometry of W is the
disjoint union Γ of the sets Γi = (W :Wi) of left cosets of W by Wi with
incidence relation I defined by αIβ provided α ∩ β 6= ∅ where α ∈ Γi,
β ∈ Γj , i 6= j. It can be interpreted as follows (see for instance [6]): Let
“adm-n3” — 2021/1/4 — 9:14 — page 128 — #134
128 On small world non-Sunada twins
N = {1, 2, . . . , n}, and consider the sets Hi = {(A, f)|A ∈ 2N , |A| =
i, f → {0, 1}}, i ∈ N . Form the disjoint union H =
⋃
iHi with incidence
relation I defined by (A, f)I(B, g) for (A, f) ∈ Hi and (B, g) ∈ Hj (i 6= j)
provided A ⊂ B or B ⊂ A, and f(x) = g(x) for all x ∈ A ∩ B. The
incidence system H is isomorphic to Γ. As always 2N stands for totality
of subsets of N .
The orbitals of W acting transitively on Ht, 1 6 t 6 n may be described
as φr,s = {((A, f), (B, g)) | s = |A∩B|, r = |{x ∈ A∩B | f(x) = g(x)}|}
where 0 6 r 6 s 6 t.
Let us consider the action of G = Xn(q) where X ∈ {B,C} on the left
cosets of its maximal standard parabolic subgroup Pt = BwtB where B
is the standard Borel subgroup of G, 1 6 t 6 n. The orbitals Xr,s of the
permutation groups (G, (G :Pt)) are in natural one-to-one correspondence
with φr,s of (W, (W :Wt)). Let M(t) = {(r, s)|0 6 r 6 s 6 t}.
Theorem 3. Let M be a proper subset of M(t), t < n. Consider the
action of G = Xn(q) where X ∈ {B,C} on the set X(t, n, q) = (G : Pt) of
left cosets of G by its maximal standard parabolic subgroup Pt. Assume that
each XM (n, t, q) is the disjoint union of Xr,s for all (r, s) ∈ M(t). Then for
all odd q > 3 and parameters t and n, the pairs (BM (n, t, q), CM (n, t, q))
form a family of non-Sunada graphs with respective automorphism groups
N(Bn(q)) and N(Cn(q)).
4. Remarks on Schubert geometry, some conjectures
Let us consider the action of the group Xn(q) on the geometry Γ(Xn(q)),
which is the disjoint union of X(n, t, q), 1 6 t 6 n, as well as the natu-
ral action of Xn(q) on X2(n, t, q) = X(n, t, q) × X(n, t, q). The Bruhat
decomposition links these actions with the permutation representation
of the Weyl group W of Xn(q) acting on the elements of its geometry
Γ(Wn(q)), which is the disjoint union of W (n, t) = (W :Wt).
Specifically, orbits of (Xn(q), X
2(n, t, q)) and (W,W (n, t)) are in a
natural one-to-one correspondence induced by the correspondence between
double cosets PiwPj and WiwWj for 1 6 i, j 6 t (see [14], [15] and further
references).
The interpretation introduced above allows one to identify W (n, t) with
{(A, f)||A| = t, f ∈ 2A}, and further identify orbits on W (n, i)×W (n, j)
with the bipartite graphs W (n, i, j, t, s) = {((A, f), (B, g)) ∈ W (n, i) ×
W (n, j)) | t = |A ∩B|, s = |{x|f(x) = g(x)}|}, where max(i+ j − n, 0) 6
t 6 min(i, j).
“adm-n3” — 2021/1/4 — 9:14 — page 129 — #135
V. Ustimenko 129
The orbits of G = Xn(q) on Γi(G) × Γj(G) are in a natural one-to-
one correspondence with W (n, i, j, t, s). We use the symbol X(n, i, j, t, s)
to denote these orbits corresponding to W (n, i, j, t, s). We define type
t(X(n, i, j, t, s)) as the ordered tuple (n, i, j, t, s).
Let T be a maximal torus of Xn(q). The totality of elements of Γ(Xn(q))
containing T with the restriction of the incidence relation I to this subset
is isomorphic to the Weyl geometry Γ(Wn(q)). There is well defined
homomorphic retraction map Retr from Γ(Xn(q)) onto Γ(Wn(q)) (see
[16] and further references).
Without loss of generality we assume that Retr(Pi) coincides with
αi = ({1, 2, . . . , i}, f), where f(j) = 0 for 1 6 j 6 i. For w a Coxeter
element of Weyl group W , elements Retr(wPi) coincide with βi = ({n, n−
1, . . . , n− i+ 1}, g), where g(j) = 1 for each n− i+ 1 6 j 6 n. We refer
to these latter elements as Coxeter cosets of type i.
LetHi = HX
i = HX
i (n, q) be the subset of elements hPi from Γi(Xn(q))
such that Retr(hPi) = βi. We refer to the incidence system H = H1 ∪
H2 · · · ∪Ht with the restriction I ′ to this set as the Schubert geometry
H = H(Xn(q)). It is easy to check that the standard Borel subgroup B
acts regularly on maximal flags of H.
Note that for i 6= j, the restriction of I ′ to Hi ∪ Hj is a biregular
bipartite graph. We may assume that Γ(Wn) is the subset of elements of
Γ(Xn(q)) containing a maximal torus. For each element γ from Hi(Xn(q))
and each βj we consider the list Lj
i (γ) of types of orbits R of (Xn(q),Γi×Γj)
that contain (γ, βj). We say that γ1, γ2 from Hi are Weyl-equivalent if
Lj
i (γ1) = Lj
i (γ2) for all j. By definition, Weyl-equivalence classes are
unions of thin Schubert cells (see [17] and further references). In fact,
each such class is a medium Schubert cell with respect to the set of Weyl
elements that contain αi and βi (1 6 i 6 n) (see [18]).
This means that the number of Weyl-equivalence classes is bounded
by a constant c(n) which does not depend on the parameter q.
We say that two orbitals Φ1, Φ2 of the transitive permutation group
(B,Hi) are Weyl equivalent if (βi, γ1) ∈ Φ1, (βi, γ2) ∈ Φ2 and γ1, γ2 are
Weyl-equivalent.
We refer to unions of Weyl-equivalent orbitals as Weyl pseudo-orbitals
of (B,Hi). We define type of a pseudo-orbital as a list Lj
i (γ), 1 6 j 6 n,
where (βi, γ) ∈ R. The partition into psudo-orbitals is defined in terms
of the Coxeter matrix of the group W (Bn) = W (Cn). Thus, cardinalities
of pseudo-orbitals of B(Bn(q)) and B(Cn(q)) of a given type are of the
same cardinality.
“adm-n3” — 2021/1/4 — 9:14 — page 130 — #136
130 On small world non-Sunada twins
Conjecture 1. Let Ω be the set of all types of pseudo-orbitals of (B,Hi)
and let J 6= ∅ be a proper subset of Ω. For each triple (n, i, J) we consider
the disjoint union X(n, i, J, q) of pseudo-orbitals of type belonging to
J . For i 6= n, the graphs B(n, i, J, q) and C(n, i, J, q) form a family of
non-Sunada twins with respective automorphism groups N(B(Bn(q)),
N(B(Cn(q)). If n is odd then B(n, n, J, q) and C(n, n, J, q) form families
of non-Sunada twins with respective automorphism groups N(B(Dn+1(q))
and N(B(Cn(q)).
5. New distance-regular graphs and non-Sunada twins
For prime powers q, Pasechnik [18] constructed a distance-regular
graph with intersection array {q3, q3− 1, q3− q, q3− q2+1, 1, q, q2− 1, q3}
as a subgraph of the dual polar graph D4(q), in particular the subgraph
induced on the set of vertices at maximal distance from an edge. Brouwer
[18] constructed related distance-regular graphs Z = Zq with intersection
array {q3−1, q3−q ·q3−q2+1, 1, q, q2−1} as follows: Consider the vector
space Fq
3 equipped with the standard cross product ×. The vertex set is
(F 3
q )
2, where a pair (u, v) is adjacent to a distinct pair (u0, v0) if and only
if u0 = u + v × v0. The extended bipartite doubles of these graphs are
the above mentioned graphs constructed by Pasechnik. In fact, Brouwer’s
graph is a subgraph of the dual polar graph B3(q); more precisely it is
the subgraph induced on the set of vertices at maximal distance from a
vertex.
For even q, the mentioned graphs have the same intersection arrays
as certain Kasami graphs (see [4], Theorem. 11.2.1 and units (11),(13)).
Pasini and Yoshiara [19] constructed distance-regular graphs with the
same intersection array as (bipartite, diameter 4) Kasami graphs using
dimensional dual hyperovals. Also the symmetric bilinear forms graphs for
q even and n = 3 are distance-regular with the same intersection array as
(diameter 3) Kasami graphs, (see [4], p. 285-286, and [20]). This shows that
Z is distance-regular with the claimed parameters. The spectrum follows.
The fact that the extended bipartite double is distance-regular, and has
the above stated intersection array, follows from [4], Theorem 1.11.2(vi).
The fact that Z3 is strongly regular follows from [4], Proposition 4.2.17(ii),
which states that this occurs when Z has eigenvalue −1. For the case
q = 2, the graphs are (i) the folded 7-cube, (ii) the folded 8-cube, (iii)
the halved folded 8-cube. All are distance-transitive. For q > 2, however,
these graphs are not distance-transitive. When q is a power of two, the
“adm-n3” — 2021/1/4 — 9:14 — page 131 — #137
V. Ustimenko 131
graphs Z have the same parameters as certain Kasami graphs, but for
q > 2 they are nonisomorphic.
Observe that set Z(q) of vertices of graph Zq is a largest Schubert cell of
B3(q) acting on dual polar spaces, i.e. a largest orbit of the Borel subgroup
B3 = B3(q) of B3(q). Group D4(q) is an overgroup of the permutation
group (B3(q), B(3, q)); the stabilizer of Z(q) in D4(q) is isomorphic to the
Borel subgroup B4 = B4(q) of this group. Group D4(q) has orbitals which
form a fusion scheme of the association scheme of orbitals (B3(q), Z(q)).
The distance in the graph Zq defines an association scheme R which is
a fusion of orbital schemes of D4(q) and B3(q). For two types T1 and
T2 of pseudo-orbitals δ1 and δ2 of B3(q), we write T1 ∼ T2 mod (D4)
and say they are D4-equivalent if there is an orbital φ of B(D4(q)) such
that φ ∩ δi 6= ∅ for i = 1, 2. We refer to minimal sets of D4-equivalent
types as generic sets. Each graph of the association scheme R coincides
with B(3, 3, J, q), where J is a union of generic sets. Note that there are
four generators of this association scheme, namely zi, 1 6 i 6 4, where
z = zq. We consider J1, J2, J3, J4 such that zi = B(3, 3, Ji, q). It turns
out that the relation siq = B(3, 3, Ji, q) (1 6 i 6 4) forms an association
scheme with the same intersection indices as scheme R. Let sq = s1q . It
is easy to see that Sq = Zq in the case of even q. In the case of odd
q, the groups Aut(Zq) and Aut(Sq) are normalisers N1 = N(B4) and
N2 = N(B(PSP6(q))) of Borel subgroups of D4(q) and C3(q) in the
corresponding symmetric groups.
Theorem 4. For odd q, the distance-regular graphs Zq and Sq have the
same parameters, and form a family of edge-intransitive non-Sunada small
world twins with respective automorphism groups N(D4(q)) and N(C3(q)).
Proposition 1. Let M be a nonempty proper subset of {1, 2, 3, 4}. Then
the unions ZM
q =
⋃
i∈M ziq and SM
q =
⋃
i∈M siq form a family of non-
Sunada small world twins as q ranges over all odd prime powers.
Theorem 5. For odd q, the extended bipartite doubles Z ′
q and S′
q of Zq
and Sq, respectively, form a family of distance-regular non-Sunada twins
with respective automorphism groups N1 × Z2 and N2 × Z2.
6. Case of the diagram An, the twisted Grassmann
graphs
In [21] van Dam and Koolen constructed the first family of non-vertex-
transitive distance-regular graphs with unbounded diameter. These graphs,
“adm-n3” — 2021/1/4 — 9:14 — page 132 — #138
132 On small world non-Sunada twins
called twisted Grassmann graphs, are denoted by J̃q(2D + 1, D) and are
constructed as follows: Let q be a prime power, and let D > 2 be an
integer. Let V be a (2D + 1)-dimensional vector space over Fq, and let H
be a hyperplane in V . Vertices are of two types: (i) (D + 1)-dimensional
subspaces of V that are not contained in H , and (ii) (D − 1)-dimensional
subspaces of H . Two vertices of the first type are adjacent if they intersect
in a D-dimensional subspace; a vertex of the first type is adjacent to a
vertex of the second type if the first contains the second; and two vertices
of the second type are adjacent if they intersect in a (D − 2)-dimensional
subspace. The twisted Grassmann graph is distance-regular and has the
same intersection array as the Grassmann graph Jq(2D + 1, D). In fact,
the Grassmann graph and twisted Grassmann graph are the point graph
and line graph, respectively, of the same partial linear space.
As mentioned above, the twisted Grassmann graph is not vertex-
transitive (it has two orbits of vertices) and hence it is not isomorphic to
the Grassmann graph. Fujisaki, Koolen, and Tagami [22] showed that the
automorphism group of the twisted Grassmann graph is the subgroup of
PΓL(2D + 1, q) that fixes H . Bang, Fujisaki, and Koolen [23] determined
the spectra of the local graphs, and studied in some detail their Terwilliger
algebras. Remarkably, these algebras with respect to vertices in distinct
orbits are not the same. The twisted Grassmann graphs are also coun-
terexamples to two conjectures by Terwilliger ([24], p. 207-210), see [23].
Jungnickel and Tonchev [25] constructed designs that are counterexamples
to Hamada’s conjecture. Munemasa and Tonchev [26] showed that the
twisted Grassmann graphs are isomorphic to the block graphs of these
designs. Munemasa [27] showed that the twisted Grassmann graphs can
also be obtained from the Grassmann graphs by Godsil-McKay switching
(cf. [28], X1.8.3]).
Proposition 2. For each D > 3 and q ranging over all prime powers, the
graphs Jq(2D+1, D) and J̃q(2D+1, D) form a family of strongly unbalanced
non-Sunada graphs with respective automorphism groups PΓL(2D + 1, q)
and K, where K is the subgroup of PΓL(2D + 1, q) fixing H.
7. On Voronoi diagrams and cells, thin Schubert cells
and isospectral graphs
The classical Voronoi diagram is a distance-based decomposition of a
metric space relative to a discrete set of nodes, called the Voronoi sites.
Given a set of Voronoi sites, the Voronoi decomposition leads to regions
“adm-n3” — 2021/1/4 — 9:14 — page 133 — #139
V. Ustimenko 133
(the Voronoi regions) consisting of all nodes that are closest to a specific
site. Mehlhorn [29] and Erwig [30] proposed an analogous decomposition,
the graph Voronoi Diagram, for both undirected and directed graphs.
Definition 1 (Graph Voronoi Diagram [29], [30]). In a graph Γ =
(V,E,w), where w is weight function, the Voronoi diagram for a set
S = {v1, . . . , vs} ⊆ V of nodes is a disjoint partition Vor(Γ, S) =
V1, V2, . . . , Vs of V such that for each node u ∈ Vi, d(u, vi) 6 d(u, vj)
for all j ∈ {1, 2, . . . , s}.
In the above, the Vi are the Voronoi regions. The graph Voronoi
diagram is not necessarily unique, as a node u may have the same distance
to more than one Voronoi site.
We introduce the Voronoi cells as classes of the equivalence relation τ
on V defined by xτy if and only if d(x, vi) = d(y, vi) for all i = 1, 2, . . . , n.
The connection with the graph Voronoi diagram is clear: Voronoi regions
are disjoint unions of Voronoi cells.
Let C(Γ, S) be the totality of Voronoi cells. We assume that the weight
of each edge is 1 and that the Voronoi Diagram is unique. We consider the
Voronoi-Schubert diagram VorSch(Γ, S) which is a partition of C(Γ, S)
corresponding to equivalence relation: two Voronoi cells are in the same
Voronoi region.
For each c ∈ C(Γ, S) we define its trace tr(c) = (d1, d2, . . . , dn) where
di = d(vi, c) = d(vi, x) for x ∈ c . If Γ is a finite graph we consider the
order |c| of the Voronoi cell c which is simply the cardinality of this subsets
of nodes.
We refer to (Γ, S) as a graph with selected nodes. We say that (Γ1, S1)
and (Γ2, S2) are Voronoi-equivalent if there are bijections η : S1 → S2,
µ :C(Γ, S1) → C(Γ2, S2) such that d(vi, c) = d(η(vi), µ(c)). We refer to
the pair (η, µ) as a diagram isomorphism.
In the case of finite graphs, we say that (Γ1, S1) and (Γ2, S2) are
strongly diagram-equivalent if they are Voronoi-equivalent and |c| = |µ(c)|
for each Voronoi cell c.
Let F be a field. The Chevalley group Xl(F ) has a BN -pair and
finite irreducible Weyl group W . Fixed points of a maximal torus T in
its action on Γ(Xl(F )) form a subset of W such that the restriction of
the incidence relation I to this subset is isomorphic to Weyl geometry of
W (Xl). So we have a natural embedding of W (Xl) into Γ = Γ(Xl(F )).
Let I(Xl(F )) denote the incidence relation of Γ. We are interested in
studying Vor(Γ(G), S).
“adm-n3” — 2021/1/4 — 9:14 — page 134 — #140
134 On small world non-Sunada twins
Conjecture 2. Let Γ(G) be the geometry of a simple group G that has
a BN-pair. Let B, W and T denote a fixed Borel subgroup of G, the Weyl
group of G and a maximal torus of G, respectively. Then the partition
of Γ(G), Γ(W ) into Voronoi cells coincides exactly with its partition into
thin Schubert cells.
In the case of projective geometry the above conjecture is supported
by a well known theorem due to I. Gelfand and R. MacPherson (see [16]
and further references).
Conjecture 3. Let F be a field. Then the pairs (I(Bn(F )),W (Bn)) and
(I(Cn(F )),W (Cn)) are Voronoi-equivalent. Moreover, if F is finite they
are strongly diagram-equivalent.
Let us consider a pair (Γ, (a, b)) where (a, b) ∈ V 2, and take S = {a, b}
of cardinality at most two. We say that (a1, b1) and (a2, b2) are Γ-equivalent
if there is diagram isomorphism (η, µ) of (Γ, {a1, b1}) with (Γ, {a2, b2})
such that η(a1) = a2 and η(b1) = b2.
We refer to classes of Γ-equivalence as Γ-orbitals. We say that a
partition into Γ-orbitals is transitive if there is a permutation group
(G, V ) such that its orbits on V 2 coincide with the Γ-orbitals.
We refer to a Voronoi-Schubert diagram of type (Γ, {a, b}) as a binary
V S-diagram. We denote its trace function on Voronoi cells by tr. If the
value |c| is given for each cell c, we then use the term scaled V S-diagram.
Two graphs Γ1 and Γ2 are said to be Voronoi-equivalent (resp., strongly
diagram-equivalent) if their orbital partitions are transitive, and their sets
of binary V S-diagrams (resp., scaled V S-diagrams) coincide.
We can use technique of [31] and prove the following.
Theorem 6. Let F be an arbitrary field. Then the incidence graphs
Γ(Bn(F )) and Γ(Cn(F )) are Voronoi-equivalent.
Theorem 7. Incidence graphs of Γ(Bn(q)) and Γ(Cn(q)) are strongly
diagram-equivalent.
Remark. Observe that isospectrality of the graphs corresponding to the
orbitals (Bn(q),Γi(Bn(q)) and (Cn(q),Γi(Cn(q)) may be deduced from
this statement.
Let us consider a partition P = {R0, R1, . . . , Rk} of the Cartesian
square V 2 such that all graphs Ri are regular (recall that R0 is the
equality relation on V ). The partition of V 2 into Ri orbitals coincides
with some fusion of partition P . We refer to such P as a Voronoi graph
configuration.
“adm-n3” — 2021/1/4 — 9:14 — page 135 — #141
V. Ustimenko 135
Example. Let (G, V ) be a transitive transformation group on V . Then
each partition of V 2 into Ri orbitals will be a Voronoi graph configuration.
Theorem 8. Consider the groups Bn(F ) and Cn(F ) defined over an
arbitrary field F , in their respective actions on totally isotropic subspaces of
equal dimension. Then their Voronoi graph configurations are isomorphic.
8. Linguistic graphs and some conjectures
We refer to a triple (V, t, I) as an incidence system, where V is a set,
t is a type function on V which implicitly defines a partition V = V1 ∪
V2 ∪ · · · ∪Vn, and I is an incidence relation (i.e. a symmetric, antireflexive
binary relation) on the set V . We refer to n as the rank of the system.
A rank 2 incidence system is called an incidence structure, and in such
case it is customary to express the partition as V = P ∪ L and refer to
the elements of P and L as points and lines, respectively. A flag is a pair
{x, y} such that xIy, where either x ∈ P , y ∈ L or y ∈ P , x ∈ L.
Let K be a finite commutative ring. We refer to an incidence structure
with point set P = Ps,m = Ks+m and line set L = Lr,m = Kr+m as a
linguistic incidence structure Im if the point
(x) = (x1, x2, . . . , xs, xs+1, xs+2, . . . , xs+m)
is incident to the line
[y] = [y1, y2, . . . , yr, yr+1, yr+2 . . . , yr+m]
if and only if the following relations hold:
ξ1xs+1 + ζ1yr+1 = f1(x1, x2, . . . , xs, y1, y2, . . . , yr)
ξ2xs+2 + ζ2yr+2 = f2(x1, x2, . . . , xs, xs+1, y1, y2, . . . , yr, yr+1)
. . .
ξmxs+m + ζmyr+m = fm(x1, x2, . . . , xs+m−1, y1, y2, . . . , yr+m−1)
In the above, ξj and ζj , j = 1, 2, . . . ,m, are not zero divisors, and the func-
tions fj are multivariate polynomials with coefficients from K. Brackets
and parenthesis allow us to distinguish points from lines (see [22]).
The colour ρ(x) = ρ((x)) of a point (x) is defined to be the projection
of (x) from a free module onto its initial s coordinates. The colour ρ(y) =
ρ([y]) of a line [y] is defined similarly via projection onto its initial r
coordinates. In other words, point (x) = (x1, x2, . . . , xs+m) has colour
“adm-n3” — 2021/1/4 — 9:14 — page 136 — #142
136 On small world non-Sunada twins
ρ(x) = (x1, x2, . . . , xs) and line [y] = [y1, y2, . . . , yr+m] has colour ρ([y]) =
(y1, y2, . . . , yr).
From the definition of linguistic incidence structure, it follows that
for each vertex of its incidence graph, there exists a unique neighbour
of each chosen colour. More specifically, for each b ∈ Kr and (p) =
(p1, p2, . . . , ps+m) there is a unique neighbour of the point [l] = Nb(p)
with the colour b. Similarly for each b ∈ Ks and [l] = [l1, l2, . . . , lr+m]
there is a unique neighbour of the line [p] = Nb([l]) with the colour b.
We should also mention that we consider linguistic incidence structures
defined by an infinite number of equations.
Let G be a group having a BN -pair, with Borel subgroup B and finite
Weyl group W . We consider the action of B on the geometry Γ(G). Orbits
of this action are known as large Schubert cells. Let us consider the union
L of two large Schubert cells Si and Sj from Γi(G) and Γj(G), i 6= j, and
assume that the restriction of incidence relation I to Si ∪ Sj is nonempty.
From the properties of BN -pairs, it follows that I ′ is an edge-transitive
linguistic graph, and the Borel subgroup acts regularly on its edges.
Let Si,j(G) be the incidence graph of the restricted geometry to the
two largest Schubert cells Si and Sj , i.e. the totality of cosets BgPi and
BgPj where g ∈ W is an element with maximal length l(g) (a so-called
Coxeter element). We refer to Si,j(G) as a Schubert graph.
Conjecture 4. Let q be an arbitrary odd power. Then the Schubert
graphs Si,j(Bn(q)) and Si,j(Cn(q)) form families of edge-transitive non-
Sunada graphs.
Conjecture 5. Let F be an arbitrary field, then the graphs Si,j(Bn(F ))
and Si,j(Cn(F )) are Voronoi-equivalent.
Remark. In the case of a field of odd characteristic or characteristic zero,
the graphs Si,j(Bn(F )) and Si,j(Cn(F )) are nonisomorphic.
9. Towards K-theory of linguistic configurations
Lingustic graphs with parameters m, s, r may be interpreted in the
following way: Let Ω be a set with distinguished subsets A1 and A2,
such that |A1 ∩A2| = m. We define a linguistic graph L(A1, A2,Ω) with
partition sets KA1 and KA2 and with colour spaces KA1,2 and KA2,1 ,
where A1,2 = A1 − (A1 ∩ A2), A2,1 = A2 − (A1 ∩ A2) such that ρ(f),
f ∈ KAi , is the restriction of f to Ai − A1 ∪ A2. To do this, we may
assign A1 ∩ A2 = {1, 2, . . . ,m}, A1 − A2 = {m + 1,m + 2, . . . ,m + s},
“adm-n3” — 2021/1/4 — 9:14 — page 137 — #143
V. Ustimenko 137
A2 − A1 = {m + s + 1,m + s + 2, . . . ,m + s + r} and identify (A1, g),
(A2, h) with the tuples (g(m+1), g(m+2), . . . , g(m+s), g(1), g(2), g(m)) =
(x1, x2, . . . , xs+m) = (x) and [h(m+ s+ 1), h(m+ s+ 2), . . . , h(m+ s+
r), h(1), h(2), . . . , h(m)] = [y1, y2, . . . , yr+m] = [y] respectively. The set Ω
may be chosen to be any set that contains {1, 2, . . . ,m+ s+ r}.
Let Γ be a simple graph with vertex set {1, 2, . . . , n}. Let us assume that
there is a set Ω and function η from V (Γ) onto 2Ω. For each edge {i, j} ∈ Γ
the linguistic graph Li,j is given with its (η(i), η(j)) interpretation. We
refer to such data as a linguistic configuration with a governing triple
(Γ, η,Ω) and linguistic relations Li,j , {i, j} ∈ E(Γ) over a commutative
ring K.
For a fixed linguistic configuration, we define a linguistic blow-up Γ̃
of the governing graph Γ which is a totality of new vertices of the kind
(i, x), x ∈ Kη(i) such that (i, x) and (j, x) are neighbours in Γ̃ if and
only if i, j are neighbours in Γ and x, y are adjacent in the linguistic
graph Li,j . For each pair (i, j) of ordered neighbouring vertices in a
governing graph Γ, we consider ∆i,j = η(i)− η(i) ∩ η(j). We refer to η as
a governing map, and we adopt the notation Ai for the set η(i). For each
set A ⊂ Ω we consider the list of all its elements a1, a2, . . . , am and the
ring K[A] = K[xa1 , xa2 , . . . , xam ] = K[A] where xai are formal variables.
10. On Coxeter and Lie geometries and corresponding
linguistic configurations
Let {α, β} be a flag of cardinality 2. In the case of general linguistic
configurations, ∆(α)−∆(α) ∩∆(β) will be denoted as ∆(α, β).
Let us consider a class of Coxeter lingustic configurations with corre-
sponding incidence graph I of the Coxeter geometry Γ(W ) and boolean
embedding ∆ : α → 2T . To define a representative from this class, we must
choose a commutative ring K, and for each edge of the Coxeter geometry,
a linguistic relation Lα,β together with its ∆(α), ∆(β), T interpretation.
Each blow-up of I corresponding to such a linguistic configuration is an
incidence relation of the incidence system such that type of vertex (α, f),
where f ∈ K∆(α), is defined simply as t(α) for α ∈ Γ(W ). We say that the
linguistic configuration L(Γ, η,Ω)(K) defined via the choice of linguistic
graphs Li,j , iIj is bilinear if there is a bilinear product × on L = KΩ and
family of functions li : Ω → K, i ∈ V (Γ), such that the incidence relation
on each linguistic graph may be written as x(s)lj(s)−y(s)li(s) = (x×y)(s),
for x ∈ Li, y ∈ Lj and s ∈ ∆(i) ∪∆(j).
“adm-n3” — 2021/1/4 — 9:14 — page 138 — #144
138 On small world non-Sunada twins
Remark. We have to choose a linear ordering for each pair (i, j). In the
case of a skew-symmetric bilinear product (i.e. x× y = −y× x), the order
on pairs is immaterial. However, in the case of an alternative bilinear
product we must speak about alternative bilinear linguistic configurations.
Functions er ∈ KΩ such that er(r) = 1 and er(r
′) = 0 for r 6= r′ form
a natural basis of the free module KΩ. We say that a linguistic bilinear
configuration is of normal type if there is a symmetric partial function
f(x, y) on Ω × Ω which is not defined for (r, r), r ∈ Ω, such that the
bilinear product on L = KΩ is given by the rule er × e′r = λr,r′ef(r,r′).
Here, λr,r′ ∈ K under the assumption that er × e′r = 0 if (r, r′) is not in
the domain of f .
11. BN -pairs, their geometries as linguistic
configurations
Throughout this section, (G,B,N, S) will denote a Tits system which
arises in connection with a Chevalley group G or its generalisations. We
write G = Xl(K) to signify that G is a Chevalley group over the field
K with associated Dynkin diagram Xl. We are mostly interested in the
case when K is finite, and we shall write Xl(q) instead of Xl(Fq) in such
case. So, fix a Chevalley group G = Xl(K) with corresponding Weyl
group W . As in the previous section, we denote by Γ(W ) and Γ(G) the
corresponding Coxeter and Lie geometries.
Proposition 3. Let Γ = Γ(Xl(F )) be the Lie geometry of a simple Cheval-
ley group over the field F of characteristic p > 3 or 0. Then there exists a
Coxeter linguistic skew-symmetric bilinear configuration L(Γ(W ),∆, T )(F )
of normal type such that its blow-up is isomorphic to Γ.
The above statement shows that many flag-transitive algebraic inci-
dence systems can be constructed in terms of linguistic configurations
defined over a field. The proof of the statement is constructive. In fact, it
is a by-product of a theorem on the embedding of a Lie Geometry into
the Borel subalgebra of its corresponding Lie Algebra (see [17] and further
references).
12. On universal geometries of Chevalley groups Xn(K)
over commutative rings
Let us consider ΓW , ∆, T and Cartan function f(x, y). For each pair
{α, β} of incident vertices of ΓW , we consider functions dα,β and dβ,α
“adm-n3” — 2021/1/4 — 9:14 — page 139 — #145
V. Ustimenko 139
mapping ∆(α) ∩∆(β) to K∗, and parameters λ(r, s, α, β) ∈ K for pairs
(r, s) where r ∈ ∆(α), s ∈ ∆(β) for which f(r, s) is well-defined. We
consider the bilinear map [x, y] from Lα × Lβ into Lα ∩ Lβ such that
[er, es] = λα,β
r,s ef(r,s) for (r, s) in the domain of f , and [er, es] = 0 for (r, s)
outside the domain of f .
We say that x ∈ Lα and y ∈ Lβ are incident provided for s ∈
∆(α) ∪∆(β) we have x(s)dβ,α(s)− y(s)dα,β(s) = [x, y](s). We use term
Generalised Coxeter linguistic configuration (GCLC) for this object. We
also speak about universal GCLC (UGLCN), wherein for each edge α, β
of the Coxeter geometry, there are functions dα, dβ defined on ∆(α)∩∆(β)
with symbolic values dα(r) = x(αr) and dβ(r) = y(βr) (variables with
values from K∗) and formal parameters λα,β
r,s (variables with all possible
values from the commutative ring K).
Special cases of GCLC are Cartan-Coxeter linguistic configurations
for which W is a finite irreducible Weyl group with Cartan matrix corre-
sponding to one of the root systems An, Bn, Cn, Dn, E6, E7, E8, F4, G2.
To define such a configuration, we have to identify the set T with the set
R of positive roots of the corresponding root system, and define f(x, y)
such that f(r, s) = r + s if r + s ∈ R and 0 otherwise. We assume that
λα,β
r,s 6= 0 if one of the roots r, s is simple.
Observe that the Universal Cartan-Coxeter linguistic configuration is
uniquely determined by the choice of Cartan matrix A and commutative
ring K. Let Xn denote one of the above root systems. We use symbol
UCC(Xn, A,K) for the universal Coxeter-Cartan linguistic configuration
with Cartan matrix A defined over commutative ring K. For investigation
of such algebraic objects, we use the universal geometry UG(Xn(K)) of
the Chevalley group Xn(K) for which the following parameters are taken
as variables: d(α, β)(s) ∈ K∗, d(β, α)(s) ∈ K∗ for s ∈ ∆(α) ∩∆(β), and
λα,β
r,s ∈ K for s ∈ ∆(α), r ∈ ∆(β). When values from K are prescribed
for all these parameters, we speak of a specialisation S of the Universal
Cartan-Coxeter linguistic configuration UGS(Xn,K) over K.
Proposition 3 of the previous section shows that in the case of fields, a
special choice of S provides a Coxeter-Cartan linguistic configuration VS
whose blow-up is isomorphic to the geometry of the Chevalley group Xl(F ).
Specialisations of the universal geometry UG(Xn,K) form an interesting
class of incidence systems which contain flag-transitive geometries of
Chevalley groups when K is a field.
Computer simulation demonstrates that altering the coefficients in the
generic equations of linguistic graphs of Coxeter-Cartan configurations
“adm-n3” — 2021/1/4 — 9:14 — page 140 — #146
140 On small world non-Sunada twins
usually changes the spectrum of the lnguistic graphs. This means that
the majority of pairs of distinct specialisations provide nonisomorphic
incidence systems. Representatives of this class of incidence systems share
some intriguing properties. For example, from each vertex of a blow-up
Γ(Xn,K) of UGS(Xn,K) to elements of the kind (Wi, 0), there is a walk
whose length is restricted by a linear function l(n) that does not depend
on K or S. Thus the diameter of ΓS(Xn,K) is bounded above by 2l(n).
In the case of a fixed n and S and family of finite rings K = Km of
increasing order, the graphs ΓS(Xn,Km), m > 1, form a family of small
world graphs with unbounded degree (see [37] for related geometrically
based constructions and further references).
Acknowledgement
I would like to express my deep gratitude to my friend and collaborator
Professor Andrew Woldar of Villanova University for his professional advice
and constant support.
References
[1] T.Sunada, Riemannian Coverings and Isospectral Manifolds, Ann. Math., 121
(1985), 169-186.
[2] R. Brooks, Non-Sunada graphs, Annales de l’institut Fourier, tome 49, no 2 (1999),
p. 707-725.
[3] M. Cvetkovic, M. Doob, I. Gootman, A. Targasev, Theory of Graph Spectra, Ann.
Disc. Math. 36, North Holland, 1988.
[4] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-regular Graphs, Springer-
Verlag, Berlin, 1989.
[5] J. Hemmeter, Distance-Regular Graphs and Halved Graphs, Europ. J. Combina-
torics (1986) 7, 119-129.
[6] V. Ustimenko, On some properties of the geometries of the Chevalley groups and
their generalizations, Investigations in Algebraic Theory of Combinatorial Objects,
Kluwer, Dordrecht (1992). p. 112-119.
[7] Edwin R. van Dam, Jack H. Koolen, Hajime Tanaka, Distance Regular Graphs,
The Electronic Journal of Combinatorics, Dynamic Survey, DS22, 2016
[8] C. T. Benson,Minimal regular graphs of girths eight and twelve, Canad. J. Math.
26 (1966), 1091-1094.
[9] J.Tits, Sur la trialite et certains groupes qui s’en deduisent, Inst. Hautes Etudes
Sci. Publ. Math. 2 (1959), 13-60.
[10] V. V. Zdan-Pushkin, V. A. Ustimenko, On the maximality of certain classical
transformation groups, Voprosi teorii grupp i gomologicheskoi algebry, 1985, pp.
125–139.
“adm-n3” — 2021/1/4 — 9:14 — page 141 — #147
V. Ustimenko 141
[11] V.V. Zdan-Pushkin, V. A. Ustimenko, Maximality of finite classical groups acting
on the totally isotropic subspaces, Selecta Mathematica Sovetica, vol. 9, no. 4, 1990,
pp. 339–354.
[12] J Dieudonné, Sur les groupes classiques, Paris: Hermann, 1948.
[13] V. V. Zhdan-Pushkin, V.A. Ustimenko, Classical groups and metric association
schemes, Kibernetika, 6, 1986, pp. 83-94.
[14] R. Carter, Simple group of Lie type, Wiley, 1989.
[15] F. Buekenhout, ed., Handbook of incidence geometry, Amsterdam: 1995.
[16] A, Borovik, I. Gelfand, N. White,Combinatorial Flag Varieties, Journal of Combi-
natorial Theory, Series A, 91, (2000) 111-136.
[17] V. Ustimenko, On the varieties of parabolic subgroups, their generalisations and
combinatorial applications, Acta Applicandae Mathematicae, 52 , 1998, 223-238.
[18] A. Brouwer, D. Pasechnik, Two distance-regular graphs, J. Algebraic Combin., 36
(2012).
[19] A, Pasini, S. Yoshiara, New distance regular graphs arising from dimensional dual
hyperovals, European J. Combin. 22 (2001), 547-560.
[20] A.E. Brouwer, Corrections and additions to the book “Distance-regular Graphs”,
http://www.win.tue.nl/~aeb/drg/BCN-ac.ps.gz (October 2008).
[21] E. R. van Dam, J, H. Koolen, A new family of distance-regular graphs with
unbounded diameter, Invent. Math. 162 (2005), 189-193.
[22] T Fujisaki, J. H. Koolen, M. Tagami, Some properties of the twisted Grassmann
graphs, Innov. Incidence Geom. 3 (2006), 81-86.
[23] S. Bang, T. Fujisaki, J. H. Koolen, The spectra of the local graphs of the twisted
Grassmann graphs, European J. Combin. 30 (2009), 638-654.
[24] P. Terwilliger, The subconstituent algebra of an association scheme , I, J. Algebraic
Combin. 1 (1992), 363-388; II, J. Algebraic Combin. 2 (1993), 73-103; III, J.
Algebraic Combin. 2 (1993), 177-210.
[25] D. Jungnickel, V. Tonchev, Polarities, quasi-symmetric designs and Hamada’s
conjecture, Des. Codes Cryptogr. 51 (2009), 131-140.
[26] A. Munemasa, V. D. Tonchev, The twisted Grassmann graph is the block graph of
a design, Innov. Incidence Geom. 12 (2011), 1-6; arXiv:0906.4509.
[27] A. Munemasa, Godsil-McKay switching and twisted Grassmann graphs, preprint
(2015); arXiv:1512.09232.
[28] A. E. Brouwer, W. H. Haemers, Spectra of Graphs, Springer, New York, 2012.
[29] K. Mehlhorn, A faster approximation algorithm for the steiner problem in graphs,
Inf. Process. Lett., 1988, 27 (3), 125-128.
[30] M. Erwig, The graph Voronoi diagram with applications, Networks, vol. 36 (2000)
no. 3, pp. 156–163.
[31] V. Ustimenko, A. Woldar, A geometric approach to orbital recognition in Chevalley-
type coherent configurations and association schemes, Australas. J. Combin. 67
(2017), no. 2, 166–202.
[32] N. Bourbaki, Lie Groups and Lie Algebras, Chapters 1 - 9, Springer, 1998-2008.
http://www.win.tue.nl/~aeb/drg/BCN-ac.ps.gz
“adm-n3” — 2021/1/4 — 9:14 — page 142 — #148
142 On small world non-Sunada twins
[33] E. Bannai, T. Ito, Algebraic Combinatorics. 1984, 449 p.
[34] I. Faradjev M. Klin, M. Muzychuk, Cellular Rings and Groups of Automorphisms of
Graphs, In “Investigations in Algebraic Theory of Combinatorial Objects” (editors:
Faradzev, I.A., Ivanov, A.A., Klin, M., Woldar, A.J.), Springer, 1994, pp.1-152.
[35] E. Hewitt, K.Ross, Abstract harmonic analysis, vol.2, Structure and analysis for
compact groups. Analysis on locally compact abelian groups, Springer, 1970, 392 p.
[36] E. Hewitt, K. Ross, Abstract Harmonic Analysis: Volume 1, Structure of Topological
Groups., Integration Theory, Group Representations, Springer, 1994, 540 p.
[37] V. Ustimenko, Urszula Romaćzuk, Finite geometries, LDPC codes and Cryptogra-
phy, Maria Curie-Sklodowska University, Institute of Computer Science, 2012, (on
line access www: informatyka.umcs.lublin.pl).
Contact information
Vasyl Ustimenko Institute of Mathematics, Maria
Curie-Skłdowska University, Poland, and
Institute of Telecommunications and Global
Information Space, NAS of Ukraine, Ukraine
E-Mail(s): vasyl@hektor.umcs.lublin.pl
Received by the editors: 20.02.2019
and in final form 12.12.2020.
mailto:vasyl@hektor.umcs.lublin.pl
V. Ustimenko
|