Disconnected vertex sets and equidistant code pairs (Q1378495)

Summary: 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|\cdot |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|\cdot |B|\) for equidistant code pairs \(A\) and \(B\) in the binary Hamming scheme.