# Disconnected vertex sets and equidistant code pairs.

Authors
Source
Legacy
Disciplines
• Communication
• Mathematics

## Abstract

Disconnected vertex sets and equidistant code pairs Willem H. Haemers Department of Econometrics, Tilburg University, Tilburg, The Netherlands; e-mail: [email protected] Submitted: October 28, 1996; Accepted: January 29, 1997. Abstract Two disjoint subsets A and B of a vertex set V of a flnite 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 f1; : : : ; qg and if two words are adjacent whenever their Hamming distance is not equal to a flxed – 2 f1; : : : ; ng, then a pair of disconnected sets becomes an equidistant code pair. For disconnected sets A and B we will give a bound for jAj ¢ jBj 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 !1 for any flxed n and –. In addition, our bound reproves some old results of Ahlswede and others, such as the maximal value of jAj ¢ jBj for equidistant code pairs A ans B in the binary Hamming Scheme. 1 Introduction Throughout G is a flnite graph with vertex set V . Two disjoint subsets A and B of V are disconnected if there is no edge between A and B. We deflne '(G) to be the maximum of q jAj ¢ jBj for disconnected sets A and B in G. Suppose V is the set of words of length n over an alphabet f1; : : : ; qg and deflne two words adjacent if their Hamming distance (i.e. the number of coordinates in which they difier) is not equal to a flxed – 2 f1; : : : ; ng. Then a pair of disconnected sets becomes an equidistant code pair. the electronic journal of combinatorics 4 (1997), #R7 2 The quantity '(G) has an application in information theory and leads to a lower bound for the two-way communication complexity of functions deflned on V £V that are constant over the non-edges of G. About ten years ago this

Seen <100 times