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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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