3 ms·
That's not the same thing. As a simple counter-example to what you're saying, given a 3D cube you can colour every vertex with either red or blue such that adj
by ColinWright 6y ago
That's not the same thing. As a simple counter-example to what you're saying, given a 3D cube you can colour every vertex with either red or blue such that adjacent vertices are different colours.
- codethief 6y agoI don't see the contradiction. In fact, Donald Knuth's simplified proof[0] phrases it exactly[1] the same way as GP: > Theorem. Any set H of 2ⁿ⁻¹+1 vertices of the n-cube contains a vertex with a least √n neighbors in H. [0]: https://www.cs.stanford.edu/~knuth/papers/huang.pdf https://www.cs.stanford.edu/~knuth/papers/huang.pdf [1]: Or almost exactly. The only difference being that Knuth's version does not make any assumptions on the set H (apart from its cardinality).
- ColinWright 6y agoOK, I've mis-understood what people are saying. I often find these colloquial re-phrasings more difficult and convoluted than the precise and exact statements, but perhaps my confusion will serve others in thinking through things.
- LolWolf 6y agoOh, I think both of these statements are quite precise (in the sense that reading them and turning them into math is rather immediate). Otoh, you are right and we are saying different things: I’m giving an equivalent formulation with a two-coloring (but there’s a bit of work to actually map it to the original problem) while the other post gives a direct formulation (though the “colors” part of the coloring is irrelevant, in that latter case).