Given a set of six colours, in some order (i.e. an ordered 6-tuple), how many ways are there to map the set to the faces of a cube, so that no pair of successive colours is on an opposite pair of faces, i.e. each successive colour pair has at most one edge between them?
We can map this problem to a graph by treating each face as a vertex and each edge as, well, an edge. Every satisfying map then corresponds to a Hamiltonian Path; that is, a path that traverses the graph while visiting each vertex exactly once. If you want the color list to "wrap around" so that 6 is adjacent to 1, then every satisfying map is a Hamiltonian Cycle. Either way, counting the number of satisfying maps is not quite the same as counting the number of Hamiltonian Paths/Cycles, because cubes have a high degree of symmetry. I doesn't matter where we put color 1, because we can always rotate the cube so that our initial face is pointing up. (Any other direction would work as well; we just have to pick a convention for the starting point and rotate our cube to match it.) Similarly, it doesn't matter which face gets color 2, because we can always spin the cube until color 2 points to the right (again, the direction is arbitrary). Once we set the directions of two faces, all the rest are fixed, so any further permutation of colors is a unique coloring. To put this back in the language of graphs, we can arbitrarily choose vertices 1 and 2 where colors 1 and 2 will go, respectively. Then, our goal is to count the number of Hamiltonian Paths/Cycles that start with 1 -> 2 and proceed to traverse the rest of the graph. Counting Hamiltonian Paths is a #P-Complete problem, so it's impossible to find a completely general solution. But for a cube, it's easy enough to brute force. Say we've labeled our cube such that vertex 1 is the top face, vertices 2-5 form the loop around the sides, and vertex 6 is the bottom. Starting with 1 -> 2, our next step can be to 3, 5, or 6. Going through each option in turn: * If we go to 3, then our subsequent step can be to either 4 or 6. Either way, this leaves us adjacent to both remaining vertices, so we can pick them up in either order. This gives a total of 4 Hamiltonian Paths. If we're looking for cycles, we can't end at vertex 6, so 4 -> 5 -> 6 is eliminated but the other 3 options still work. * Since our setup has reflective symmetry, going to 5 gives us the same number of options as going to 3. * If we go to 6, then our subsequent step can be to 3, 4, or 5. 3 -> 4 -> 5 and 5 -> 4 -> 3 are both valid paths, but going to 4 leaves us stuck, so there are 2 Hamiltonian Paths. Both of them are also Cycles. All told, then, we're looking at 10 valid color maps, or 8 if we require that color 6 be adjacent to color 1.
Yes, that did occur to me. And since there is one and only one edge between vertices, the graph is either a Hamiltonian path or a Hamiltonian cycle, as you state. So there is a sequence of edges associated with each, five for a path or six for a cycle. Indeed; if it's color 1 that's where we always start, it's the first place (color 1 could be represented by the number 1, so the second place is occupied by the number 2 and so on). I think that means you can say 2-colouring any two adjacent faces of a cube is an equivalence class. But there are two different ways to 3-colour adjacent faces, one way has colour 3 opposite colour 1 (i.e. not adjacent), the other has two distinct orientations of three colors (all adjacent on a cube). And as you say, identifying two adjacent faces orients the remaining ones. Note that it's impossible to colour the graph with only two colours, given the usual rule that colours must be different across boundaries, evidently you can colour at most four faces. I'm still thinking about the difference using a third colour introduces, like giving it one more degree of freedom, albeit constrained by cubic symmetry.
And I started thinking about it from the point of view, given a cube with six different colours-a fixed map, how many sets of edges between adjacent faces are Hamiltonian paths or cycles. Which I see as equivalent to asking: for a cube which has a fixed colouring and is on a plane surface, if the same colour is 'down' first in each case, how many ways can the cube be rotated on the surface across a sequence of edges, without slipping, so each face is in the down position or flush with the surface once? So you can think about printing the colour on each face in a sequence that records a sequence of rotations across "fixed" edges. But this is just equivalent to looking at each face in a sequence that doesn't have repeats.
I think I've seen a way to think this through. Suppose you have a blank cube, you colour two adjacent faces leaving four faces blank. This is an equivalence because there is only one edge between any two faces. Now colour two more faces in the same way, with two different colours than the first two. Again the two faces have one edge between them, but must have three more edges adjacent to the first two colours (so how many ways can the second pair of faces be oriented relative to the first pair? is it three?). Now colour the last two faces which must again have one edge between them, and all the other edges adjacent to the first four colours. There must be only two ways to colour the last pair. But either colouring is equivalent if the problem is to visit each face once. So I get 3 possible colourings.
Nah, I got it wrong. I guess if you're good at spatial reasoning you can "think it through", but I got losted. With paper, you can draw squares in a pattern that, when you cut it out, will wrap around a cube (or, it won't). So any pair of squares which are edge-adjacent will do this, i.e. you can always wrap two adjacent squares onto a cube given the sizes match. With three squares you get three patterns, and if you think about it as adding two pairs of squares (i.e. (1,2) + (3,4)) there are 6 ways to do this. But two of these six have only one way to add squares (5,6) to the first four. So yeah, 10 altogether.
So, of course, because a cubic graph has a dual graph, the problem is also equivalent to finding all Hamiltonian paths in the dual of a cubic graph. But a sequence of faces of a cube is also a subset of a tiling of the plane, there are 10 sequences which correspond to Hamiltonian paths. So if the plane is like a space to which the 10 sequences are mapped, is the set of sequences a fiber over a base space? That is, given one face of a cube as a start point, all 10 sequences (a total space) can be found on the rest of the cube?
Each of the 10 Hamiltonian paths is a fiber if: each path is topologically equivalent. I think that means, given a Hamiltonian path over six faces of a cube or equivalently, over six vertices of an octahedron, you can deform any sequence into any other. That means something like "wrapping" a given sequence, then "unwrapping" it in a different sequence. The ideal fiber is just any Hamiltonian path. But some (6 I think) paths are also cycles. The map that takes sets of adjacent squares in the plane to the faces of a cube is this "wrapping" function. You can consider "unwrapping" the faces as akin to slicing edges and peeling off the faces so you have a connected set of six squares; there is one and only one way to peel a single face from a cube, you have to slice all four edges of that face, to peel off two adjacent faces, you have to slice three edges on each face leaving one edge intact, and so on. But you don't have to do any of this except in a mathematical sense, in fact all you need is a sequence of faces which is equivalent to a sequence of rotations of the cube.
So, combinatorially, there are 6! ways to colour the faces of a cube from a set of 6 colours. The first set is "free", but once you start colouring, things can change. If you have a cube which is already coloured this way, then there are six ways to choose which face is the first face. If you then introduce the rule that going from face to face is equivalent to going from vertex to vertex in the cube's dual, the octahedron (or you're traversing a graph), you then have four ways to choose which face is the second colour. Next, there are three ways to choose the third (in some "cubic order"), and two ways to choose the last two faces (because there is only one way to choose the 6th). That's 6 x 4 x 3 x 2 x 1 = 6! / 5 = 144 For some reason, because the second face can't be opposite the first, reducing the choices from 5 to 4, you get the total number of combinations reduced by a factor of 5. And there are 10 patterns of squares "in the plane" which correspond to complete walks, visiting each vertex once. If you look at these patterns, you see each has a mirror image, a reflection symmetry. So arguably there are 5 patterns with reflections. Reflecting through an internal line of symmetry is equivalent to reflecting through some external line (modulo rotations). Each of the 10 graph-walks is invariant under rotation (say, from horizontal to vertical in a square tiling), but not reflection.
I skipped over the 4th choice, this one actually has two possibilities, the last two are fixed once four choices have been made because the cube has a fixed colouring (if it didn't and you were colouring as you go, type of thing, there would be more choices). So, I think, one way to look at the combinations/permutations is as a set of colours over each square in a Hamiltonian path, respectively, over each vertex in the dual graph. The dual graph embeds on the sphere, so you can consider a path as a particular unrolling of a sphere (along geodesic sections) which has been divided into eight equal-area sections, or octants. For example, consider a path that starts at the "North pole", moves to the equator, then moves around the equator through four vertices, then to the "South pole". Since you fix two opposite poles, you can cyclically permute the four vertices around the equator. Hence there are four distinct paths, and the mirror path also has this multiplicity. But there are six choices for which face is the "North pole", so there are 6 x 4 = 24 distinct paths for each square pattern. Then the set of colours over each square is generally: six over the first square (North pole), four over the second square (determined by the first choice), three over the third square (again determined by the previous choice), two over the fourth square, and one over each of the fifth and sixth squares. In the pole-to-pole traversal, choosing the first colour also fixes the sixth colour. Choosing the second colour plus a direction fixes all the other colours
Ha. As usual when I start looking into some mathematical topic, I realise I haven't fleshed out all the details. And I make mistakes. There are 144 x 2 = 288 possible permutations of the faces over all paths/cycles because there are two ways to choose the 4th, and also two ways to choose the 5th face. But no matter, I've also worked out that there is only one pair of Hamiltonian paths, this should be obvious because to not be adjacent, the first and last faces have to be opposite, so the remaining four faces (on an equator), can only be traversed in one of two directions apart from having cyclic permutations. And I've figured out that the remaining four pairs are all cycles, so it doesn't matter where you start, and starting in a different place means you 'transform' a given pattern of squares into one of the other cycles (but not into a reflection). So there are in fact two distinct Hamiltonian cycles plus their reflections, plus the transforms. The path (and its reflection) which is not a cycle won't transform like this, you have to start at one of the poles. One of the cycles (and its reflection) transforms into itself when you start at a different location, the pattern is invariant. The other pair of non-cycles can't transform so its like another identity.
Label the colors 1-6. Color a face of the cube with color 6. Five colors remain with which to color the opposite face. Thus there are five unique ways to pair color 6 with an opposite color. Four colors remain and four faces in a belt remain. Pick the lowest order one and color one face, thus breaking the circular symmetry. Three colors and three faces in a row remain, so there are 6 ways to color them. Thus a total of thirty distinguishable ways of coloring all six faces. Further, you may identify which cube you have by orienting the cube such that color 6 is at the top and the lowest number of its neighbors is facing you. Top-bottom-facing-left-back-right 612345 to 651432 This identification scheme gives the second way to count the choices. 6!=720 ways to map colors to faces but this is an overcount since turning the face with color 6 as the top face reduces distinct choices by a factor of 6 while rotating the cube about the new vertical axis reduces the distinct choices by another factor of 4. 5 • 3! = 6! /( 6 • 4 ) = 30 From this set of thirty, you need to remove the cases where adjacent colors are on opposite sides, which as pointed out above begs the question: are colors 1 and 6 adjacent? Assume yes. Case I: top 6, bottom 1 or 5: FORBIDDEN Case II: top 6, bottom 2, near 1 back 4: 2 choices Case III: top 6, bottom 4, near 1 back 3: 2 choices Case IV: top 6, bottom 3, near 1 back 4: 2 choices Case V: top 6, bottom 3, near 1 back 5: 2 choices So 8 cube choices remain. If 1 and 6 are not adjacent then Case I becomes: Top 6, bottom 1, near 2, far 4: 2 choices and the total becomes 10.
I've been trying to relate this to an old article about fiber bundles. To get there, I need to have a cubic graph with 8 vertices embedded on a sphere along with its dual graph. The article I refer to describes how to lift a path from the base space to the total space, but, both spaces are continuous (if all points on a sphere are in the space) whereas a graph is a discrete set of points. Nonetheless I think there is a way to define curvature via parallel transport--fix a direction in one of the 10 patterns in the plane and transport it around the sphere (resp, the cube or its dual). I've reasoned that, given a first square, rotating the cube to a second square also defines a direction. If you now rotate to a third square which is perpendicular to this initial direction (keeping the initial direction parallel) then back to the first, you have a pattern of four squares with a common vertex--a square pattern of squares--but the first and last squares in the pattern correspond to the square you started on. To wrap this pattern onto the faces of a cube, you have to wrap the first and last squares to the same face of the cube. Investigating what happens to the direction of the parallel vector, it gets rotated by 90 deg. Giving each of the 10 paths a parallel transport 'mechanism' should also give them this property. To make this a bit more concrete, for each pattern of six squares, draw the dual graph as a set of vertices, one in the centre of each square, and connect them with edges, then draw arrows along the edges all in the same direction (i.e. all parallel), and 'roll' the pattern plus arrows onto a cube. (This notion of rolling a sphere along a straight line with arrows drawn on it is something the article uses, and topologically a cube is a sphere). Another avenue is considering which faces of a cube are not flush with a plane surface and how that changes in a given pattern (or repeating a given pattern, say).
In this article I keep referring to, the canonical example of finding a reference direction on a sphere is explained. You can't assign the same direction to every point, but you can do this on a hemisphere. If you project a hemisphere onto a circle in the plane, you have lines of latitude as concentric circles which can have the same reference direction assigned to every point. The fiber over every point is a topological space in which an angle relative to some reference direction (defined everywhere) is a point on a vertical line (the fiber) over that point, and together all the fibers are a bundle which looks like a solid cylinder. The height of this cylinder is given by the maximum angle of 2π. Well, that's the continuous version. If you have a cube with one face on a plane, the rest of the cube is topologically equivalent to a hemisphere with four points on an equator plus one at a pole. There are only five fibers, you can only have a path from fiber to fiber in lots of π/2. And by golly, this is in the example. The path is called a connection and it means having to give the topological bundle some extra structure, what the authors call a path-lifting rule. All the curvature in the base space is in the concentric circles, transporting a direction (vector) from the centre towards an equator is a flat line, but transporting it around the equator or a line of latitude 'lifts' the path in the total space. Around the equator you have the path lying on a set of parallel planes assigned to every point in the total space coincident with the path, all at the same angle. All the curvature in this connection on the fiber bundle after lifting the path from the base space is now in these fixed plane surfaces. . . With squares in the plane you have sequences of faces in two dimensions, with a map to sequences of orientations of a cube in three dimensions, a bundle of orientations. So a correction: a path isn't a fiber, it's a connection on a bundle of fibers.
Here is a diagram from the article: Please Register or Log in to view the hidden image! It's a bit smudged, but you can see how all the plane surfaces in the fiber bundle are at the same angle on a given line of latitude. The left diagram is relevant to the "path around a cube" problem, the right diagram illustrates parallel transport (topologically) around a fixed latitude. Anyone interested in the article itself can find a copy here.
Please Register or Log in to view the hidden image! This is an image of a square tiling and its dual. The square is one of three regular tilings of Euclidean 2-space. Ok, so we want to colour squares in a certain pattern that corresponds to Hamiltonian paths over the faces of a cube. Then with this added feature (a way to trace paths), the dual of the coloured square tiling defines a structure which is not a cube, but its dual in Euclidean 3-space (yay!). But that's because the relations between edges and vertices in the space and its dual space change, when you define paths this way. Because the paths over the square tiling are also over a cube, all of the free edges in two dimensions are glued together (pairwise) in three dimensions. But can we consider a square tiling plus its dual, with a colouring "algorithm" to represent (I think that means: lift to) a tiling of the 3-plane? Does this tiling then represent the faces of a tiling of the 4-plane? What kinds of clues are there in the fact there are only ten patterns, two of these are the only two ways to find a path from pole to pole, is it possible to close these paths somehow?
We can think about symmetries of the spaces above as having a global and a local structure. The geometries are used as a basis to set up a kind of notation--strings of square faces with such strings having more than one dimension as a string like abcdef is one-dimensional. What's globally symmetric about a square tiling? There are no gaps, it's a dense packing. Its dual is another square tiling, it's homogenous or composed of the same thing everywhere and in all directions. Rotating the plane doesn't change anything. But define a set of paths over this tiling such that we can consider each path to have a "cube's worth" of information once we account for all the gluing, and we break up the symmetry, although locally we just move "symmetrically" from face to face of a cube, something we can do by rotating a cube keeping in the same place. This moving from face to face is a local gauge symmetry (if I understand t"Hooft at all).
Had to use the dictionary for , tiling , Hamiltonian paths and more , just trying to understand the concept here. Right or wrong , ( I wouldn't really know ) , but it did expand my mind . Thanks river
Well, I don't really know if I have even half of it right. Nonetheless, a square tiling isn't a hard thing to think about. There are a couple of things though, about colouring the squares. Suppose you can colour the tiles randomly with n colours, then if n is at least 6, there must be a patch somewhere that corresponds to a Hamiltonian colouring. In the dual tiling, each tile can have more than one colour on each face. But there will also be Hamiltonian paths in this dual space. Is there a way to do something in the third dimension (when the path is on a cube) that generates a dual path? Maybe you can see where this might be going.
