We construct graph on the vertex set $\{0,1\}^n$ where $n$ is a positive integer. For $x,y \in \{0,1\}^n$ the Hamming distance of $x,y$ is the cardinality of the set $\{ i \in \{0, ..., n-1\} : x(i) \neq y(i)\}$ (i.e. we count the positions on which $x$ and $y$ do not agree).

Fix a positive integer $k \leq n$. Two distinct elements of $\{0,1\}^n$ form an edge if their Hamming distance is at most $k$ (so they are in some sense "close" to each other). We denote the resulting graph on $\{0,1\}^n$ by $H(n,k)$.

Conjecture: If $G=(V,E)$ is a simple, undirected subgraph with $|V|=n$, then $G$ is isomorphic to some induced subgraph of $H(n,1)$ or $H(n,2)$.

Is this conjecture true?


For $n\geq 8$, $K_n$ with one edge removed is not such an induced subgraph. It's clearly not a subgraph of $H(n,1)$ since the latter is bipartite.

Suppose that graph is an induced subgraph of $H(n,2)$, say it's spanned on strings $x_1,\dots,x_n$ with $x_{n-1},x_n$ not connected. Observe we may assume $x_1$ is the zero sequence, so the strings hence can be identified with at-most-two-element subsets of $[n]$ with pairwise symmetric differences of size at most two. First note that at least one of the sets has two elements (otherwise the induced graph would be complete), say $x_2$. But then at most two sets have exactly one element, ones corresponding to elements of $x_2$, let's say those are $x_3,x_4$ (we should also check for the case when $x_{n-1}$ or $x_n$ is one of those sets, but that case is easier). A little case work shows that if we have any four or more two-element sets which are pairwise intersecting, then they necessarily have a common element. Applying this to $x_2,x_5,\dots,x_{n-2},x_{n-1}$ and $x_2,x_5,\dots,x_{n-2},x_n$ have a common element. It follows $x_{n-1},x_n$ have a common element too, so they are connected in the graph. We need $n\geq 8$ here for there to be enough vertices, but this can be easily improved.

I believe a similar reasoning can be used to show that for a fixed $k$ and large enough $n$, $K_n$ without an edge is not an induced subgraph of $H(n,k)$ -- I can show this for $k=3$ (I won't bother writing that down in detail since it's a lot of case work), but for general $k$ we need some general kind of general result that if we have a family of set with large pairwise intersections, then there is some "core" contained in all of them.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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