{'fraction_non_alphanumeric': 0.069340053973281, 'fraction_numerical': 0.010928474251176483, 'mean_word_length': 3.496389891696751, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 31, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
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 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 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 {M 1 , M 2 } such that the eigenvalues of the Laplace operator satisfy λ i (M 1 ) = λ i (M 2 ) 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 M G , with M 1 and M 2 quotients of M G by subgroups H 1 and H 2 respectively, then M 1 and M 2 will be isospectral if the induced representations (1 H 1 ) G and (1 H 2 ) G are equivalent (here 1 X 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 B n and C n 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 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 Γ(B n (q)) i and Γ(C n (q)) i be the totalities of elements of the respective geometries of Chevalley groups B n (q) and C n (q), where the subscript i (type) corresponds to the node i of the Coxeter Dynkin diagram, i = 1, 2, . . . , n.
Consider the binary relations φ(B n (q)) and φ(C n (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 (B n (q)) and Γ n (C n (q)) are nonisomorphic but isospectral. For n 3, φ(B n (q)) and φ(C n (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 B n (or C n ) defined over the commutative ring K defined in section 9, compute its specialisation S which is an incidence system with partition sets Γ 1 (X n ), Γ 2 (X n ), . . . , Γ n (X n ).
(2) Consider the graphs φ S (X n , K) of the binary relation of incidence of two distinct elements of Γ n (X n ) to some element of Γ n−1 (X n ).
Note that new families of small world graphs φ S (X n , 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 S 1 and S 2 such that nonisomorphic graphs φ S 1 (B n , K) and φ S 2 (C n , K) are isospectral. In the case of finite fields F q of odd prime-power order q, such a pair S 1 , S 2 actually exists.
We can consider families of distance-regular graphs φ(D n+1 (q)) (two vertices of Γ n (D n+1 (q)) are incident to some element of type n − 1) and φ ′ (X n (q)) (two vertices of Γ n (X n (q)) are incident to some element of type n − 2) where X = B or X = C and n 3.
Note that the graphs φ(D n+1 (q)) and φ ′ (B n (q)) are isomorphic, whereas φ ′ (C n (q)) are the Ustimenko graphs (see subject index of [4]). One can take the universal geometries of X n 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 φ S 1 (D n+1 , K), φ ′ S 2 (B n , K) and φ ′ S 3 (C n , K) makes sense because of isospectrality of φ(D n+1 (q)) and Ustimenko graphs for odd q and n 3.
We may consider the restrictions of φ(D 4 (q)) and φ(X 3 (q)) for X = B or X = C on the largest Schubert cells of the corresponding geometry which are also distance-regular graphs (see section 6), and investigate restrictions of φ S 1 (D 4 , K), φ ′ S 2 (B 3 , K) and φ ′ S 3 (B 3 , K) on the corresponding largest Voronoi-Schubert cells (see section 9).
The interpretation of the geometry Γ(n, q) of the Chevalley group X n (q) as a special interpretation of the universal geometry U (X n , K) allows one to generate this object in computer memory in time O(|Γ(n, q)|) with fast algorithm (O(n 2 )) to check whether or not two elements of the geometry are incident. Notice that the incidence systems U S (X n , K) where K is a finite commutative ring are "computationally equivalent" to Γ(n, q).
The interpretation of Γ(n, q) as U S (X n , K) for specialisation S allows one to effectively generate small world graphs corresponding to double cosets of the form P i gP i and more general graphs corresponding to P i gP j such as the Double Grassman graphs of geometry A 2k+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 (X n , 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 (X n , K), one can find the naturally embedded geometry of the Weyl group W (X n ). So Voronoi-Schubert cells can be considered for each incidence graph of U S (X n , K). We believe that properties of this partition are important for spectrum investigation of small world graph defined in terms of U (X n , K).

Some basic definitions from Graph Theory and
Algebraic Combinatorics

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 G i (x) = {y : d(x, y) = i}. We sometimes write G(x) for G 1 (x). Also x ∼ y is used to denote that x ∈ G(y). Now fix x and y in V (G) with y ∈ G i (x). Define 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 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 F 1 and F 2 be disjoint sets of the same size as x, y ∈ V (G * ) we will write d * (x, y) for the distance from x to y. We also define φ : 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 x l , x 2 ∈ X we define x 1 ∈ G ′ (x 2 ) provided x 1 ∈ G 2 (x 2 ). G ′ is called a halved graph of G. More information on halved graphs may be found in [4].

On Coxeter groups, Tits systems and their geometries
An incidence system is a triple (Γ, I, t) where I is a symmetric antireflexive 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]).
An important example of an incidence system as described above is the so-called group incidence system Γ(G, G s ) s∈S . Here G is the abstract group and {G s } s∈S is the family of distinct subgroups of G. The objects of Γ(G, G s ) s∈S are the left cosets of G s in G for all possible s ∈ S. Cosets α and β are incident precisely when α ∩ β = ∅. The type function is defined by t(α) = s where α = gG s 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 = {s 1 , s 2 , . . . , s n } and generic relations (s i s j ) m ij = 1 for all 1 i, j n. Here M = (m ij ) is a symmetric n × n matrix with m ii = 1 and off-diagonal entries satisfying m ij 2 (allowing m ij = ∞ as a possibility, in which case the relation (s i s j ) m ij = 1 is omitted). Letting W i = S − {s i } , 1 i n, we obtain a group incidence system Γ(W ) = Γ(W, W i ) 1 i n which is called the Coxeter geometry of W . The subgroups W i 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 gs i g −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 {s 1 , s 2 , . . . , s n }.
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 = 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 P i of G defined by BW i B are called the standard maximal parabolic subgroups of G. The group incidence system Γ(G) = Γ(G, P i ) 1 i n 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 : gP i → wW i , where w is determined from the equality BgP i = BwP i . This morphism Retr is called a retraction.
Let us consider the totality F of conjugates of Borel subgroup B of the form B n = 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).

On association schemes, permutation groups and hypergroups
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 does not depend on the choice of the pair (a, b) ∈ R k . 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 Then orbitals of (G, X) are in one-to-one correspondence with double cosets of the form HgH, g ∈ G.
For each directed graph R i of an associative scheme we consider its adjacency matrix A i of size |X| × |X| with entries a(x, y) ∈ {0, 1} such that a(x, y) = 1 if and only if (x, y) ∈ R i . It follows from the definition of matrix product that 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 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): where A π is the n × n permutation matrix corresponding to the permutation π.
We also consider the totality H[G] of formal linear combinations of the symbols a 0 , a 1 , . . . , a d such that the relations give us the definition of an associative algebra with unity a 0 . This object is known in Functional Analysis as a hypergroup (see, [35], [36]). Note that a hypergroup is an abstract algebra with fixed basis {a 0 , a 1 , . . . , a d } and integer structure constants p k i,j 0. We will refer to nonisomorphic Bose-Mesner matrix algebras with the same hypergroups as hyper-equivalent BM algebras.

Two Cartan matrices with the same Coxeter group and large families of isospectral graphs
Let us consider the Coxeter-Dynkin diagrams X n with n nodes, where X stands for one of the letters B, C and D with n 3. For each X n we denote by W (X n ) and X n (q) the Weyl group and Chevalley group over the finite field F q , respectively.
Let {s 1 , s 2 , . . . , s n } be a set of Coxeter generators of W = W (X n ) with X = B or X = C, and let s n correspond to the extreme right node of the diagram X n . Let us consider the action of the group W (X n ) on its left cosets by its standard subgroup W n generated by the elements s 1 , s 2 , . . . , s n−1 . One can identify the variety (W : W n ) with a vector space F 2 n . The permutation group (W, (W : W n )) coincides with the affine transformations T A,b of the kind x → xA + b, where A is a permutation matrix, and x and b are row vectors from F 2 n . Thus W is a semidirect product of the symmetric group S n with the additive group of the vector space F 2 n . Let T be the linear map on F 2 n defined by Then the group T, s 1 , s 2 , . . . , s n−1 is isomorphic to S n+1 . Observe that the group W ′ = W, T is isomorphic to Weyl group W (D n+1 ). It is known that W (X n ) preserves Hamming distance d on F 2 n defined by the rule Hence, orbitals of the transitive permutation group W (X n ) are binary One can see that the orbitals of W ′ are φ 0 (equality relation) and Let us consider the Chevalley group X n (q) with Borel subgroup B acting on the totality of left cosets (X n (q) : P n ) by its standard parabolic subgroup P n = BW n B corresponding to the extreme right node of the Coxeter-Dynkin diagram. There is a natural one-to-one correspondence between orbitals of (X n (q), (X n (q) : P n )) and orbitals of (W (X n ), (W : W n )) (see [14]).
Let φ ′ i be the orbital of X n (q) corresponding to the orbital φ i of Weyl group W . Let S(Ω) be the symmetric group acting on the totality of left cosets Ω = (X n (q) : P n ). All proper subgroups G of S(Ω) such that X n (q) G are described in ( [10], [11]). The proof does not use the classification of finite simple groups.
If X = C then X n (q) < G < N (X n (q)), where the normaliser in S(Ω) is simply an extension of X n (q) via automorphisms of the ground field F q . So orbitals of N (C n (q)) and C n (q) are the same.
If X = B, then B n (q) < G < N (B n (q)) or D n+1 (q) < G < N (D n+1 (q)). The orbitals of groups B n (q) and D n+1 (q) coincide with orbitals of their respective normalisers, which are extensions of the corresponding Chevalley groups by automorphisms of the ground field F q (see [12] for the details).
We can describe orbitals of D n+1 (q) via special subsets of N = {1, 2, . . . , n}. In the case of even n, we refer to {i, i + 1} (1 i n/2) as generic subsets. In the case of odd n, our generic subsets are {i, i + 1} Let J be a proper subset of N = {1, 2, . . . , n}, and let C J = C J (n, q), B J = B J (n, q) be graphs of binary invariant relations i∈J φ ′ i of the respective permutation groups (C n (q), (C n (q) : P n )) and (B n (q), (B n (q) : P n )). Hecke algebras of (B n (q), (B n (q) : P n )) and (C n (q), (C n (q) : P n )) have the same intersectional indices (see [13] for closed formulae). This fact follows also from distance regularity of φ ′ . In fact, structure constants of the Hecke algebras of groups B n (q) and C n (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 B n . Theorem 1. Let J be a proper subset of N = {1, 2, . . . , n}. For each n 3, the graphs C J (n, q) and B J (n, q), where q ranges over various odd prime powers, form a family of non-Sunada twins for which Aut(C J (n, q)) = N (C n (q)), and Aut(B J (n, q)) = N (D n+1 (q)) if J is a union of generic subsets and Aut(B J (n, q)) = N (B J (n + 1, q)) in all other cases. Moreover, if J is generic set of cardinality 2 then for each n 3 the graphs C J (n, q) and B J (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 C J (n, q) and B J (n, q) form a balanced family of non-Sunada small world twins with respective automorphism groups N (C n (q)) and N (B n (q)). If J = {n} then the graphs C J (n, q) and B J (n, q) form a balanced family of small world non-Sunada twins with respective automorphism groups N (C n (q)) and N (D n+1 (q)).
Theorem 2. Let J be a proper subset of N = {1, 2, . . . , n}. For each n 3 the graphs C J (n, q) * and B J (n, q) * , where q ranges over various prime powers, form a family of non-Sunada twins with automorphism groups Aut(C J (n, q)) * = N (C n (q))×Z 2 , and Aut(B J (n, q)) * = N (D n+1 (q))×Z 2 if J is union of generic subsets and Aut(B J (n, q)) = N (B n+1 (q)) × Z 2 in all other cases. Moreover, if J is a generic set of cardinality 2, then for each n 3 the graphs C J (n, q) * and B J (n, q) * form a family of unbalanced non-Sunada twins.

Case of other nodes
We introduce orbitals of the Coxeter group W of type B n (or C n ) acting on left cosets by its maximal standard subgroup W i = s 1 , s 2 , . . . , s i−1 , s i+1 , s i+2 , . . . , s n for i = 1, 2, . . . , n. The Coxeter geometry of W is the disjoint union Γ of the sets Γ i = (W : W i ) of left cosets of W by W i with incidence relation I defined by αIβ provided α ∩ β = ∅ where α ∈ Γ i , β ∈ Γ j , i = j. It can be interpreted as follows (see for instance [6]): Let N = {1, 2, . . . , n}, and consider the sets for all x ∈ A ∩ B. The incidence system H is isomorphic to Γ. As always 2 N stands for totality of subsets of N .
The orbitals of W acting transitively on H t , 1 t n may be described as φ r,s = { ((A, f ), (B, g) Let us consider the action of G = X n (q) where X ∈ {B, C} on the left cosets of its maximal standard parabolic subgroup P t = Bw t B where B is the standard Borel subgroup of G, 1 t n. The orbitals X r,s of the permutation groups (G, (G : P t )) are in natural one-to-one correspondence with φ r,s of (W, (W : W t )). Let M (t) = {(r, s)|0 r s t}.
Theorem 3. Let M be a proper subset of M (t), t < n. Consider the action of G = X n (q) where X ∈ {B, C} on the set X(t, n, q) = (G : P t ) of left cosets of G by its maximal standard parabolic subgroup P t . Assume that each X M (n, t, q) is the disjoint union of X r,s for all (r, s) ∈ M (t). Then for all odd q 3 and parameters t and n, the pairs (B M (n, t, q), C M (n, t, q)) form a family of non-Sunada graphs with respective automorphism groups N (B n (q)) and N (C n (q)).

Remarks on Schubert geometry, some conjectures
Let us consider the action of the group X n (q) on the geometry Γ(X n (q)), which is the disjoint union of X(n, t, q), 1 t n, as well as the natural action of X n (q) on X 2 (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 X n (q) acting on the elements of its geometry Γ(W n (q)), which is the disjoint union of W (n, t) = (W : W t ).
Specifically, orbits of (X n (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 P i wP j and W i wW j for 1 i, j t (see [14], [15] and further references).
The orbits of G = X n (q) on Γ i (G) × Γ j (G) are in a natural one-toone 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 X n (q). The totality of elements of Γ(X n (q)) containing T with the restriction of the incidence relation I to this subset is isomorphic to the Weyl geometry Γ(W n (q)). There is well defined homomorphic retraction map Retr from Γ(X n (q)) onto Γ(W n (q)) (see [16] and further references).
Let H i = H X i = H X i (n, q) be the subset of elements hP i from Γ i (X n (q)) such that Retr(hP i ) = β i . We refer to the incidence system H = H 1 ∪ H 2 · · · ∪ H t with the restriction I ′ to this set as the Schubert geometry H = H(X n (q)). It is easy to check that the standard Borel subgroup B acts regularly on maximal flags of H.
Note that for i = j, the restriction of I ′ to H i ∪ H j is a biregular bipartite graph. We may assume that Γ(W n ) is the subset of elements of Γ(X n (q)) containing a maximal torus. For each element γ from H i (X n (q)) and each β j we consider the list L j i (γ) of types of orbits R of (X n (q), Γ i ×Γ j ) that contain (γ, β j ). We say that γ 1 , γ 2 from H i are Weyl-equivalent if L j i (γ 1 ) = L j 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 i 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 We refer to unions of Weyl-equivalent orbitals as Weyl pseudo-orbitals of (B, H i ). We define type of a pseudo-orbital as a list L j i (γ), 1 j n, where (β i , γ) ∈ R. The partition into psudo-orbitals is defined in terms of the Coxeter matrix of the group W (B n ) = W (C n ). Thus, cardinalities of pseudo-orbitals of B(B n (q)) and B(C n (q)) of a given type are of the same cardinality.

Conjecture 1.
Let Ω be the set of all types of pseudo-orbitals of (B, H i ) and let J = ∅ 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 = 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(B n (q)), N (B(C n (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(D n+1 (q)) and N (B(C n (q)).

New distance-regular graphs and non-Sunada twins
For prime powers q, Pasechnik [18] constructed a distance-regular graph with intersection array {q 3 , q 3 − 1, q 3 − q, q 3 − q 2 + 1, 1, q, q 2 − 1, q 3 } as a subgraph of the dual polar graph D 4 (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 = Z q with intersection array {q 3 − 1, q 3 − q · q 3 − q 2 + 1, 1, q, q 2 − 1} as follows: Consider the vector space F q 3 equipped with the standard cross product ×. The vertex set is 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 B 3 (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 Z 3 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 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 Z q is a largest Schubert cell of B 3 (q) acting on dual polar spaces, i.e. a largest orbit of the Borel subgroup is an overgroup of the permutation group (B 3 (q), B(3, q)); the stabilizer of Z(q) in D 4 (q) is isomorphic to the Borel subgroup B 4 = B 4 (q) of this group. Group D 4 (q) has orbitals which form a fusion scheme of the association scheme of orbitals (B 3 (q), Z(q)). The distance in the graph Z q defines an association scheme R which is a fusion of orbital schemes of D 4 (q) and B 3 (q). For two types T 1 and T 2 of pseudo-orbitals δ 1 and δ 2 of B 3 (q), we write T 1 ∼ T 2 mod (D 4 ) and say they are D 4 -equivalent if there is an orbital φ of B(D 4 (q)) such that φ ∩ δ i = ∅ for i = 1, 2. We refer to minimal sets of D 4 -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 4) forms an association scheme with the same intersection indices as scheme R. Let s q = s 1 q . It is easy to see that S q = Z q in the case of even q. In the case of odd q, the groups Aut(Z q ) and Aut(S q ) are normalisers N 1 = N (B 4 ) and N 2 = N (B(P SP 6 (q))) of Borel subgroups of D 4 (q) and C 3 (q) in the corresponding symmetric groups.
Theorem 4. For odd q, the distance-regular graphs Z q and S q have the same parameters, and form a family of edge-intransitive non-Sunada small world twins with respective automorphism groups N (D 4 (q)) and N (C 3 (q)). Proposition 1. Let M be a nonempty proper subset of {1, 2, 3, 4}. Then the unions Z M q = i∈M z i q and S M q = i∈M s i q 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 Z q and S q , respectively, form a family of distance-regular non-Sunada twins with respective automorphism groups N 1 × Z 2 and N 2 × Z 2 .

Case of the diagram A n , the twisted Grassmann graphs
In [21] van Dam and Koolen constructed the first family of non-vertextransitive distance-regular graphs with unbounded diameter. These graphs, 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 F q , 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 J q (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 vertextransitive (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 counterexamples 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 J q (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.

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 (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 In the above, the V i 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, v i ) = d(y, v i ) 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) = (d 1 , d 2 , . . . , d n ) where 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.
In the case of finite graphs, we say that (Γ 1 , S 1 ) and (Γ 2 , S 2 ) 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 X l (F ) has a BN -pair and finite irreducible Weyl group W . Fixed points of a maximal torus T in its action on Γ(X l (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 (X l ). So we have a natural embedding of W (X l ) into Γ = Γ(X l (F )). Let I(X l (F )) denote the incidence relation of Γ. We are interested in studying Vor(Γ(G), S).

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(B n (F )), W (B n )) and (I(C n (F )), W (C n )) 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 (a 1 , b 1 ) and 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 Γ(B n (F )) and Γ(C n (F )) are Voronoi-equivalent.
Remark. Observe that isospectrality of the graphs corresponding to the orbitals (B n (q), Γ i (B n (q)) and (C n (q), Γ i (C n (q)) may be deduced from this statement.
Let us consider a partition P = {R 0 , R 1 , . . . , R k } of the Cartesian square V 2 such that all graphs R i are regular (recall that R 0 is the equality relation on V ). The partition of V 2 into R i orbitals coincides with some fusion of partition P . We refer to such P as a Voronoi graph configuration.
Example. Let (G, V ) be a transitive transformation group on V . Then each partition of V 2 into R i orbitals will be a Voronoi graph configuration.
Theorem 8. Consider the groups B n (F ) and C n (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.

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 = V 1 ∪ V 2 ∪ · · · ∪ V n , 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 = P s,m = K s+m and line set L = L r,m = K r+m as a linguistic incidence structure I m if the point if and only if the following relations hold: . . , x s , y 1 , y 2 , . . . , y r ) . , x s , x s+1 , y 1 , y 2 , . . . , y r , y r+1 ) . . . ξ m x s+m + ζ m y r+m = f m (x 1 , x 2 , . . . , x s+m−1 , y 1 , y 2 , . . . , y r+m−1 ) In the above, ξ j and ζ j , j = 1, 2, . . . , m, are not zero divisors, and the functions f j are multivariate polynomials with coefficients from K. Brackets and parenthesis allow us to distinguish points from lines (see [22]).
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 ∈ K r and (p) = (p 1 , p 2 , . . . , p s+m ) there is a unique neighbour of the point 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 S i and S j from Γ i (G) and Γ j (G), i = j, and assume that the restriction of incidence relation I to S i ∪ S j 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 S i,j (G) be the incidence graph of the restricted geometry to the two largest Schubert cells S i and S j , i.e. the totality of cosets BgP i and BgP j where g ∈ W is an element with maximal length l(g) (a so-called Coxeter element). We refer to S i,j (G) as a Schubert graph.

Conjecture 4.
Let q be an arbitrary odd power. Then the Schubert graphs S i,j (B n (q)) and S i,j (C n (q)) form families of edge-transitive non-Sunada graphs.
Conjecture 5. Let F be an arbitrary field, then the graphs S i,j (B n (F )) and S i,j (C n (F )) are Voronoi-equivalent.
Remark. In the case of a field of odd characteristic or characteristic zero, the graphs S i,j (B n (F )) and S i,j (C n (F )) are nonisomorphic.
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 L i,j is given with its (η(i), η(j)) interpretation. We refer to such data as a linguistic configuration with a governing triple (Γ, η, Ω) and linguistic relations L i,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 L i,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 A i for the set η(i). For each set A ⊂ Ω we consider the list of all its elements a 1 , a 2 , . . . , a m and the ring where x a i are formal variables.
Let us consider a class of Coxeter lingustic configurations with corresponding incidence graph I of the Coxeter geometry Γ(W ) and boolean embedding ∆ : α → 2 T . 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 L i,j , iIj is bilinear if there is a bilinear product × on L = K Ω and family of functions l i : Ω → K, i ∈ V (Γ), such that the incidence relation on each linguistic graph may be written as x(s)l j (s)−y(s)l i (s) = (x×y)(s), for x ∈ L i , y ∈ L j and s ∈ ∆(i) ∪ ∆(j).
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 e r ∈ K Ω such that e r (r) = 1 and e r (r ′ ) = 0 for r = 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 e r × e ′ r = λ r,r ′ e f (r,r ′ ) . Here, λ r,r ′ ∈ K under the assumption that e r × e ′ r = 0 if (r, r ′ ) is not in the domain of f .

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 = X l (K) to signify that G is a Chevalley group over the field K with associated Dynkin diagram X l . We are mostly interested in the case when K is finite, and we shall write X l (q) instead of X l (F q ) in such case. So, fix a Chevalley group G = X l (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 Γ = Γ(X l (F )) be the Lie geometry of a simple Chevalley 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 incidence 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 X n (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 β,α 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 Γ(X n , K) of U G S (X n , K) to elements of the kind (W i , 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 (X n , K) is bounded above by 2l(n).
In the case of a fixed n and S and family of finite rings K = K m of increasing order, the graphs Γ S (X n , K m ), m 1, form a family of small world graphs with unbounded degree (see [37] for related geometrically based constructions and further references).