zbMATH — the first resource for mathematics

Characterizing completely regular codes from an algebraic viewpoint. (English) Zbl 1231.05300
Brualdi, Richard A. (ed.) et al., Combinatorics and graphs. Selected papers based on the presentations at the 20th anniversary conference of IPM on combinatorics, Tehran, Iran, May 15–21, 2009. Dedicated to Reza Khosrovshahi on the occasion of his 70th birthday. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4865-4/pbk). Contemporary Mathematics 531, 223-242 (2010).
Summary: The class of completely regular codes includes not only some of the most important error-correcting codes, such as perfect codes and uniformly packed codes, but also a number of substructures fundamental to the study of distance-regular graphs themselves.
In a companion paper, we study products of completely regular codes and codes whose parameters form arithmetic progressions. This family of completely regular codes, while quite special in one sense, contains some very important examples and exhibits some of the nicest features of the larger class. Here, we approach these features from an algebraic viewpoint, exploring \(Q\)-polynomial properties of completely regular codes and introducing Leonard completely regular codes.
After reformulating some basic background on completely regular codes in a unified way, we propose the study of a certain class of codes where the eigenspaces of the code are naturally arranged in a linear order. In addition to the arithmetic codes of the companion paper, this highly structured class of codes, which we call Leonard completely regular codes, includes other interesting examples and we propose their classification in the Hamming graphs. The main result of the paper shows that the Leonard condition is equivalent to the presence of a certain Leonard pair acting on the outer distribution module. This connection has impact in two directions. First, the Leonard pairs have been classified by Terwilliger and we gain quite a bit of information about the algebraic structure of any code in our class. But also this gives a new setting for the study of Leonard pairs, one closely related to the classical one – where a Leonard pair arises from each thin/dual-thin irreducible module of a Terwilliger algebra of some \(P\)- and \(Q\)-polynomial association scheme yet not previously studied. It is particularly interesting that the Leonard pair associated to some code \(C\) may belong to one family in the Askey scheme while the distance-regular graph containing the code may belong to another.
For the entire collection see [Zbl 1202.05003].

05E30 Association schemes, strongly regular graphs
94B25 Combinatorial codes
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)