Hamming graph and independent sets

Question

I'm defining the Hamming graph $H(d,q)$ in the usual way, so we have a set $S$ of $q$ elements, the hamming graph $H(d,q)$ has vertex set $S^{d}$ (the set of all ordered $d$-tuples of elements of $S$) and the edge set formed of all pairs of vertices which differ in exactly one element.

I'm interested in the following questions of which I've found it difficult to find answers.

1. Is the exact independence number of $H(d,q)$ known?
2. For any set of size $k$ less than or equal to the independence number, how many independent sets of size $k$ does the hamming graph contain?

Answer 1

If I understand correctly, the answer to (1) is discussed in http://en.wikipedia.org/wiki/Singleton_bound: There is a straightforward bound to the independence number of $q^{d-1}$ and it is attained by the set of codewords of "MDS codes". (The rest of the analysis is whether an MDS code exists for any particular case of (1).)

I would expect the analysis of (2) to be very difficult.

Answer 2

(1) As others have pointed out, the independence number is $q^{d-1}$: Two words in an independent set have to differ in the first $d-1$ coordinates. On the other hand, when $S=\mathbb{Z}_q$, words of the form $$(c_1,c_2,\dots,c_{d-1}, c_1+c_2+\cdots+c_{d-1})$$ form an independent set.

(2) This is a difficult problem even for $k=q^{d-1}$: An independent set of size $q^{d-1}$ can be described as a function $f:S^{d-1}\to S$ so that the set contains words $$(c_1,c_2,\dots,c_{d-1}, f(c_1,c_2,\dots,c_{d-1})),$$ and $f$ has the property that if $d-2$ coordinates are fixed, every symbol occurs exactly once. This is the definition of $f$ being a $(d-1)$-dimensional Latin hypercube of order $q$, or a $(d-1)$-ary quasigroup of order $q$.

For small values, see

• B. D. McKay and I. M. Wanless, A census of small Latin hypercubes, SIAM J. Discrete Math., 22 (2008), 719–736.

Another paper considering the exact numbers in $q=4$ and asymptotic bounds in the general case:

• V. N. Potapov and D. S. Krotov, On the number of $n$-ary quasigroups of finite order, Discrete Math. Appl., 21 (2011), 575–585.

This paper also mentions:

The asymptotics of the number and even of the logarithm of the number (and even of the logarithm of the logarithm of the number) of $n$-ary quasigroups of orders more than $4$ is unknown.