2
$\begingroup$

Let $H_{n,r}$ the graph whose vertices are the vectors of $\mathbb{F}_2^n$ and there exists an edge between $x$ and $y$ if and only if the Hamming distance $d(x,y)$ is equal exactly to $r$.

Q1: Could I say that its diameter verifies $d(H_{n,r}) \leq n$?

These graph are $\binom{n}{r}$-regular, then I could say that the length of a path cannot exceed $\binom{n}{r}$ in the hypothesis when, from a vertex $v$, I can pass through distinct vectors of $\mathbb{F}_2^n$ adding to $v$, at each step of my path, any of the vectors of weight $r$ that I did not add previously, thus exhausting the $\binom{n}{r}$ vectors of weight $r$. From this reasoning I can say that

Q2: $d(H_{n,r}) \leq \binom{n}{r}$?

The case $r=1$, the hypercube, covers both inequalities: from this observation originates my conjectures.

NOTE: for $r$ even and $r=0,n$, $H_{n,r}$ is not connected, then we speak about diameter only for $r$ odd and $1\leq r <n$.

$\endgroup$
1
$\begingroup$

First, if $X$ is a graph with diameter $d$, then $d+1$ is a lower bound on the number of distinct eigenvalues. Second, any eigenvector for the $n$-cube is an eigenvector for $H_{n,r}$. Since the $n$-cube has exactly $n+1$ distinct eigenvalues, it follows that any component of $H_{n,r}$ has diameter at most $n$. [The diameter bound is standard, google "adjacency algebra". The second statement follows from the fact that the adjacency matrix of $H_{n,r}$ is a polynomial of degree $r$ in the adjacency matrix of the $n$-cube.]

$\endgroup$
  • $\begingroup$ This is a brilliant way to deal with my problem. Unfortunately I don't know anything about adjacency algebra. Do you know where I can see an explanation/proof that the adjacency matrix of $H_{n,r}$ is a polynomial of degree $r$ in the adjacency matrix of the $n-$cube?? It doesn't seem straightforward to me! Many thanks $\endgroup$ – ilmarchese Aug 22 '16 at 13:49
  • $\begingroup$ From your observation, we get a direct proof of $Q1$ observing that the eigenvalues $\lambda_a^{n,r}$ of $H_{n,r}$ are the Krawtchouk Polynomials in $(n,r,a)$ and, fixing $n,r$, depends only on $0\leq a \leq n$. Then we can have at maximum $n+1$ values for $a$ and then at maximum $n+1$ distinct eigenvalues for $H_{n,r}$, thus $d \leq n$. $\endgroup$ – ilmarchese Aug 22 '16 at 14:03
  • 1
    $\begingroup$ @ilmarchese: if $A_r$ is the adjacency matrix of $H_{n,r}$, then $A_1A_r$ is a linear combination of $A_{r-1}$ and $A_{r+1}$; this gives recurrence for $A_{r+1}$ in terms of $A_r$ and $A_{r-1}$. As for the adjacency algebra, see the wikipedia page. $\endgroup$ – Chris Godsil Aug 22 '16 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.