Disconnected vertex sets and equidistant code pairs

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, . . . , q} and if two words are adjacent whenever their Hamming distance is not equal to a fixed δ ∈ {1, . . . , 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 δ, and for q → ∞ for any fixed n and δ. 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 ans B in the binary Hamming Scheme.