4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$

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.