The foolproof cube – a study in symmetry

Besides being a fun toy, and perhaps the most popular puzzle in human history, the Rubik’s Cube is an interesting mathematical example. It provides a nice example of a nonabelian group, and in another article I may discuss some features of this group structure. This expository article is about an experiment, where I made Rubik’s cubes with two or three colors, instead of six. In particular, I want to mention an interesting observation made by Dave Rosoff about one of the specially colored cubes: It turns out to be foolproof, in the sense that no matter how one breaks it apart and reassembles the pieces, it is still solvable by twisting the sides. It is well known that this is not a property that stock Rubik’s Cubes have.

The first observation about the physical construction of the cube is that it is made out of 21 smaller plastic pieces: a middle piece with 6 independently spinning center tiles, 12 corner cubies, and 8 edge cubies.  The frame includes 6 of the stickers. Each corner cubie has 3, and each edge cubie has 2. (And this accounts for all of the 6 \times 9 =54 = 6+ 12 \times 3 + 8 \times 2 stickers. These stickers are on a solid piece of plastic, so they always stay next to each other, no matter matter how much you scramble it by twisting the sides. (I remember getting really mad as a kid, after figuring out that someone else had messed around with the stickers on my cube. Still a pet peeve, taking stickers off a cube is like fingernails on a chalkboard for me.)

So anyway, it’s impossible to get two yellow stickers on the same edge cubie, for example, because that would make the cube impossible to solve: you couldn’t ever get the two stickers onto the same side. But this is not the only thing that can’t happen. Let’s restrict ourselves from now on to just the positions you can get to by taking the cube apart into plastic pieces, and putting them back together. If you take it apart, and put it back together randomly, will you necessarily be able to solve it by only twisting sides? (Of course you can always solve it by taking it back apart and putting it back together solved!) I knew, empirically, as a kid that you might not be able to solve it if you put it together haphazardly. Someone told me in high school that if you put it together “randomly,” your chances that it was solvable were exactly 1 in 12, and explained roughly why: it is impossible to flip an edge (gives a factor of 2), rotate a corner (a factor of 3), or to switch any two cubies (another factor of 2).

This seemed plausible at the time, but it wasn’t until a graduate course in algebra that I could finally make mathematical sense of this. In fact, one of the problems on the take-home final was to prove that it’s impossible to flip any edge (leaving the rest of the cube untouched!), through any series of twists. I thought about it for a day or two, and was extremely satisfied to finally figure it out, how to prove something that I had known in my heart to be true since I was a kid. It is a fun puzzle, and one can write out a proof that doesn’t really use group theory in any essential way (although to be fair, group theory does provide a convenient language, and concise ways of thinking about things). For example, it is possible to describe a number 0 or 1 to every position, such that the number doesn’t change when you twist any side (i.e. it is invariant). Then provided that the property prescribes a 0 to a solved cube and a 1 to a cube with a flipped edge, the invariance gives  that the flipped edge cube is unsolvable.

Several years ago, I got inspired to try different colorings of a Rubik’s Cube, just allowing some of the sides to have the same color. I was picky about how I wanted to do it, however. Each color class should “look the same,” up to a relabeling. A more precise way to say this is that every permutation of the colors is indistinguishable from some isometry. (Isometries of the cube are its symmetries: reflections, and rotations, and compositions of these. There are 48 in total.)

It turns out that this only gives a few possibilities. The first is the usual coloring by 6-colors. Although there are several ways to put 6 colors on the faces of a cube,  for our purposes here there is really only one 6-color cube. There is also the “Zen cube,” with only one color. (“Always changing, but always the same.”) But there are a few intermediate possibilities that are interesting. First, with two colors, once can two-color the faces of a cube in essentially two different ways. Note that since we want each color class to look the same, each color gets three sides. The three sides of a color class either all three meet at a corner, or they don’t. And these are the only two possibilities, after taking into account all of the symmetries.

So I bought some blank cubes and stickers, and made all four of the mathematically interesting possibilities. (I keep meaning to make a nice Zen cube, perhaps more interesting philosophically than mathematically, but I still haven’t gotten around to it. ) My friend Dave Rosoff and I played around with all of these, and found them somewhat entertaining. A first surprise was that they seem harder to solve than a regular Rubik’s cube. Seems like it should be easier, in terms of various metrics: the number of indistinguishable positions being much smaller, or equiavalently, the number of mechanical positions which are indistinguishable from the “true” solved position being much bigger. However in practice, what happens for many experience cube solvers, is that they get into positions that they don’t recognize at the end: the same-colored stickers seem to mask your true position. Nevertheless, an experienced solver can handle all four of these cubes without too much difficulty.

When playing around with them, occasionally a cubie would pop out fall to the floor. The thing to do is to just pop the piece back in arbitrarily, and the solve it as far as you can. It is usually an edge that pops, so the probability of having a solvable cube is 1/2.  And if not, one can tell at the end, and then remedies the situation by flipping any edge back. Dave noticed something special about one of these four cubes, I think just from enough experience with solving it: no matter which piece got popped out, when he popped it back in randomly, the cube still seemed to be solvable. He thought it seemed too frequent to be a coincidence, so after a while of chatting about it, we convinced ourselves that this cube indeed had a special property: if one takes it apart into its 21 pieces, and reassembles it arbitrarily, it is always solvable by twists, a property we described as, “foolproof.” We talked it about it for a while longer, and convinced ourselves that this is the only foolproof cube, up to symmetry and permuting colors. (Well, the Zen cube is foolproof too.)

So which of these four cubes is foolproof? This puzzle yields to a few basic insights, and does not actually require making models of each type of cube, although I would encourage anyone to do so who has extra blank cubes and stickers around, or who wants a neat Cube variant for their collection.

Threshold behavior for non-monotone graph properties

One of my research interests is what you might call non-monotone graph properties.

A seminal result of Erdős and Rényi is that if p \ll \log{n} / n, then the random graph G(n,p) is a.a.s. disconnected, while if p \gg \log{n} /n then G(n,p) is a.a.s. connected. This can be made more precise; for example, if p = \frac{\log{n} + c}{n}, with c \in \mathbb{R}, then \mbox{Pr}[G(n,p) \mbox{ is connected }] \to e^{-e^{-c}} as n \to \infty. Connectivity is an example of a monotone graph property, meaning a set of graphs either closed under edge deletion or edge contraction. Other examples would be triangle-free, k-colorable, and less than five components. The fact that every monotone graph property has a sharp threshold is a celebrated theorem of Friedgut and Kalai.

More generally, a graph property is a way of assigning numbers to finite graphs that is invariant under graph isomorphism, and increases or decreases with edge deletion or addition. Examples would be the number of triangle subgraphs, chromatic number, and number of connected components.

Much of random graph theory is concerned with monotone properties of random graphs. But it is not hard to think of examples of non-monotone properties. For example, let i = the number of induced four-cycle subgraphs. Another example would be j = the number of complete K_3-subgraphs that are not contained in any K_4-subgraph. When p is very large,  p \gg n^{-1/3}, then a.a.s. every three vertices share some common neighbor, so every K_3-subgraph is contained in a K_4-subgraph and j=0. Similarly, when p is very small, p \ll n^{-1}, then a.a.s. there are no K_3 subgraphs, and j=0. For intermediate values of p, n^{-1/3} \ll p \ll n^{-1}, the expected value of j is E[j] = \theta (n^3 p^3).

So the expected value of the graph property is unimodal in edge density, and we still have threshold behavior. Can Friedgut and Kalai’s result be extended to a more general setting that includes these cases?

This is a simple and perhaps natural combinatorial example, but my original motivation was topological. I wrote a paper about topological properties of random clique complexes, available on the arXiv, which turn out to be non-monotone generalizations of the original Erdős-Rényi theorem. I will continue to write more about this and other related examples sometime soon, and as I have time, but in the meantime if anyone knows any nice examples of non-monotone graph properties, please leave a comment.

One more thought for now. It seems in many of the most natural examples we have of non-monotone properties F, the expected value of F over the probability space G(n,p) is basically a unimodal function in the underlying parameter p. Can you give any natural examples of bimodal or multimodal graph properties? (Pathological examples?)