What is the independence number of hamming graph? 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?
 A: 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}$.
A: 
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.



*

*S. El Rouayheb and C.N. Georghiades, Graph Theoretic Methods in Coding Theory (2012)

*R. Ahlswede and L.H. Khachatrian The Diametric Theorem in Hamming Spaces -- Optimal Anticodes (1998)


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


*

*P. Frankl and N. Tokushige, The Erdos-Ko–Rado Theorem for Integer Sequences (1999)

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

A: 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.
