Disconnected Vertex Sets and Equidistant Code Pairs

Abstract

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.