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
    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
    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