Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Disconnected vertex sets and equidistant code pairs. | Disconnected vertex sets and equidistant code pairs Willem H. Haemers Department of Econometrics Tilburg University Tilburg The Netherlands e-mail haemers@ Submitted October 28 1996 Accepted January 29 1997. Abstract Two disjoint subsets A and B of a vertex set V of a hnite 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 . qg and if two words are adjacent whenever their Hamming distance is not equal to a hxed Ỏ 2 1 . ng 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 1 for any hxed 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. 1 Introduction Throughout G is a hnite 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 dehne G to be the maximum of ự1 A B for disconnected sets A and B in G. Suppose V is the set of words of length n over an alphabet 1 . qg and dehne two words adjacent if their Hamming distance . the number of coordinates in which they differ is not equal to a hxed 2 1 . 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 dehned on V V that are constant over the non-edges of G. About ten years ago this application caused some activity in the study of equidistant code pairs. The best result
