An Algorithmic Approach to the Extensibility of Association Schemes
From MaRDI portal
Publication:6235973
arXiv1209.6312MaRDI QIDQ6235973FDOQ6235973
Authors: Manuel Arora, Paul-Hermann Zieschang 
Publication date: 27 September 2012
Abstract: An association scheme which is associated to a height t presuperscheme is said to be extensible to height t. Smith (1994, 2007) showed that an association scheme X=(Q,Gamma) of order d:=|Q| is Schurian iff X is extensible to height (d-2). In this work, we formalize the maximal height t_max(X) of an association scheme X as the largest positive integer such that X is extensible to height t (we also include the possibility t_max(X)=infty, which is equivalent to t_max(X)ge (d-2)). Intuitively, the maximal height provides a natural measure of how close an association scheme is to being Schurian. For the purpose of computing the maximal height, we introduce the association scheme extension algorithm. On input an association scheme X=(Q,Gamma) of order d:=|Q| and an integer t such that 1le tle (d-2), the association scheme extension algorithm decides in time d^(O(t)) if the scheme X is extensible to height t. In particular, if t is a fixed constant, then the running time of the association scheme extension algorithm is polynomial in the order of X. The association scheme extension algorithm is used to show that all non-Schurian association schemes up to order 26 are completely inextensible, i.e. they are not extensible to a positive height. Via the tensor product of association schemes, the latter result gives rise to a multitude of examples of infinite families of completely inextensible association schemes.
Combinatorics in computer science (68R05) Symbolic computation and algebraic computation (68W30) Association schemes, strongly regular graphs (05E30) Complexity of computation (including implicit computational complexity) (03D15)
This page was built for publication: An Algorithmic Approach to the Extensibility of Association Schemes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6235973)
