4
$\begingroup$

Hamming graph H(d,q) is Cartesian product of d complete graphs Kq. We know the independence number of direct product of d complete graphs Kq. What is the independence number of hamming graph?

$\endgroup$

4 Answers 4

7
$\begingroup$

I take the Hamming graph $H(d,q)$ to be the Cartesian product of $d$ copies of the complete graph $K_q$. Its independence number is $q^{d-1}$.

Proof: The Hamming graph lies in the Hamming scheme, so the clique-coclique bound holds: If $C$ is a clique and $S$ a coclique, then $|C||S|\ne n$, where $n$ is the number of vertices of the scheme - here $q^d$. Clearly we have cliques of size $q$, so $|S|\le q^{n-1}$. To get a coclique of the right size, view the vertices of $K_q$ as integers mod $q$ and let $S$ be the set of $d$-tuples whose coordinates sum to zero. Then no two $d$-tuples in $S$ differ in exactly one position, and so $S$ is a coclique.

Of course the clique-coclique bound is overkill here. The $d$-tuples with first $d-1$ coordinates zero form a subgroup of order $q$ in $Z_q^d$. Hence the cosets of this subgroup form a partition of the vertices of the Hamming graph into cliques of size $q$, and therefore $|S| \le q^{d-1}$.

$\endgroup$
2
$\begingroup$

The Hamming graph $H(n,d)$ has $2^n$ vertices labeled by the binary vectors of length $n$, two vertices being joined by an edge if and only if the Hamming distance between the corresponding vectors is at least $d$. More generally $H_q(n,d)$ refers to $q^n$ vertices labeled by $q$-ary vectors of length $n$.

  • N.J.A. Sloane, Unsolved Problems in Graph Theory Arising from the Study of Codes (1989)

The independence number $\alpha(H_q(n,d))$ of the Hamming graph $H_q(n,d)$ is determined by the maximum number $N_q(n,s)$ of $q$-ary sequences of length $n$ that intersect pairwise, i.e., have the same entries, in at least $s=n-d+1$ positions.

You want the binary case $q=2$. Closed-form expressions for the number $N_q(n,s)$ exist, see cited references and Theorem 2 of

$\endgroup$
6
  • 1
    $\begingroup$ What is $H_q(n,d)$ ? Classically, $H(n,d)$ is the graph on $n$-tuples of words in the alphabet of size $d$, with adjacency being having Hamming distance 1. And why $q=2$? Do you mean $q=1$? $\endgroup$ Commented Sep 11, 2013 at 8:45
  • $\begingroup$ Thank u carlo, but there is no any exact answer for this, am i right? $\endgroup$
    – Saravanan
    Commented Sep 11, 2013 at 8:45
  • $\begingroup$ Hq(n; d), has as vertices all the q-ary sequences of length n, and two vertices are adjacent if their Hamming distance is larger or equal to d. So it will not represent classical hamming graph as q=2. $\endgroup$
    – Saravanan
    Commented Sep 11, 2013 at 8:51
  • $\begingroup$ I added the definition of Hamming graph from coding theory, which my answer addressed. I guess there's more than one "Hamming graph"? $\endgroup$ Commented Sep 11, 2013 at 9:51
  • $\begingroup$ Ofcourse, In hamming graph, what I asked for, two vertices are adjacent if their hamming distance is 1. But in Hq(n,d) vertices are adjacent if their hamming distance is larger or equal to d. $\endgroup$
    – Saravanan
    Commented Sep 11, 2013 at 9:59
1
$\begingroup$

Experiments suggest it might be $q^{d-1}$.

Here is data from sage:

d= 2 q= 2 alpha= 2 factor= 2  alpha - q^(d-1) 0
d= 2 q= 3 alpha= 3 factor= 3  alpha - q^(d-1) 0
d= 2 q= 4 alpha= 4 factor= 2^2  alpha - q^(d-1) 0
d= 2 q= 5 alpha= 5 factor= 5  alpha - q^(d-1) 0
d= 2 q= 6 alpha= 6 factor= 2 * 3  alpha - q^(d-1) 0
d= 3 q= 2 alpha= 4 factor= 2^2  alpha - q^(d-1) 0
d= 3 q= 3 alpha= 9 factor= 3^2  alpha - q^(d-1) 0
d= 3 q= 4 alpha= 16 factor= 2^4  alpha - q^(d-1) 0
d= 3 q= 5 alpha= 25 factor= 5^2  alpha - q^(d-1) 0
d= 3 q= 6 alpha= 36 factor= 2^2 * 3^2  alpha - q^(d-1) 0
d= 4 q= 2 alpha= 8 factor= 2^3  alpha - q^(d-1) 0
d= 4 q= 3 alpha= 27 factor= 3^3  alpha - q^(d-1) 0
d= 4 q= 4 alpha= 64 factor= 2^6  alpha - q^(d-1) 0
d= 4 q= 5 alpha= 125 factor= 5^3  alpha - q^(d-1) 0
$\endgroup$
1
$\begingroup$

I did a google, and came up with this paper:

Graph Theoretic Methods in Coding Theory by Salim El Rouayheb and Costas N. Georghiades

Let me quote from them.

The independence number $\alpha(H_q(n;d))$ of the Hamming graph $H_q(n,d)$ is actually the maximum number of sequences of length $n$ such that the Hamming distance between any two of them is at most $d-1$. A set of sequences satisfying this property is called an anticode with maximum distance $d-1$. Define $N_q(n,s)$ to be the maximum number of $q$ -ary sequences of length $n$ that intersect pairwise, i.e., have the same entries, in at least $s$ positions. It follows that $$\alpha(H_q(n;d)) = N_q(n,t); \textrm{ with } t=n-d+1.$$

They go on to assert that a closed form for $N_q(n,t)$ can be found as the Diametric Theorem of this paper...

R. Ahlswede and L. H. Khachatrian, The Diametric Theorem in Hamming Spaces - Optimal anticodes, Adv. in Appl. Math , vol. 20, pp. 429-449, 1998.

... or as Theorem 2 of this paper

P. Frankl and N. Tokushige, The Erdos-Ko-Rado Theorem for Integer Se-quences," Combinatorica , vol. 19, pp. 55-63, 1999.

I can't access this second paper but I've looked at the first. Stating the closed form is a pain, so I won't do it here, but you should have a look.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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