Disconnected vertex sets and equidistant code pairs

Willem H. Haemers

The electronic journal of combinatorics, Tome 4 (1997) no. 1

Résumé

Two disjoint subsets $A$ and $B$ of a vertex set $V$ of a finite graph $G$ are called disconnected if there is no edge between $A$ and $B$. If $V$ is the set of words of length $n$ over an alphabet $\{1,\ldots,q\}$ and if two words are adjacent whenever their Hamming distance is not equal to a fixed $\delta\in\{1,\ldots,n\}$, then a pair of disconnected sets becomes an equidistant code pair. For disconnected sets $A$ and $B$ we will give a bound for $|A|.|B|$ in terms of the eigenvalues of a matrix associated with $G$. In case the complement of $G$ is given by a relation of an association scheme the bound takes an easy form, which applied to the Hamming scheme leads to a bound for equidistant code pairs. The bound turns out to be sharp for some values of $q$, $n$ and $\delta$, and for $q\rightarrow\infty$ for any fixed $n$ and $\delta$. In addition, our bound reproves some old results of Ahlswede and others, such as the maximal value of $|A|.|B|$ for equidistant code pairs $A$ and $B$ in the binary Hamming Scheme.

Détail

DOI : 10.37236/1292

Classification : 05C50, 05E30
Mots-clés : alphabet, words, Hamming distance, equidistant code pair, disconnected sets, eigenvalues, matrix, assiciation scheme, Hamming scheme