Comment by danbruc | Hacker News Reader

Comment by danbruc | Hacker News Reader

The interpretation with the cube on the corner seems pretty intuitive - the cube essentially becomes a stack of layers. For every coloring of the cube there is one layer where the transition from white to blue happens, all layers below are completely white, all layers above are completely blue. A layer with n vertices can be colored in 2^n ways.

So we just have to start in the bottom layer of an all blue cube, go through all colorings of the current layer until we get to all white, then move one layer up and repeat until we reach the top layer. When we move to the next layer up, we have to color at least one vertex white or else the coloring would not change, so there are only 2^n - 1 relevant colorings in each layer. In the end we also have to add one for the all blue cube.

1, 1-1, 1-2-1, 1-3-3-1 are the layers in dimensions zero to three. The number of relevant colorings per layer are 1, 1-1, 1-3-1, 1-7-7-1, their sum plus one are 2, 3, 6, 17. So this worked for dimensions zero to two but gives the wrong answer for three which should be 20, not 17 according to the article. Where did I make the mistake? Was the visualization with the cube oversimplifying the problem?

For dimensions four I would guess the layer structure 1-4-6-4-1 which yields 96 which also does not match 168.

"Below" in this context means "directly below and connected by a line" (the lines are the edges of the cube). So you can have a blue vertex that is vertically below a white vertex, so long as they are not connected by an edge. The first time this can happen is for a 3 dimensional cube. You can have blue at the top, then 2 blue and 1 white below that, and then 1 blue (under and between the 2 blues in the layer above) and 2 white in the layer below that, and then white for the bottom vertex. This configuration can be rotated 3 ways and this takes us from 17 to 20.

There needn't be a layer such that all layers below are completely white and all layers above are completely blue.

For example, consider a cube. It has four layers. We could say the bottom-most layer is the one with (0, 0, 0).

Above that, there's a layer which contains (0, 0, 1), (0, 1, 0), and (1, 0, 0) [the entries with a single 1].

Above that, there's a layer which contains (1, 1, 0), (1, 0, 1), and (0, 1, 1) [the entries with two 1s].

Above that, there's a layer which contains (1, 1, 1).

We could make (0, 0, 0), (0, 0, 1), (0, 1, 0) and (0, 1, 1) white, while making (1, 0, 0), (1, 1, 0), (1, 0, 1), and (1, 1, 1) blue.

Note that all the blue values will have a 1 in the first position, while all the white values will have a 0 in the first position, ensuring monotonicity.

But both the "single 1" and the "double 1" layers have a mix of blue and white within them. So there's no single transition layer, as you put it.

You are right, I also just figured that out. They did not simply mean above in the sense of higher above the table but taking into account the edge structure, should have though about it in terms of monotone functions.

Yeah I've always found these examples are kind of a Sorting Hat for math students. I find the monotone functions definition much more intuitively graspable but a lot of people find the N-cube definition or the subset definition much more amenable.

the layers of the cube are just the number of elements in the set, for the cube on 4 elements 1,2,3,4, we have the coloring where every set containing 1 is blue. certainly there is a blue one element set {1} so by your intuition, every three element set must be blue, but {2,3,4} does not contain 1, so it is white.

Reply on news.ycombinator.com