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?
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
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}$.
answered Sep 11, 2013 at 12:42
$\begingroup$
$\endgroup$
6
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$.
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)
answered Sep 11, 2013 at 8:33
-
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$ 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$ 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$ Commented Sep 11, 2013 at 9:59
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
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.
