Eigenspace embeddings of imprimitive association schemes
Janoš Vidali · 2025
Read Eigenspace embeddings of imprimitive association schemes by Janoš Vidali (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-08733.txt.
Introduction
Janoš Vidali studied embeddings of a class of algebraic structures in a 2025 mathematics paper. Association schemes organize pairs of objects into relations, and each scheme carries eigenspaces into which its points can be mapped as unit vectors. In such spherical pictures, the angle between two vectors depends only on the relation between the points. Vidali used these pictures to test whether certain proposed schemes can exist at all.
The targets were open parameter sets for quotient-polynomial graphs, listed by Herman and Maleki. By embedding substructures into eigenspaces in ways consistent with the spherical picture, the author ruled out two parameter sets for four-class schemes and one for a five-class scheme. Each had passed every previously known feasibility check. Two other five-class sets were shown to be unique if they exist.
Catalog record
| CREATOR | Janoš Vidali |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-08733
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Eigenspace embeddings of imprimitive association schemes Janoš Vidali Abstract . For a given symmetric association scheme 𝒜 \mathcal{A} and its eigenspace S j S_{j} there exists a mapping of vertices of 𝒜 \mathcal{A} to unit vectors of S j S_{j} , known as the spherical representation of 𝒜 \mathcal{A} in S j S_{j} , such that the inner products of these vectors only depend on the relation between the corresponding vertices; furthermore, these inner products only depend on the parameters of 𝒜 \mathcal{A} . We consider parameters of imprimitive association schemes listed as open cases in the list of parameters for quotient-polynomial graphs recently published by Herman and Maleki, and study embeddings of their substructures into some eigenspaces consistent with spherical representations of the putative association schemes. Using this, we obtain nonexistence for two parameter sets for 4 4 -class association schemes and one parameter sets for a 5 5 -class association scheme passing all previously known feasibility conditions, as well as uniqueness for two parameter sets for 5 5 -class association schemes. 2020 Mathematics Subject Classification 05E30 1. Introduction Association schemes were first introduced within the theory of experimental design, however, since Delsarte [ 9 ] , they have been primarily studied as combinatorial objects of their own, representing the basic underlying structures in various fields such as coding theory, design theory, and finite geometry. Much of the research on association schemes has been focused on some special cases, such as strongly regular graphs (i.e., 2 -class association schemes), distance-regular graphs (corresponding to P -polynomial association schemes) and Q -polynomial association schemes. Nevertheless, even for these subfamilies, a complete classification is still a widely open problem. Tables of feasible parameters for various families of association schemes have been compiled, in particular, by Brouwer et al. [ 4 , 5 , 6 ] for strongly regular and distance-regular graphs, and by Williford [ 13 , 36 ] for Q -polynomial association schemes. Recently, two new surveys of feasible parameter sets of association schemes have been compiled by Herman and Maleki: one for association schemes with noncyclotomic eigenvalues [ 19 ] and one for quotient-polynomial graphs [ 18 , 20 ] . Contributions to the classification of association schemes come in the form of new constructions and characterizations of association schemes with a certain parameter set or belonging to a family of parameter sets – in particular, it may be possible to prove that there is a unique association scheme with a given parameter set (uniqueness proof), or that there are none (nonexistence proof). Many families and sporadic examples of association schemes are known, and constructing new ones, particularly in the more studied subfamilies, has proved to be increasingly difficult. On the other hand, there are many parameter sets which pass the known feasibility conditions, but no corresponding association scheme has been constructed; there are also many cases when one or more corresponding association schemes are known, but it is not known whether there are any more. One of the techniques that can be used to study association schemes is to study their spherical representations in their eigenspaces. Bannai, Bannai and Bannai [ 3 ] have used this technique to prove uniqueness of two association schemes arising from spherical codes; more recently, Gavrilyuk and Suda [ 12 ] have used a similar technique to prove uniqueness of an association scheme related to the Witt design on 11 points. In the present paper, we apply such a technique to study imprimitive association schemes with parameters which are listed as open cases in the aforementioned list of parameter sets of association schemes corresponding to quotient-polynomial graphs. We first apply the known feasibility conditions and find numerous cases when they either rule out a parameter set, or there is a known example (see Appendix A ). Then, using software [ 34 , 35 ] developed on top of the SageMath computer algebra system [ 28 ] , we conduct some computer searches and conclude nonexistence for three of the cases that satisfy the known feasibility conditions, and uniqueness for two more cases. 2. Preliminaries In this section we review some basic definitions and concepts. See Brouwer, Cohen and Neumaier [ 6 ] for further details. Let X be a set of n vertices , and R\subseteq X^{2} a binary relation on X . The matrix A\in\{0,1\}^{X\times X} such that A_{xy}=1 if and only if (x,y)\in R is called the adjacency matrix of the relation R . If R is an irreflexive relation, then the pair \Gamma=(X,R) is called a (simple, directed) graph – such a graph has the set X as its vertex set and the set R as its arc set (i.e., the set of its directed edges), and A is its adjacency matrix. In the case when R is a symmetric relation, we will understand the graph \Gamma to be undirected, and its edges are precisely the unordered pairs \{x,y\} such that (x,y)\in R . For a subset Y\subseteq X , we define the induced subgraph of \Gamma on Y as \Gamma|_{Y}=(Y,R|_{Y}) , where R|_{Y}=\{(x,y)\in R\mid x,y\in Y\} is the restriction of the relation R onto the subset Y . Let \mathcal{R}=\{R_{i}\mid i\in\mathcal{I}\} , where \mathcal{I} is an index set of size d+1 for some d , be a partition of X^{2} such that \operatorname{Id}_{X}:=\{(x,x)\mid x\in X\}\in\mathcal{R} and \emptyset\not\in\mathcal{R} – i.e., \mathcal{R} is a set of binary relations on X containing the identity relation such that each pair of vertices of X lies in precisely one relation of \mathcal{R} . A relation scheme is defined by a pair \mathcal{A}=(X,\mathcal{R}) . A non-identity relation of \mathcal{R} is also called a class , so we may refer to \mathcal{A} as a d -class relation scheme . Customarily, we will have \mathcal{I}=\{0,1,\dots,d\} and R_{0}=\operatorname{Id}_{X} , although we may occasionaly deviate from this convention. A relation scheme may be concisely represented by its relation matrix M\in\mathcal{I}^{X\times X} satisfying (x,y)\in R_{M_{xy}} ( x,y\in X ). An isomorphism between relation schemes \mathcal{A}=(X,\mathcal{R}) and \mathcal{A}^{\prime}=(X^{\prime},\mathcal{R}^{\prime}) is a pair (\phi,\psi) of bijective maps \phi:X\to X^{\prime} and \psi:\mathcal{R}\to\mathcal{R}^{\prime} such that for each pair of vertices x,y\in X and for each relation R\in\mathcal{R} we have (x,y)\in R if and only if (x^{\phi},y^{\phi})\in R^{\psi} . The relation schemes \mathcal{A} and \mathcal{A}^{\prime} are isomorphic if there exists such an isomorphism. An automorphism of \mathcal{A} is an isomorphism between \mathcal{A} and itself. If all the relations of \mathcal{R} are symmetric, then \mathcal{A} is called a symmetric relation scheme . For a subset Y\subseteq X , we define the induced subscheme of \mathcal{A} on Y as \mathcal{A}|_{Y}=(Y,\mathcal{R}|_{Y}) , where \mathcal{R}|_{Y}=\{R|_{Y}\mid R\in\mathcal{R}\}\setminus\{\emptyset\} is the restriction of the partition \mathcal{R} onto the subset Y . Note that (\operatorname{Id}_{X})|_{Y}=\operatorname{Id}_{Y}\in\mathcal{R}|_{Y} , so \mathcal{A}|_{Y} is also a relation scheme. Clearly, if \mathcal{A} is symmetric, \mathcal{A}|_{Y} is symmetric as well. Suppose that \mathcal{A}=(X,\mathcal{R}) is a symmetric relation scheme with the additional property that there exist numbers p^{h}_{ij} ( h,i,j\in\mathcal{I} ) such that for each pair (x,y)\in R_{h} , there are precisely p^{h}_{ij} vertices z\in X with (x,z)\in R_{i} and (z,y)\in R_{j} . Then \mathcal{A} is called a (symmetric) association scheme , and the numbers p^{h}_{ij} ( h,i,j\in\mathcal{I} ) are its intersection numbers . The number k_{i}:=p^{0}_{ii} is the valency of the relation