Hacker News Reader

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.

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.

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

[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).

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.

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

I like graph theory a lot (even though my prof in uni was horrible at teaching it). One thing I like about it is at least we can easily visualize most graphs, as opposed to say, n-dimensional spaces from real analysis. I also like that coloring vertices is a thing, and that so many problems can be represented by graphs and we can apply so many graph algorithms on top of those graph representations.

One thing that always makes me laugh though is the terminology in math. Things like "hypercube" just get a chuckle out of me.

I didn't know what the sensitivity conjecture is but your explanation using coloring a graph is very straightforward.

> One thing that always makes me laugh though is the terminology in math. Things like "hypercube" just get a chuckle out of me.

Oh just wait until you get to physics ! :)

> I didn't know what the sensitivity conjecture is but your explanation using coloring a graph is very straightforward.

Kidding aside, thank you!

> 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?

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

Yes! 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 :)

The 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.pd...

Let v be a vertex in a N-dimensional hypercube. Assume it's colored C. It has N neighbors, which must be colored ~C if we're using 2 colors.

If you change v to ~C, v now has N neighbors with the same color. This improves on the √N you're giving.

What did I misunderstand?

Well, turns out you’re completely right and I fucked up my reduction (quite badly it seems)! Alas, it also turns out I can’t edit nor delete the post, so, hopefully people get this far down the thread and read this :)

A vertex on an nD hypercube has n neighbours, so how do you manage to colour it to have √n neighbours? Shouldn't it be n? If it's √n, then do you round it up or down?

Sorry, if it wasn't clear it should have √n neighbours of the same color! (The number of actual neighbors of each vertex is fixed, as you said, to n :)

In the latter case, you round up!

This subthread was originally in reply to https://news.ycombinator.com/item?id=26116077 but we detached it so that it can float freely to a higher place.

This is a bit of a random comment @dang, but it's always a bit of a shame when a long explanation gets posted and the comment that it is responding to dies or is downvoted for some reason or another. I've seen this happen a few times and am wondering if there is a possible fix?

I guess this is the risk one takes when responding to comments, but it feels like there might be a reasonable tradeoff/possible solution! :)

Yes, it's a problem. We can do things but unfortunately they're all manual for now, so we have to know about it, and that's a bottleneck. Thanks for letting us know!