Disconnected vertex sets and equidistant code pairs (Q1378495)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Disconnected vertex sets and equidistant code pairs |
scientific article |
Statements
Disconnected vertex sets and equidistant code pairs (English)
0 references
12 February 1998
0 references
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.
0 references
alphabet
0 references
words
0 references
Hamming distance
0 references
equidistant code pair
0 references
disconnected sets
0 references
eigenvalues
0 references
matrix
0 references
assiciation scheme
0 references
Hamming scheme
0 references