0
$\begingroup$

Consider the 4D hypercube, with white-colored vertices. If you pick a vertex $v$, all the (4) adjacent vertices are colored black. $v$ itself is not colored black.

What is the name of the graph covering that colors all vertices of the 4D hypercube black, by picking only 4 vertices (with similar properties as $v$)?

Is this covering unique (except for orientation and symmetry)? Is there a more rigorous algorithm, that chooses the correct $\frac {2^n}{n}$ vertices to satisfy the graph cover a $n$ dimensional hypercube, where $n$ is any power of 2?

$\endgroup$
2
  • $\begingroup$ Do you know for a fact that there is such a covering? $\endgroup$ Apr 23, 2017 at 9:30
  • $\begingroup$ I'm not well versed with graph theory, so here's an algorithm and diagram. Algorithm: within the 4D hypercube, within one of the inner 3D cubes, choose 2 diametrically opposite vertices. Choose the "same" 2 vertices on the other inner 3D cubes. These 4 vertices satisfy the covering. What I'm interested in is a more rigorous algorithm, that chooses the correct $n$ vertices to satisfy the graph cover a $n$ dimensional hypercube, where $n$ is a power of 2. Diagram: edges of hypercube are lines. 4 vertices chosen for graph cover are blue circles. imgur.com/a/v91sS $\endgroup$ Apr 23, 2017 at 9:57

1 Answer 1

1
$\begingroup$

Here's a more general construction that works in $n=2^r$ dimensions for any $r$.

Note that for each vertex we pick, that vertex itself will not be colored black by picking it, so we must also pick an adjacent vertex. So we might as well devote one of the coordinates to dealing with these adjacent pairs. That is, if a vertex has coordinates $(x_0, x_1, x_2, \dots, x_{n-1})$ with $x_i \in \{0,1\}$, then we will declare that $(0, x_1, x_2, \dots, x_{n-1})$ is picked whenever $(1, x_1, x_2, \dots, x_{n-1})$ is picked.

This is equivalent to a problem in $n-1$ dimensions where picking a vertex does color that vertex black. So now we want to pick some vertices in $n-1$ dimensions such that each vertex is either picked and has no adjacent picked vertices, or is not picked and has exactly one adjacent picked vertex. This can be accomplished by picking all the codewords in a $2^r -1$ dimensional Hamming code (Wikipedia link).

Translated back into the $2^r$ dimensional setting, this results in the following construction. Number the coordinates in binary: $$\underbrace{00\dots00}_r, \underbrace{00\dots01}_r, \dots, \underbrace{11\dots11}_r.$$ Then pick all vertices that satisfy the following $r$ conditions:

  • Among the coordinates numbered $0\dots001, 0\dots011, 0\dots101, 0\dots111, \dots, 1\dots111$, an even number are $1$'s.
  • Among the coordinates numbered $0\dots010, 0\dots011, 0\dots110, 0\dots111, \dots, 1\dots111$, an even number are $1$'s.
  • In general, if we pick all coordinates whose $i^{\text{th}}$ bit is set, an even number of those are $1$'s.

Note that none of these conditions specify anything about the $00\dots00^{\text{th}}$ coordinate of a vertex, so that is the "free" coordinate where we pick a vertex with $0$ and also pick a nearly-identical vertex with $1$.

You can check that this colors every vertex black. Given a vertex, if it is one of the picked vertices, change the $00\dots00^{\text{th}}$ coordinate, and you will get another picked vertex. If a vertex is not one of the picked vertices, find all the parity conditions that fail, let $i$ be the coordinate with a $1$ in all the bits corresponding to the failed conditions; change the $i^{\text{th}}$ coordinate, and you will get a picked vertex.

$\endgroup$
5
  • $\begingroup$ I follow until the parity conditions - why does even parity ensure a minimum graph covering? $\endgroup$ Apr 26, 2017 at 6:41
  • $\begingroup$ The easiest way to check that this is best possible is because, out of $2^n$ points, $2^{n-r}$ satisfy $r$ linear conditions: and we can't do better than $2^{n-r} = 2^n/2^r$ because each vertex only colors $2^r$ others. We check that this does color all vertices by showing how to find a picked vertex adjacent to any vertex we like. $\endgroup$ Apr 26, 2017 at 13:32
  • $\begingroup$ Oh I think I get it - picked vertices corresponds to codewords in a single error correction hamming code, which is a minimum graph covering - but I still don't get how you define the codewords from the parity checksums. Why does an even number of picked vertices for every set of coordinates which the ith bit is 1 lead to a set of SEC codewords? $\endgroup$ Apr 27, 2017 at 0:21
  • $\begingroup$ Have you read the wikipedia article? $\endgroup$ Apr 27, 2017 at 1:37
  • $\begingroup$ Yeah I've read it. I know how a hamming code works, and I can show how a given set of codewords based on parity of some bits is SEC, and I create codewords based on trial and error, but I don't know the rules to create codewords. And I can't seem to find any resources on the net. $\endgroup$ Apr 27, 2017 at 3:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .