This is a follow up on an [older](https://mathoverflow.net/questions/319940/conjecture-on-representing-graphs-within-0-1-n) 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](https://en.wikipedia.org/wiki/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?



Hamming representability of finite graphs
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$.


