Disconnected vertex sets and equidistant code pairs

Willem H. Haemers

Department of Econometrics, Tilburg University, Tilburg, The Netherlands; e-mail: haemers@kub.nl

Submitted: October 28, 1996; Accepted: January 29, 1997.

Abstract

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, …, q} and if two words are adjacent whenever their Hamming distance is not equal to a fixed δ ∈ {1, …, 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| · |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 → ∞ for any fixed 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 finite 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 define Φ(G) to be the maximum of \sqrt{|A| · |B|} for disconnected sets A and B in G. Suppose V is the set of words of length n over an alphabet {1, …, q} and define two words adjacent if their Hamming distance (i.e. the number of coordinates in which they differ) is not equal to a fixed δ ∈ {1, …, n}. Then a pair of disconnected sets becomes an equidistant code pair.

The quantity Φ(G) has an application in information theory and leads to a lower bound for the two-way communication complexity of functions defined 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 is due to Ahlswede [1], who gives the exact value of Φ(G) for q = 2, 4 and 5, for every δ and n.

In this paper we will give a bound for Φ(G) in terms of eigenvalues of a matrices 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. This bound is not as accurate as Ahlswede’s result, but it is more general and it turns out to be sharp for some values of q, n and δ, and for q → ∞ for any fixed n and δ.

2 Disconnected vertex sets

Let V = {1, …, v}. We define M(G) to be the collection of symmetric v × v matrices M with all row and column sums equal to 1, such that (M)_{i,j} = 0 if i and j are distinct non-adjacent vertices of G. Let λ_{1}(M), …, λ_{v}(M) denote the eigenvalues of a matrix M ∈ M(G), such that λ_{1}(M) has eigenvector \underline{1} (the all-one vector), so λ_{1}(M) = 1. Put

λ(M) = max_{i≠1} |λ_{i}(M)|.

Lemma 2.1 If A and B are disconnected vertex sets of G and M ∈ M(G), then

\frac{|A| · |B|}{(v − |A|)(v − |B|)} ≤ λ^{2}(M).

Proof. See [7] Theorem 2.1, or [11] Lemma 6.1. □

Theorem 2.2 For any M ∈ M(G)

Φ(G) ≤ v \frac{λ(M)}{1 + λ(M)} .

Proof. Put Φ = Φ(G) and take A and B such that Φ^{2} = |A| · |B|. Then by Lemma 2.1

\frac{Φ^{2}}{λ^{2}(M)} ≤ (v^{2} − v(|A| + |B|) + Φ^{2}) ≤ (v^{2} − 2v\sqrt{|A| · |B|} + Φ^{2}) = (v − Φ)^{2}.

Clearly v ≥ Φ, so Φ ≤ (v − Φ)λ(M), which yields the required bound. □

In order to investigate when the bound of Theorem 2.2 is best possible, we define

ϕ(G) = min_{M∈M(G)} v \frac{λ(M)}{1 + λ(M)}

and we let M′(G) denote the set of matrices from M(G) for which the above minimum is attained. Thus Theorem 2.2 becomes Φ(G) ≤ ϕ(G). To determine ϕ(G) we need to find a matrix in M′(G). For that purpose the automorphisms of G can be helpful.

Lemma 2.3 Let A be an automorphism group of G. Then M′(G) contains a matrix which is constant over each orbit of the action of A on V × V.

Proof. Let P_{g} denote the permutation matrix corresponding to g ∈ A and take M′ ∈ M′(G). Then clearly P_{g}M′P_{g}^{⊤} ∈ M′(G) and, by Rayleigh’s principle, |u^{⊤}P_{g}M′P_{g}^{⊤}u| ≤ λ(M′) for every unit vector u orthogonal to \underline{1} . Define

\overline{M} = \frac{1}{|A|} ∑_{g∈A} P_{g}M′P_{g}^{⊤},

then clearly \overline{M} ∈ M(G) and \overline{M} is constant over A-orbits on V × V. Let u (u ⊥ \underline{1}) be a unit eigenvector for the eigenvalue ±λ(\overline{M}). Then λ(\overline{M}) = |u^{⊤}\overline{M}u| ≤ λ(M′), so λ(\overline{M}) = λ(M′) and hence \overline{M} ∈ M′(G). □

In particular we may take the diagonal constant if G has a transitive automorphism group. Theorem 2.2 leads to a more explicit bound in terms of the Laplacian eigenvalues of G. (If A is the standard adjacency matrix of G and D is the diagonal matrix containing the vertex degrees, then F = D − A is the Laplacian matrix of G. It easily follows that F is positive semi-definite and singular; see for example Brualdi and Ryser [6].)

Theorem 2.4 Suppose F is the Laplacian matrix of G and let 0 = μ_{1} ≤ μ_{2} ≤ … ≤ μ_{v} be the eigenvalues of F, then

ϕ(G) ≤ \frac{v}{2} (1 − \frac{μ_{2}}{μ_{v}} )

with equality if G has an automorphism group that acts transitively on the edges.

Proof. Define

M = \frac{−2}{μ_{2} + μ_{v}} F + I.

Then M ∈ M(G) and λ(M) = (μ_{v} − μ_{2})/(μ_{v} + μ_{2}), which yields the inequality.

Suppose G has an automorphism group which acts transitively on the edges. Then, by Lemma 2.3 there exists a matrix M′ ∈ M′(G) such that M′ = xF + D for some constant x and diagonal matrix D. Now M′\underline{1} = \underline{1} gives D = I and so

λ(M′) = max{|xμ_{2} + 1|, |xμ_{v} + 1|}.

It follows that λ(M′) is minimal if xμ_{2} + 1 = −xμ_{v} − 1, that is, if x = −2/(μ_{2} + μ_{v}). Thus M ∈ M′(G). □

Example. Suppose G is the triangular graph T (2m) (that is, the line graph of K_{2m}). Then v = m(2m − 1), μ_{2} = 2m and μ_{v} = 4m − 2. Theorem 2.4 gives ϕ(G) = \binom{m}{2}. We easily have that Φ(G) ≥ \binom{m}{2}, so Φ(G) = \binom{m}{2}.

Next we consider association schemes. For theory and notation see [4], [5] or [9]. Let S be an n-class association scheme defined on the set V with relations R_{0}, …, R_{n}. For δ ∈ {1, …, n} we denote by G_{δ} the graph (V, R_{δ}) and by G\overline{δ} the complement of G_{δ}.

Theorem 2.5 If Q is the matrix of dual eigenvalues of S, then

ϕ(G\overline{δ}) ≤ \frac{v}{∑_{j=0}^{n} |Q_{δ,j}|} .

Equality holds if the automorphism group of S acts transitively on each relation.

Proof. Let A_{0}, …, A_{n} (with A_{0} = I) be the adjacency matices of S and let E_{0}, …, E_{n} (with vE_{0} = J, the all-one matrix) be the minimal idempotents. Then the matrix Q of dual eigenvalues is given by

vE_{j} = ∑_{i=0}^{n} Q_{i,j}A_{i}, for j = 0, …, n.

So v(E_{j})_{k,l} = Q_{δ,j} whenever {k, l} ∈ R_{δ}. Define P_{δ} = {j|1 ≤ j ≤ n, Q_{δ,j} > 0\}, m = ∑_{j∈P_{δ}} Q_{δ,j} + \frac{1}{2} and

M = \frac{1}{m}(\frac{1}{2}I − ∑_{j∈P_{δ}}(E_{j} − Q_{δ,j}E_{0})).

Then, since E_{j}\underline{1} = \underline{0} for j ≠ 0 one readily verifies that M ∈ M(G\overline{δ}). Moreover ∑_{j∈P_{δ}} E_{j} has only 0 and 1 as eigenvalues. This implies that λ_{i}(M) = ±\frac{1}{2m} for i ≠ 1, so λ(M) = \frac{1}{2m}, and thus we find ϕ(G\overline{δ}) ≤ \frac{v}{2m+1}. By use of ∑_{j=0}^{n} Q_{δ,j} = 0 and Q_{δ,0} = 1, we obtain

m + \frac{1}{2} = 1 + ∑_{j∈P_{δ}} Q_{δ,j} = \frac{1}{2} ∑_{j=0}^{n} |Q_{δ,j}|,

and the required inequality follows.

Next assume that S admits an automorphism group which is transitive on each relation. Then by Lemma 2.3 there exists a matrix M′ ∈ M′(G\overline{δ}) which is a linear combination of A_{0}, …, A_{n}, that is, M′ is in the Bose-Messner algebra of S. Let λ_{j′}(M′) denote the eigenvalue of M′ whose eigenspace is given by E_{j}. We claim that we may assume that λ_{j′}(M′) = λ(M′) if Q_{δ,j} ≤ 0. Indeed, suppose this is not the case, then define d = λ(M′) − λ_{j′}(M′), m = 1 − dQ_{δ,j} and M′′ = \frac{1}{m}(M′ + d(E_{j} − Q_{δ,j}E_{0})). It follows that M′′ ∈ M(G\overline{δ}), m ≥ 1 and λ_{j′}(M′′) = λ(M′′) = \frac{1}{m}λ(M′) ≤ λ(M′). So we can redefine M′ = M′′, which proves the claim. Similarly, we may assume that λ_{j′}(M′) = −λ(M′) if Q_{δ,j} ≥ 0 and j ≠ 0. It now follows that

E = \frac{1}{2λ(M′)}(λ(M′)I − M′ + (λ(M′) − 1)E_{0})

has eigenvalue 0 and 1 only, and hence E is an idempotent of S. Therefore E is the sum of those E_{j} that correspond to the eigenvalue 1 of E, that is E = ∑_{j∈P_{δ}} E_{j}. In addition, since (M′)_{k,l} = 0 for {k, l} ∈ R_{δ}, we have ∑_{j∈P_{δ}} Q_{δ,j} = \frac{1}{2λ(M′)} − \frac{1}{2}. This implies that M′ = M, so M ∈ M′(G\overline{δ}). □

A graph G\overline{δ} in a 2-class association scheme is the same as a strongly regular graph. An example of such a graph is the triangular graph T (m), described in the example above. It is not difficult to see that for strongly regular graphs the bounds of Theorem 2.4 and Theorem 2.5 coincide.

3 Equidistant code pairs

Suppose V = {1, …, q}^{n}, the set of words of length n over an alphabet of size q, and define two words to be in relation R_{δ} if their Hamming distance (the number of coordinate places in which they differ) equals δ. This defines the well known Hamming association scheme H(n, q). For a graph G\overline{δ} in H(n, q) two disconnected sets in G\overline{δ} are called equidistant code pairs (at distance δ) and we write Φ_{δ} and ϕ_{δ} in stead of Φ(G\overline{δ}) and ϕ(G\overline{δ}) respectively.

Lemma 3.1

Φ_{δ}^{2} ≥ max_{0≤δ′≤δ} \binom{n − δ′}{δ − δ′}(q − 1)^{δ−δ′} (⌊\frac{q}{2}⌋ ⌈\frac{q}{2}⌉)^{δ′} .

Proof. Take for A the set of words (x_{1}, …, x_{n}) with 1 ≤ x_{i} ≤ \frac{q}{2} if i ≤ δ′ and x_{i} = 1 if i > δ′, and let B consist of the words (x_{1}, …, x_{n}) with \frac{q}{2} < x_{i} ≤ q if i ≤ δ′ and x_{i} ≠ 1 for precisely δ − δ′ values of i > δ′. Then A and B form an equidistant code pair at distance δ with sizes ⌊\frac{q}{2}⌋^{δ′} and ⌈\frac{q}{2}⌉^{δ′} \binom{n−δ′}{δ−δ′}(q −1)^{δ−δ′}, respectively. □

The above construction was given by Ahlswede [1]. He proves that equality holds for q = 4 and q = 5 and conjectures equality for all q ≥ 4. For q = 2 and q = 3 there exist better constructions of equidistant code pairs (see below).

The Hamming scheme is self-dual, which means that the dual eigenvalues coincide with the eigenvalues. They are given by (see [8]):

Q_{δ,j} = ∑_{k=0}^{n}(−1)^{k}(q − 1)^{j−k}\binom{δ}{k}\binom{n − δ}{j − k} for δ, j ∈ \{0, …, n\}.

The automorphism group of H(n, q) is transitive on each relation, so Theorem 2.5 gives the exact value of ϕ_{δ} for all n, q and δ.

Example If n = 6 and q = 6, then for j = 0, …, 6 the respective values of Q_{4,j} are 1, 6, −9, −44, 111, −90 and 25. Theorem 2.5 gives ϕ_{4} = 46656/286 ≈ 163.13. With Lemma 3.1 (take δ′ = 2) we find 45\sqrt{6} ≤ Φ_{4} ≤ 23328/143.

This example shows that our bound will not prove Ahlswede’s conjecture. But it can give interesting results in some cases.

Theorem 3.2 If q > 2 then

ϕ_{δ} ≤ \frac{q^{n}}{(q − 2)^{n−δ}2^{δ}} .

Equality holds if and only if δ = n.

Proof. The inequality follows from Theorem 2.5 and

∑_{j=0}^{n} |Q_{δ,j}| ≥ | ∑_{j=0}^{n}(−1)^{j}Q_{δ,j}| = |∑_{k=0}^{n} \binom{δ}{k} ∑_{j=0}^{n}(−1)^{j−k}(q − 1)^{j−k}\binom{n − δ}{j − k}| = 2^{δ}(q−2)^{n−δ}.

If j runs from 0 to n, Q_{n,j} alternates in sign, so we have equality if δ = n. The dual eigenvalues of any association scheme satisfy ∑_{j=0}^{n} \frac{1}{μ_{j}} Q_{δ,j}Q_{n,j} = 0 if δ ≠ n (μ_{j} = rk E_{j}). Therefore Q_{δ,j} cannot alternate in sign if δ ≠ n, so then we have strict inequality. □

Corollary 3.3 If q > 2 then

Φ_{δ} ≤ \frac{q^{n}}{(q − 2)^{n−δ}2^{δ}} .

Equality holds if and only if δ = n and q is even.

Proof. If δ = n and q is even, Lemma 3.1 (with δ′ = δ) gives Φ_{n} ≥ (\frac{q}{2})^{n}, which equals ϕ_{n}. If q is odd, (\frac{q}{2})^{2n} is not an integer, so Φ_{n} ≠ ϕ_{n}. □

We see that the lower bound of Lemma 3.1 and the upper bound of Corollary 3.3 tend to the same value (\frac{q}{2})^{δ} if q → ∞. More precisely:

Corollary 3.4

Φ_{δ} = (\frac{q}{2})^{δ} + O(q^{δ−1}) (q → ∞).

For q ≥ 4 Ahlswede and Mörs [3] showed that Φ_{δ} < Φ_{n} if δ < n. This result now follows directly from Corollary 3.3 when q is even and, by Lemma 3.1, also when q is odd and n is not too big.

For q = 3 not much is known about Φ_{δ}. Ahlswede [1] has a construction for equidistant code pairs and conjectures that it is best possible. If this is true then Φ_{δ} attains its maximal value

(\frac{3}{2})^{⌊ \frac{n}{3} ⌋} 2^{\frac{n}{2}}

if δ = ⌈\frac{2n}{3}⌉. Theorem 3.2 gives ϕ_{n} = (\frac{3}{2})^{n}, thus we have that Φ_{n} < Φ_{δ} if δ = ⌈\frac{2n}{3}⌉ (n > 2). By use of Theorem 2.5, stronger results are possible, but it turns out that the bound ϕ_{δ} is not good enough to prove that Φ_{δ} is maximal if δ = ⌈\frac{2n}{3}⌉.

For q = 2 the value Φ_{δ} is known for all δ; see [1]. It attains the maximal value 2^{⌈ \frac{n}{2} ⌉} if δ = ⌊\frac{n}{2}⌋ and if δ = ⌈\frac{n}{2}⌉. This result was first proved by Ahlswede, El Gamal and Pang [2] and has several different proofs now (see [1]). We shall see that our bound provides yet another proof. The construction is as follows. Take for A the set of words (x_{1}, …, x_{n}) with x_{2i−1} = x_{2i} for 1 ≤ i ≤ \frac{n}{2} and x_{n} = 1 if n is odd. Take for B the set of words with x_{2i−1} ≠ x_{2i} for 1 ≤ i ≤ \frac{n}{2} and x_{n} fixed if n is odd. Then A and B are equidistant code pairs at distance ⌊\frac{n}{2}⌋ or ⌈\frac{n}{2}⌉ and |A| = |B| = 2^{⌊ \frac{n}{2} ⌋}.

Theorem 3.5 If q = 2 then

ϕ_{δ} ≤ 2^{⌊ \frac{n}{2} ⌋} for δ ∈ \{1, …, n\}.

Equality holds if δ ∈ \{⌊\frac{n}{2}⌋, ⌈\frac{n}{2}⌉\}.

Proof. With i = \sqrt{−1} we have

∑_{j=0}^{n} i^{j}Q_{δ,j} = ∑_{k=0}^{n} i^{−k}\binom{δ}{k} ∑_{j=0}^{n} i^{j−k}\binom{n − δ}{j − k} = (1 − i)^{δ}(1 + i)^{n−δ} = 2^{\frac{n}{2}} ω,

wherein ω = e^{\frac{πi}{4} (n−2δ)}. Hence

∑_{j=0}^{n} |Q_{δ,j}| = ∑_{j even} |Q_{δ,j}| + ∑_{j odd} |Q_{δ,j}| ≥ 2^{\frac{n}{2}} (|Re ω| + |Im ω|) = 2^{⌈ \frac{n}{2} ⌉},

and the inequality follows by use of Theorem 2.5. The construction above shows that Φ_{δ} = ϕ_{δ} = 2^{⌊ \frac{n}{2} ⌋} if |\frac{n}{2} − δ| ≤ \frac{1}{2}. □

With a similar argument and a bit more work as in the proof of Theorem 3.2 it can be seen that if |\frac{n}{2} − δ| ≥ 1 the bound ϕ_{δ} is strictly less than 2^{⌊ \frac{n}{2} ⌋}.

4 Concluding remarks

There is some similarity between our function ϕ(G) and Lovász’s function θ(G) (see [12]). The latter function gives an upper bound for a coclique (independent set of vertices) in G, which is, in a sense, a vertex set disconnected to itself. Lovasz’s θ(G) is known to be computable in polynomial time (see [10]), but we do not know the complexity of the computation of ϕ(G) and Φ(G).

If we apply Theorem 2.5 to the Johnson association scheme J(m, n), we obtain bounds for equidistant code pairs in (binary) constant weight codes. It seems certainly worthwhile to work this out and we intend to do so. The problem is that the formulas for the dual eigenvalues are rather complicated. For the special case that δ = n we believed that ∑_{j} |Q_{δ,j}| = \binom{\frac{m}{2}}{n}, but had no proof, until Volker Strehl (private communication) provided us with a computer-generated proof by use of Zeilberger’s algorithm.

Acknowledgement. The research for this paper was done when the author was a guest of the Sonderforschungsbereich “Diskrete Structuren in der Mathematik” at the University of Bielefeld. Special thanks goes to Professor Rudi Ahlswede for the invitation, and several fruitful discussions concerning the subject.

References

[1] R. Ahlswede, On code pairs with specified Hamming distances, Colloquia Mathematica Societas János Bolyai 52, Combinatorics, Eger (Hungary), 1987, pp. 9-47.

[2] R. Ahlswede, A. El Gamal and K.F. Pang, A two-family extremal problem in Hamming space, Discrete Math. 49 (1984), 1-5.

[3] R. Ahlswede and M. Mörs, Inequalities for code pairs, Europ. J. Combinatorics 9 (1988), 175-181.

[4] A.E. Brouwer, A.M. Cohen and A. Neumaier, Distance-regular graphs, Springer-Verlag, Berlin, 1989.

[5] A.E. Brouwer and W.H. Haemers, Association schemes, chapter 15 in: Handbook of Combinatorics (R. Graham, M. Grötschel and L. Lovász eds.), Elsevier Science, Amsterdam, 1995, pp. 747-771.

[6] R.A. Brualdi and H.J. Ryser, Combinatorial matrix theory, Cambridge University Press, Cambridge, 1991.

[7] E.R. van Dam and W.H. Haemers, Eigenvalues and the diameter of graphs, Linear Multilinear Algebra 39 (1995), 33-44.

[8] Ph. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Research Rep. Suppl. 10, 1973.

[9] C.D. Godsil, Algebraic combinatorics, Chapman and Hall, New York - London, 1993.

[10] M. Grötschel, L. Lovász and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), 169-197.

[11] W.H. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl. 226-228 (1995), 593-616.

[12] L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), 1-7.