3 ms·
> So, it turns out (and I will give it to you as an exercise!) that you can color 2ⁿ⁻¹ vertices of the cube with two colors without any vertices of a single col
by twic 6y ago
> So, it turns out (and I will give it to you as an exercise!) that you can color 2ⁿ⁻¹ vertices of the cube with two colors without any vertices of a single color being adjacant to each other
For n=3, a three-dimensional cube, you're saying I can colour four vertices.
But I can colour all eight.
r --- g
|\ |\
| g --+ r
| | | |
g +-- r |
\| \|
r --- g
And I think there's a simple method to take a completely coloured n-cube and construct a completely coloured n+1-cube: make a copy, flip the colours, then connect corresponding vertices.
What have I misunderstood?
- codethief 6y agoI don't think you misunderstood (or at least I interpreted GP's post the same way). I suppose GP meant to say that you can color all 2ⁿ vertices of the n-dimensional cube such that precisely half of them (2ⁿ⁻¹) are red and half of them are green and such that no vertices of a single color are adjacent to each other.
- LolWolf 6y agoYes! Sorry, I mixed up two sentences in my head there. I meant to say that you can color 2ⁿ⁻¹ green and 2ⁿ⁻¹ red (or, alternatively, you can color all 2ⁿ vertices with one of green or red) such that no two vertices of the same color share an edge. (Which is what you describe!) It’s a bit late for me to edit now, but alas :)
- rocqua 6y agoThe actual paper is rather easy to understand [1]. I glanced through it for a bit. Your construction of "Make a copy, flip the colors, the connect corresponding vertices" is very similar to the construction of the matrix A used in lemma 2.2 This matrix is essentially the adjacency-matrix of the hyper-cube, except with a few minus signs. Take the hyper-cube to have weighted edges of either 1 or -1, then the construction is. Take two hyper cubes, connect them, flip the sign of all internal connections in one of the cubes. [1] http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pd...