Extended Hypercube Graph

Question

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.

Answer 1

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.

Answer 2

That exact graph doesn't seem to have a standard name. I have heard "power of the hypercube" informally. However, there are many very related graphs, with associated literature.

One related graph starts by restricting to vertices with Hamming weight $r$. Then, for the case $k=2$, this graph is known as a Johnson graph (wikipedia) or a Kleitman-West graph (Harper's original paper). Some recent results study isoperimetric questions for these graphs. For example, see

• D. Christofides, D. Ellis, P. Keevash, An Approximate Vertex-Isoperimetric Inequality for r-sets. Elec. J. Comb. 20 (2013) #P15

and

• S. Das, W. Gan, B. Sudakov, The minimum number of disjoint pairs in set systems and related problems. Combinatorica (to appear), arXiv:1305.6715 [math.CO].

The area of Covering Codes, for Hamming distance, studies related objects as well (see wikipedia and references therein). In general, there are facts about this graph tucked away in papers that study algorithms related to Hamming distance, such as the papers on similarity search and locality sensitive hashing.