MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Definition 1. The $n$-hypercube graph has vertices which are the elements of the set $\lbrace 0,1\rbrace^n$ of $n$-bit binary strings, and an edge is drawn between each pair of vertices representing a pair of strings differing on precisely $1$ bit.

Definition 2. The $(n,k)$-hypercube graph has vertices which are the elements of $\\lbrace 0,1\rbrace^n$, and an edge is drawn between each pair of strings differing on between $1$ and $k$ bits, inclusive.

The former is a classic of course, and the latter is a product of my imagination for the sake of some research I am doing in coding theory. For $k=n$, it would be the complete graph of order $2^n$.

Question. Has the latter structure been studied, for any $k\ge 2$? If so, I would be delighted to receive direction to known results, such as papers, theorems, keywords.

share|cite|improve this question

The graphs you are considering are technically unions of classes in the binary Hamming scheme. The Hamming scheme is an instance of an association scheme, and it is studied at some length in the classic book on coding theory by MacWilliams and Sloane. (And in other places, but this is a good starting point.)

A coclique in your $(n,k)$-hypercube is a set of binary vectors with the property that any two distinct vectors are distance at least $k+1$ (in the Hamming metric), and of course these are exactly the binary codes with minimum distance $k+1$. In his Ph.D. thesis Delsarte showed how to use linear programming, in combination with the theory of association schemes, to derive useful bounds on the size of codes.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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