5 ms·

The sensitivity conjecture is actually pretty simple to understand, intuitively. (Its reduction to applications, and its proof, of course, are both a little bit

The sensitivity conjecture is actually pretty simple to understand, intuitively. (Its reduction to applications, and its proof, of course, are both a little bit more of the "magical" parts so-to-speak.) The 'canonical' way of thinking about it is in terms of the hypercube graph, which is defined in the following way: - The dimension-0 hypercube graph is... just a single vertex. . - The dimension-1 hypercube graph is two vertices connected by a single edge. ⋅-⋅ - The dimension-2 hypercube graph is four vertices, connected in a square pattern: ⋅-⋅ | | ⋅-⋅ - The dimension-3 hypercube graph is the graph representing a cube! - The dimension-4 hypercube graph is the graph which takes a cube, makes a copy, and then connects the corresponding vertices. ... - The dimension-n hypercube graph is the graph which takes a dimension-(n-1) hypercube graph, makes a copy, and connects the corresponding vertices. Ok, so let's play a game (for now, think about the 3-dimensional cube graph as a concrete example): if you could color the vertices of the cube red or green, what is the largest number of red (or green) vertices you can find such that no two of the same color are adjacent to each other? Note that the 3D hypercube has 2³=8 vertices, and, more generally, the nD hypercube has 2ⁿ vertices, so you have a lot of vertices to color :) 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 adjacent to each other, but, if you try changing the color of any one vertex then at least one of the colors will have (at least) √n neighbors that are the same color! (It may be worth reading this once or twice :) This is the sensitivity conjecture! The fact that changing any one color would immediately imply that now you have at least √n neighbors that are all of the same color. (This is a slightly funky restatement of it, the usual one is in terms of subgraphs or boolean functions, but one is easily mapped to the other.) It turns out a lot of important problems (in things like voting systems, for example) can be reduced to proving this conjecture, which gives a rather neat set of results "for free" when proving it, and why it's been such an interesting object for the past uhh, quite a few years in computer science :)

swagonomixxx 6y ago
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.
- LolWolf 6y ago
  > 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!
LolWolf 6y ago
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! :)
- dang 6y ago
  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!
dang 6y ago
This subthread was originally in reply to https://news.ycombinator.com/item?id=26116077 https://news.ycombinator.com/item?id=26116077 but we detached it so that it can float freely to a higher place.
syockit 6y ago
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?
- LolWolf 6y ago
  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!
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).
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 ago
  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.
  - LolWolf 6y ago
    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 :)
- rocqua 6y ago
  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.pdf http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pd...
MichaelBurge 6y ago
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?
- LolWolf 6y ago
  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 :)

swagonomixxx 6y ago

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.

LolWolf 6y ago
> 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!

LolWolf 6y ago

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

dang 6y ago
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!

dang 6y ago

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

syockit 6y ago

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?

LolWolf 6y ago
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!

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

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 ago
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.
- LolWolf 6y ago
  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 :)
rocqua 6y ago
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.pdf http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pd...

MichaelBurge 6y ago

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?

LolWolf 6y ago
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 :)