3 ms·

FWIW, I found your explanation helpful, but introducing two colours confused it needlessly for me. I'd say: You have a hypercube of dimension n with 2^n vertic

by FabHK 6y ago

FWIW, I found your explanation helpful, but introducing two colours confused it needlessly for me. I'd say: You have a hypercube of dimension n with 2^n vertices, and you start colouring one after another of them, without having any two adjacent vertices coloured. You'll find that you can mark half of them (that is, 2^(n-1)) without any having a coloured neighbour (basically, you always go diagonal) - but as soon as you mark even one more, there'll be at least one vertex with at least sqrt(n) marked neighbours.

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 ago
  I 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 ago
    OK, 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 ago
      Oh, 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).

by FabHK 6y ago

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 ago
I 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 ago
  OK, 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 ago
    Oh, 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).