# Hamming representability of finite graphs

This is a follow up on an older question.

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)$$.

We say that a finite simple, undirected graph $$G=(V,E)$$ is Hamming-representable if there are positive integers $$k\leq n$$ such that $$G$$ is isomorphic to an induced subgraph of $$H(n,k)$$.

Question. Is every finite graph Hamming-representable?

Yes. This is going to be very inefficient, but: Let $$E$$ be the number of edges and let $$V$$ be the number of vertices. I will embed $$G$$ into $$H(|E|(|V|-1),\ 2|E|-2)$$. To each vertex $$v$$ of $$G$$, we will associate an $$|E| \times (|V|-1)$$ matrix $$M_v$$ with rows indexed by the edges of $$G$$. There will be a single $$1$$ in each row, with all other entries in that row equal to $$0$$.
If $$v \in e$$, then the $$1$$ in row $$e$$ of $$M_v$$ will be in the first column. If not, we will place a $$1$$ in one of the other $$|V|-2$$ columns, so that each of the non-endpoints of $$e$$ gets a $$1$$ in a different position of row $$e$$.
If $$v$$ and $$w$$ are not joined by an edge, the Hamming distance between $$M_v$$ and $$M_w$$ is $$2 |E|$$ because they have no $$1$$'s in common; if they are joined, then the Hamming distance is $$2|E|-2$$.