\documentstyle[12pt]{article}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lm}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\def\j{\underline{1}}
\def\0{\underline{0}}
\def\s{\Phi}
\def\b{\phi}
\def\d{\delta}
\def\Gd{G_{\overline\d}}
\def\G4{G_{\overline 4}}
\def\8{\infty}
\def\2{\frac{1}{2}}
\def\g2{{\mbox{\large{2}}}}
\def\M{\overline{M}}
\def\P{{\cal P}}

\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 4 (1997),
\#R7 \hfill}
\thispagestyle{empty}

\begin{document}
\begin{center}
{\LARGE Disconnected vertex sets\\
\vspace{2mm}
and equidistant code pairs}\\
\vspace{5mm}
{\large Willem H. Haemers}\\
\vspace{3mm}
{\small Department of Econometrics, Tilburg University,\\
Tilburg, The Netherlands; e-mail: haemers@kub.nl}\\
\vspace{3mm}
Submitted: October 28, 1996; Accepted: January 29, 1997.\\
\end{center}

\begin{abstract}
Two disjoint subsets $A$ and $B$ of a vertex set $V$ of a finite
graph $G$ are called {\it 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 $\d\in\{1,\ldots,n\}$, then a pair
of disconnected sets becomes an {\it 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 $\d$,
and for $q\rightarrow\8$ for any fixed $n$ and $\d$.
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$ ans $B$ in the binary Hamming Scheme.
\end{abstract}

\section{Introduction}
Throughout $G$ is a finite graph with vertex set $V$.
Two disjoint subsets $A$ and $B$ of $V$ are {\it disconnected} if
there is no edge between $A$ and $B$.
We define $\s(G)$ to be the maximum of $\sqrt{|A|\cdot|B|}$
for disconnected sets $A$ and $B$ in $G$.
Suppose $V$ is the set of words of length $n$ over an alphabet
$\{1,\ldots,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 $\d\in\{1,\ldots,n\}$.
Then a pair of disconnected sets becomes an {\it equidistant code 
pair}.

The quantity $\s(G)$ has an application in information theory and 
leads to a lower bound for the two-way communication complexity of 
functions defined on $V \times 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~\cite{ahl}, who gives the exact 
value of $\s(G)$ for $q=2$, 4 and 5, for every $\d$ and $n$.

In this paper we will give a bound for $\s(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 
$\d$, and for $q\rightarrow\8$ for any fixed $n$ and $\d$.

\section{Disconnected vertex sets}
Let $V=\{1,\ldots,v\}$.
We define ${\cal M}(G)$ to be the collection of symmetric $v\times 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 $\lambda_1(M),\ldots,\lambda_v(M)$ denote the eigenvalues of a 
matrix $M\in{\cal M}(G)$, such that $\lambda_1(M)$ has eigenvector 
$\j$ (the all-one vector), so $\lambda_1(M)=1$.
Put \[ \lambda(M)=\max_{i \neq 1} |\lambda_i(M)| . \]
%{\mbox{ and }} \lambda=\min_{M\in{\cal M}(G)}\lambda(M)

\begin{lm}\label{ab}
If $A$ and $B$ are disconnected vertex sets of $G$ and $M\in{\cal 
M}(G)$, then
$$ \frac{|A|\cdot|B|}{(v-|A|)(v-|B|)} \leq \lambda^2(M) .$$
\end{lm}
{\bf Proof.}
See \cite{dh} Theorem~2.1, or \cite{hae} Lemma~6.1. \hfill$\Box$\\

\begin{thm}\label{phi}
For any $M \in {\cal M}(G)$
$$ \s(G) \leq v\frac{\lambda(M)}{1+\lambda(M)} \ . $$
\end{thm}
{\bf Proof.}
Put $\s=\s(G)$ and take $A$ and $B$ such that $\s^2=|A|\cdot|B|$.
Then by Lemma~\ref{ab}
\[ \frac{\s^2}{\lambda^2(M)} \leq (v^2-v(|A|+|B|)+\s^2)
        \leq (v^2-2v\sqrt{|A|\cdot|B|}+\s^2)
        = {(v-\s)}^2 . \]
Clearly $v\geq\s$, so $\s\leq(v-\s)\lambda(M)$, which yields the 
required
bound. \hfill$\Box$\\

\noindent
In order to investigate when the bound of Theorem~\ref{phi} is best
possible, we define
$$ \b(G)=\min_{M\in{\cal M}(G)} v\frac{\lambda(M)}{1+\lambda(M)} $$
and we let ${\cal M'}(G)$ denote the set of matrices from ${\cal 
M}(G)$ for which the above minimum is attained.
Thus Theorem~\ref{phi} becomes $\s(G) \leq \b(G)$.
To determine $\b(G)$ we need to find a matrix in ${\cal M'}(G)$.
For that purpose the automorphisms of $G$ can be helpful.\\

\begin{lm}\label{aut}
Let ${\cal A}$ be an automorphism group of $G$.
Then ${\cal M'}(G)$ contains a matrix which is constant over each
orbit of the action of ${\cal A}$ on $V \times V$.\\
\end{lm}
{\bf Proof.}
Let $P_g$ denote the permutation matrix corresponding to
$g\in{\cal A}$ and take $M'\in{\cal M'}(G)$.
Then clearly $P_gM'P_g^\top\in{\cal M'}(G)$
and, by Rayleigh's principle, $|u^\top P_gM'P_g^\top u| \leq 
\lambda(M')$ for every unit vector $u$ orthogonal to $\j$ .
Define
\[ \M = \frac{1}{|{\cal A}|} \sum_{g \in {\cal A}} P_gM'P_g^\top , \]
then clearly $\M\in{\cal M}(G)$ and $\M$ is constant over 
${\cal A}$-orbits on $V\times V$.
Let $u$ ($u\perp\j$) be a unit eigenvector for the eigenvalue
$\pm\lambda(\M)$.
Then $\lambda(\M) = |u^\top\M u| \leq \lambda(M')$, so
$\lambda(\M)=\lambda(M')$ and hence $\M\in{\cal M'}(G)$.
\hfill$\Box$\\

\noindent
In particular we may take the diagonal constant if $G$ has a 
transitive automorphism group.
Theorem~\ref{phi} 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~\cite{br}.)

\begin{thm}\label{lap}
Suppose $F$ is the Laplacian matrix of $G$ and let
$0=\mu_1\leq\mu_2\leq\ldots\leq\mu_v$ be the eigenvalues of $F$, then
\[ \b(G) \leq \frac{v}{2}\left(1-\frac{\mu_2}{\mu_v}\right) \]
with equality if $G$ has an automorphism group that acts transitively 
on the edges.\\
\end{thm}
{\bf Proof.} Define
\[ M = \frac{-2}{\mu_2+\mu_v}F+I. \]
Then $M\in{\cal M}(G)$ and $\lambda(M)=(\mu_v-\mu_2)/(\mu_v+\mu_2)$,
which yields the inequality.

Suppose $G$ has an automorphism group which acts transitively on the 
edges.
Then, by Lemma~\ref{aut} there exists a matrix $M'\in{\cal M'}(G)$ 
such that $M'=xF+D$ for some constant $x$ and diagonal matrix $D$.
Now $M'\j=\j$ gives $D=I$ and so
\[ \lambda(M') = \max\{|x\mu_2+1|,|x\mu_v+1|\} . \]
It follows that $\lambda(M')$ is minimal if $x\mu_2+1 = -x\mu_v-1$,
that is, if $x=-2/(\mu_2+\mu_v)$.
Thus $M\in{\cal M'}(G)$. \hfill$\Box$\\

\noindent
{\bf Example.}
Suppose $G$ is the triangular graph $T(2m)$ (that is, the line graph 
of $K_{2m}$).
Then $v=m(2m-1)$, $\mu_2=2m$ and $\mu_v=4m-2$.
Theorem~\ref{lap} gives $\b(G)={m\choose2}$.
We easily have that $\s(G)\geq{m\choose2}$, so $\s(G)={m\choose2}$.\\

\noindent
Next we consider association schemes.
For theory and notation see \cite{bcn}, \cite{bh} or \cite{god}.
Let $S$ be an $n$-class association scheme defined on the set
$V$ with relations $R_0,\ldots,R_n$.
For $\d\in\{1,\ldots,n\}$ we denote by $G_\d$ the graph $(V,R_\d)$ and
by $\Gd$ the complement of $G_\d$.\\

\begin{thm}\label{ass}
If $Q$ is the matrix of dual eigenvalues of $S$, then
\[ \b(\Gd) \leq \frac{v}{\sum_{j=0}^n |Q_{\d,j}|} \ . \]
Equality holds if the automorphism group of $S$ acts transitively on 
each relation.\\
\end{thm}
{\bf Proof.}
Let $A_0,\ldots,A_n$ (with $A_0=I$) be the adjacency matices of $S$
and let $E_0,\ldots,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 = \sum_{i=0}^n Q_{i,j}A_i ,\mbox{ for } j=0,\ldots,n. \]
So $v(E_j)_{k,\l} = Q_{\d,j}$ whenever $\{k,\l\}\in R_\d$.
Define $\P_\d = \{j|1\leq j\leq n,\ Q_{\d,j}>0\}$,
$ m=\sum_{j\in \P_\d}Q_{\d,j}+\2$ and
\[ M = {\textstyle\frac{1}{m}} ({\textstyle\2}I -
\sum_{j\in \P_\d}(E_j - Q_{\d,j}E_0)) . \]
Then, since $E_j\j=\0$ for $j\neq 0$ one readily verifies that
$M\in{\cal M}(\Gd)$.
Moreover $\sum_{j\in \P_\d}E_j$ has only $0$ and $1$ as eigenvalues.
This implies that $\lambda_i(M)=\pm\frac{1}{2m}$ for $i\neq 1$, so
$\lambda(M)=\frac{1}{2m}$, and thus we find 
$\b(\Gd)\leq\frac{v}{2m+1}$.
By use of $\sum_{j=0}^n Q_{\d,j} = 0$ and $Q_{\d,0}=1$, we obtain
\[ m+{\textstyle\2} = 1+\sum_{j\in \P_\d} Q_{\d,j} =
{\textstyle\2}\sum_{j=0}^n |Q_{\d,j}|, \]
and the required inequality follows.

Next assume that $S$ admits an automorphism group which is transitive 
on each relation.
Then by Lemma~\ref{aut} there exists a matrix $M'\in{\cal M'}(\Gd)$
which is a linear combination of $A_0,\ldots,A_n$, that is, $M'$ is
in the Bose-Messner algebra of $S$.
Let $\lambda_{j'}(M')$ denote the eigenvalue of $M'$ whose eigenspace 
is given by $E_{j}$.
We claim that we may assume that $\lambda_{j'}(M')=\lambda(M')$ if
$Q_{\d,j} \leq 0$.
Indeed, suppose this is not the case,
then define $d=\lambda(M')-\lambda_{j'}(M')$, $m=1-dQ_{\d,j}$ and
$M'' = \frac{1}{m}(M'+d(E_{j}-Q_{\d,j}E_0))$.
It follows that $M''\in{\cal M}(\Gd)$, $m \geq 1$ and
$\lambda_{j'}(M'') = \lambda(M'') = \frac{1}{m}\lambda(M') \leq 
\lambda(M')$.
So we can redefine $M'=M''$, which proves the claim.
Similarly, we may assume that
$\lambda_{j'}(M')=-\lambda(M')$ if $Q_{\d,j} \geq 0$ and $j\neq 0$.
It now follows that
\[ E = \frac{1}{2\lambda(M')}(\lambda(M')I-M'+(\lambda(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=\sum_{j\in \P_\d}E_j$.
In addition, since $(M')_{k,l} = 0$ for $\{k,l\}\in R_\d$, we have
$\sum_{j\in\P_\d} Q_{\d,j} = \frac{1}{2\lambda(M')}-\2$.
This implies that $M'=M$, so $M\in{\cal M'}(\Gd)$.
\hfill$\Box$\\

\noindent
A graph $\Gd$ 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~\ref{lap} and Theorem~\ref{ass} coincide.

\section{Equidistant code pairs}
Suppose $V=\{1,\ldots,q\}^n$, the set of words of length $n$ over an
alphabet of size $q$, and define two words to be in relation $R_{\d}$
if their Hamming distance (the number of coordinate places in which 
they differ) equals $\d$.
This defines the well known Hamming association scheme $H(n,q)$.
For a graph $\Gd$ in $H(n,q)$ two disconnected sets in $\Gd$ are
called equidistant code pairs (at distance $\d$) and we write
$\s_\d$ and $\b_\d$ in stead of $\s(\Gd)$ and $\b(\Gd)$ 
respectively.\\

\begin{lm}\label{ahl}
\[ \s_\d^2\ \geq\ 
\max_{0\leq\d'\leq\d} {n-{\d}'\choose\d-\d'}(q-1)^{\d-\d'}
\left( \left\lfloor \frac{q}{2} \right\rfloor
\left\lceil \frac{q}{2} \right\rceil \right)^{\d'}.\]
\end{lm}
{\bf Proof.}
Take for $A$ the set of words $(x_1,\ldots,x_n)$ with
$1\leq x_i \leq \frac{q}{2}$ if $i\leq\d'$ and $x_i=1$ if
$i>\d'$, and let $B$ consist of the words $(x_1,\ldots,x_n)$ with
$\frac{q}{2} < x_i\leq q$ if $i\leq\d'$ and $x_i\neq 1$
for precisely $\d-\d'$ values of $i>\d'$.
Then $A$ and $B$ form an equidistant code pair at distance $\d$ with
sizes $\lfloor\frac{q}{2}\rfloor^{\d'}$ and
$\lceil\frac{q}{2}\rceil^{\d'}{n-\d'\choose\d-\d'}(q-1)^{\d-\d'}$,
respectively. \hfill$\Box$\\

\noindent
The above construction was given by Ahlswede~\cite{ahl}.
He proves that equality holds for $q=4$ and $q=5$ and conjectures
equality for all $q\geq 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~\cite{del}):
\[ Q_{\d,j} = \sum_{k=0}^n (-1)^k(q-1)^{j-k}{\d\choose k}
{n-\d\choose j-k}\ \mbox{ for }\d,j\in\{0,\ldots,n\}. \]
The automorphism group of $H(n,q)$ is transitive on each relation, so
Theorem~\ref{ass} gives the exact value of $\b_\d$ for all $n$, $q$
and $\d$.\\

\noindent {\bf Example} If $n=6$ and $q=6$, then for $j=0,\ldots,6$
the respective values of $Q_{4,j}$ are $1$, $6$, $-9$, $-44$, $111$, 
$-90$ and $25$.
Theorem~\ref{ass} gives $\b_4 = 46656/286 \approx 163.13$.
With Lemma~\ref{ahl} (take $\d'=2$) we find 
$45\sqrt{6} \leq \s_4 \leq 23328/143$.\\

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

\begin{thm}\label{q} If $q>2$ then
\[ \b_\d \leq \frac{q^n}{(q-2)^{n-\d} 2^\d}. \]
Equality holds if and only if $\d=n$.\\
\end{thm}
{\bf Proof.}
The inequality follows from Theorem~\ref{ass} and
\[ \sum_{j=0}^n |Q_{\d,j}| \geq |\sum_{j=0}^n (-1)^j Q_{\d,j}|
= \left|\sum_{k=0}^n{\d\choose k}\sum_{j=0}^n (-1)^{j-k}(q-1)^{j-k}
{n-\d\choose j-k}\right| = 2^\d (q-2)^{n-\d} .\]
If $j$ runs from $0$ to $n$, $Q_{n,j}$ alternates in sign, so we have
equality if $\d=n$.
The dual eigenvalues of any association scheme satisfy
$\sum_{j=0}^n \frac{1}{\mu_j} Q_{\d,j} Q_{n,j} = 0$ if $\d\neq n$
($\mu_j=$ rk~$E_j$).
Therefore $Q_{\d,j}$ cannot alternate in sign if $\d\neq n$, so then 
we have strict inequality. \hfill$\Box$

\begin{cor}\label{q1}
If $q>2$ then
\[ \s_\d \leq \frac{q^n}{(q-2)^{n-\d} 2^\d}. \]
Equality holds if and only if $\d=n$ and $q$ is even.\\
\end{cor}
{\bf Proof.}
If $\d=n$ and $q$ is even, Lemma~\ref{ahl} (with $\d'=\d$) gives
$\s_n\geq(\frac{q}{2})^n$, which equals $\b_n$.
If $q$ is odd, $(\frac{q}{2})^{2n}$ is not an integer, so
$\s_n\neq\b_n$. \hfill$\Box$\\

\noindent
We see that the lower bound of Lemma~\ref{ahl} and the upper
bound of Corollary~\ref{q1} tend to the same value $(\frac{q}{2})^\d$
if $q\rightarrow\8$.
More precisely:\\

\begin{cor}
\[ \s_\d = \left(\frac{q}{2}\right)^\d + O(q^{\d-1})\ \ 
(q\rightarrow\8).\]
\end{cor}

\noindent
For $q\geq 4$ Ahlswede and M\"ors~\cite{am} showed that $\s_\d < \s_n$
if $\d < n$.
%=(\lfloor\frac{q}{2}\rfloor\lceil\frac{q}{2}\rceil)^{\frac{n}{2}}$
This result now follows directly from Corollary~\ref{q1} when $q$ is 
even and, by Lemma~\ref{ahl}, also when $q$ is odd and $n$ is not too 
big.

For $q=3$ not much is known about $\s_\d$.
Ahlswede~\cite{ahl} has a construction for equidistant code pairs and
conjectures that it is best possible.
If this is true then $\s_\d$ attains its maximal value
\[\left({\frac{3}{2}}\right)^{\lfloor\frac{n}{3}\rfloor}
\g2^{\frac{n}{2}}\]
if $\d = \lceil\frac{2n}{3}\rceil$.
Theorem~\ref{q} gives $\b_n = (\frac{3}{2})^n$,
thus we have that $\s_n<\s_\d$ if $\d=\lceil\frac{2n}{3}\rceil$
($n>2$).
By use of Theorem~\ref{ass}, stronger results are possible, but
it turns out that the bound $\b_\d$ is not good enough to prove
that $\s_\d$ is maximal if $\d=\lceil\frac{2n}{3}\rceil$.

For $q=2$ the value $\s_\d$ is known for all $\d$; see~\cite{ahl}.
It attains the maximal value $2^{\lceil\frac{n}{2}\rceil}$
if $\d=\lfloor\frac{n}{2}\rfloor$ and if
$\d=\lceil\frac{n}{2}\rceil$.
This result was first proved by Ahlswede, El Gamal and Pang~\cite{aep}
and has several different proofs now (see \cite{ahl}).
We shall see that our bound provides yet another proof.
The construction is as follows.
Take for $A$ the set of words $(x_1,\ldots,x_n)$ with
$x_{2i-1}=x_{2i}$ for $1\leq i\leq \frac{n}{2}$ and $x_n=1$
if $n$ is odd.
Take for $B$ the set of words with $x_{2i-1}\neq x_{2i}$
for $1\leq i\leq \frac{n}{2}$ and $x_n$ fixed if $n$ is odd.
Then $A$ and $B$ are equidistant code pairs at distance
${\lfloor\frac{n}{2}\rfloor}$ or ${\lceil\frac{n}{2}\rceil}$
and $|A|=|B|=2^{\lfloor\frac{n}{2}\rfloor}$.\\

\begin{thm}
If $q=2$ then
\[ \b_\d \leq {\g2}^{\lfloor\frac{n}{2}\rfloor} \ \mbox{ for }
\d \in \{1,\ldots,n\} . \]
Equality holds if
$\d\in\{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil\}$.\\
\end{thm}
{\bf Proof.}
With $i=\sqrt{-1}$ we have
\[ \sum_{j=0}^n i^j Q_{\d,j} =
\sum_{k=0}^n i^{-k}{\d \choose k} \sum_{j=0}^n
i^{j-k}{n-\d \choose j-k} = (1-i)^\d(1+i)^{n-\d}
= {\g2}^{\frac{n}{2}} \omega , \]
wherein $\omega = e^{\frac{\pi i}{4}(n-2\d)}$.
Hence
\[ \sum_{j=0}^n |Q_{\d,j}| = \sum_{j\mbox{\scriptsize\ even}} 
|Q_{\d,j}| + \sum_{j\mbox{\scriptsize\ odd}} |Q_{\d,j}|
\geq {\g2}^{\frac{n}{2}} (|\mbox{Re~}\omega| + |\mbox{Im~}\omega|) =
{\g2}^{\lceil\frac{n}{2}\rceil} ,\]
and the inequality follows by use of Theorem~\ref{ass}.
The construction above shows that
$\s_\d=\b_\d=2^{\lfloor\frac{n}{2}\rfloor}$ if
$|\frac{n}{2}-\d|\leq\2$.
\hfill$\Box$\\

\noindent
With a similar argument and a bit more work as in the proof of
Theorem~\ref{q} it can be seen that if $|\frac{n}{2}-\d|\geq 1$ the 
bound $\b_\d$ is strictly less than $2^{\lfloor\frac{n}{2}\rfloor}$.

\section{Concluding remarks}
There is some similarity between our function $\b(G)$ and Lov\'asz's 
function $\theta(G)$ (see \cite{lov}).
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 $\theta(G)$ is known to be computable in polynomial time
(see~\cite{gls}), but we do not know the complexity of the computation
of $\b(G)$ and $\s(G)$.

If we apply Theorem~\ref{ass} 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 $\d=n$ we believed that
$\sum_{j} |Q_{\d,j}|={\frac{m}{2} \choose n}$, but had no proof,
until Volker Strehl (private communication) provided us with a
computer-generated proof by use of Zeilberger's algorithm.\\

\noindent
{\bf 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.

\newpage

\begin{thebibliography}{99}
\bibitem{ahl} R. Ahlswede,
{\it On code pairs with specified Hamming distances,}
Colloquia Mathematica Societas J\'anos Bolyai {\bf 52},
Combinatorics, Eger (Hungary), 1987, pp. 9-47.
\bibitem{aep} R. Ahlswede, A. El Gamal and K.F. Pang,
{\it A two-family extremal problem in Hamming space,}
Discrete Math. {\bf 49} (1984), 1-5.
\bibitem{am} R. Ahlswede and M. M\"ors,
{\it Inequalities for code pairs,} Europ. J. Combinatorics {\bf 9}
(1988), 175-181.
\bibitem{bcn} A.E. Brouwer, A.M. Cohen and A. Neumaier,
{\it Distance-regular graphs,} Springer-Verlag, Berlin, 1989.
\bibitem{bh} A.E. Brouwer and W.H. Haemers,
{\it Association schemes,} chapter 15 in: Handbook of Combinatorics
(R. Graham, M. Gr\"otschel and L. Lov\'asz eds.), Elsevier Science,
Amsterdam, 1995, pp. 747-771.
\bibitem{br} R.A. Brualdi and H.J. Ryser,
{\it Combinatorial matrix theory,} Cambridge University Press,
Cambridge, 1991.
\bibitem{dh} E.R. van Dam and W.H. Haemers,
{\it Eigenvalues and the diameter of graphs,}
Linear Multilinear Algebra {\bf 39} (1995), 33-44.
\bibitem{del} Ph. Delsarte,
{\it An algebraic approach to the association schemes of coding 
theory,} Philips Research Rep. Suppl. {\bf 10}, 1973.
\bibitem{god} C.D. Godsil, {\it Algebraic combinatorics,} Chapman and 
Hall, New York - London, 1993.
\bibitem{gls} M. Gr\"otschel, L. Lov\'asz and A. Schrijver,
{\it The ellipsoid method and its consequences in combinatorial 
optimization,} Combinatorica {\bf 1} (1981), 169-197.
\bibitem{hae} W.H. Haemers,
{\it Interlacing eigenvalues and graphs,}
Linear Algebra Appl. {\bf 226-228} (1995), 593-616.
\bibitem{lov} L. Lov\'asz, {\it On the Shannon capacity of a graph,}
IEEE Trans. Inform. Theory {\bf 25} (1979), 1-7.
\end{thebibliography}
\end{document}