Adrian Marple
Description of URAP
research project under
Carlo H. Sequin
I started off with a simple task inherited from the group that last year worked on Hamiltonian paths. The task of trying to find all possible Hamiltonian paths for the Platonic solids (to within congruence) was used as a warm-up, as it way the year before. Furthermore, Prof. Sequin recommended that I acquainted myself better with Python by using it to solve the problem. This was done knowing how much one of his students raves about the programming language and knowing I had to learn Python for one of my classes. I then spent a week or so mulling over the problem and considering how to approach a representation of Platonic solids that would have the proper graph structure and make it easy to check for congruence. The first problem I had was how to generate the Platonic solids in general. I knew if I could actively generate a Platonic solid, I would be able to connect it properly as the program iterated through new vertices. The solution I came up with was the following somewhat ambitious scheme for a program that could generate any of the Platonic solids given a specific input parameter pair. It was based on the idea from two dimensions demonstrated in the following diagram:
Here, in 2D at least, in order to make a regular polygon all that is required to generate it is an initial radial vector another one that sets the angle between two radial vectors. From doing this it is easy to see that the other radial vectors (i.e. 2D location of vertices) can be constructed by decomposing an edge vector into parallel and perpendicular components, negating the perpendicular component, and adding it all back together. Of course very specific angle choices have to be made in order to actually produce a regular polygon.
Now, this concept generalized to three dimensions is a little bit trickier than it is fortwo. Notice that if this exact same procedure was done in 3D, it would still only produce regular polygons (that happen to exist in a three dimensional representation). The key is recognizing that instead of operating on the line perpendicular to a circle at vertex v, the new process needs to operate on the plane perpendicular to the sphere at vertex v. This introduces another degree of freedom, which can be dealt with either by setting another vertex, or by defining the number of edges that connect to each vertex. I chose to deal with the issue using the latter solution. This solution effectively establishes the angle between edge vectors projected onto the perpendicular plane, which in combination with an proper orthonormal basis of the perpendicular plane defines the other vertex vectors without ambiguity.
After working out the kinks of this method, I was able to generate all Platonic solids given the angle between adjacent radial vectors and the number of edges connecting each vertex.
Of course I needed a way to check that what I had done actually worked. Since I was working with something that was so visually based, I managed to write some code to display three dimensional objects. Since I had already fiddled around with how to do this in java this task did not take too long. The code projected down the three dimensional vertex vectors to two by adding a certain amount in the x direction, then converting to spherical coordinates, and ignoring the radial term. Then edges were drawn by making lines connecting the new two dimensional coordinates.
Once I knew I had an accurate graph structure for all Platonic solids, creating a search algorithm to check for unique Hamiltonian paths was relatively simple. Unfortunately, as I found with my next meeting with Prof. Sequin that I had forgotten to account for one type of congruence. I was also informed of a more efficient way to code a path that made comparing paths much faster. Armed with this new information, I amended my search algorithm and satisfactorily completely the initial warm up task. What interested me more, was to see if I could use similar methods to produce all four dimensional regular polychora, and Prof. Sequin agreed that it was an interesting task and I spent the next couple of weeks working on it.
Before doing this however, I felt the need to improve my miniature graphics engine, adding improvements such as wider brighter lines for closer edges, and a queue of edges that popped further edges first (so farther objects are not drawn on top of closer ones). The result is the following type of image seen at the bottom of the page (of course I could not at the time produce the 4D tesseract).
One key to the extending the ideas which had worked for 2 and 3 dimensions was to figure out a way to express and basis for the three dimensional “vector space.” Notice that “vector space” is in quotes because it does not contain 0, but instead is a four dimensional translation of a vector space which maps 0 to a vertex. The other key was that I could use the Platonic solids I had already generated to figure out where the perpendicular component of edges connecting a vertex lay. To clarify this issue, consider again the three dimensional case. In it I had to figured out the angle between edges that were projected onto this perpendicular plane. This is, however, equivalent to placing a regular polygon in the plane, such that its center barely touches the sphere and its own radial struts comprised the projected edges. Angles are not enough touniquely describe how to project edges from a hyper-sphere onto the three dimensional perpendicular space because there is an extra degree of freedom that is not accounted for. Knowing this, the best approach, I decided, was to use the method outlined earlier for 3D but for 4D. So once any vertex had two adjacent vertices defined, two edges were defined and therefore two radial vectors of the Platonic solid, which is enough to uniquely determine how the Platonic solid is oriented, and hence sets the other radial vectors and therefore edges connected to the vertex in question. To give a little better scope of what I am talking about here are the types of connectivity for each of the regular polychora (note that edges per vertex of the polychora = total number of 3D vertices):
Simplex:Tetrahedron
Tesseract:Tetrahedron
16-cell:Octahedron
24-cell:Cube
120-cell:Tetrahedron
600-cell:Icosahedron
Needless to say it was not the easiest thing to transform this idea into working code, but sheets with formulae and hours of debugging prevailed and I was able to generate all regular polychora(albeit slowly for the massive 120 and 600 cells). Of course, knowing that I would be asked to perform some sort of search on vertices, edges, and faces, I actively connected all of these things together properly as the 4D objects were created. Upon hearing this, Prof. Sequin set me to task on a problem similar to what another group was doing for the 600-cell. The goal was to make two congruent “Hamiltonian” paths of faces that covered the entire 120-cell. Upon quick examination in was clear that the following two rules would have to hold:
Every edge has exactly 2 faces of one color and 1 of the other.
Every vertex touches 3 faces of both colors.
Also the path could not wind back on itself, but the two prior rules turned out to be more important. Before I could start work on this problem, I knew I would have to be able to generate my 120-cell faster. So I decided to make a very simple file that could store the 4D coordinates as well as all the connectivity of the 120-cell (I also did this for all the other regular polychora, but since the 120-cell was what I was working on, it was what really mattered).
Furthermore, I decided to use something I had learned from my Artificial Intelligence class to solve “Constraint Satisfaction Problems” (CSP’s) since I realized that the two above indented rules fell in that domain. I used an adaptation of the AC-3 algorithm that is used to enforce arc-consistency of a CSP to efficiently color faces when they were forced to take on a color value based on those two rules. Naturally, if it ever came upon an inconsistency while doing this forced coloring, if signal so, and the entire branch of the search would halt. As I had come to realize while coding was that the third requirement was inconsistent with the first two, and actually just made a loop through the 120-cell that only hit 30 faces. However, the program had its uses, not only could I confirm my conclusion, but I developed machinery that would be extremely useful for later searches.
The next problem posed to my by Prof. Sequin was then to see if the first two rules were consistent and if so see if the following thing could be done: if each edge is colored the color that is on two of its adjacent faces, can a Hamiltonian path be formed by at least one of the colors. He also made the very good recommendation of using something called the union-find algorithm to check to see if a path had prematurely looped on itself. Later, to see if I had implemented the algorithm correctly, I ended up doing the exact same task the group last year had done, namely, find a pair of congruent Hamiltonian paths for the 120-cell. What was most remarkable about my code is that it was able to do so under 10 seconds including preprocessing time.
Over the next several weeks, I was getting a little more bogged down with school work. Nevertheless, a more or less stead stream of new discoveries were being found out about what we ended up calling a two color “carpeting” of the 120-cell:
- It is not possible to make a Hamiltonian path that followed the two rules.
- The carpeting has I/O symmetry (i.e. opposite faces on the 4D “sphere” had the same color).
- When analyzing the edge loops, the carpeting has either 6 loops of length 100 or 8 loops of length 30 and 6 loops of length 60.
- These two types of carpeting are complementary (whenever green fit the first type, red fit the second, and visa versa).
- There is only one possible carpeting to within congruence (including switching colors).
Now that last discovery is rather profound, and interestingly enough implies the other listed discoveries. Because it is so interesting I will go into how I made this conclusion. First, to explain an intuition I had, I need to give background on the different possible edge colorings for a specific pentagon. There are only four possible colorings, two corresponding to a face colored red, and two to green. In essence this is because two adjacent green edges on a red pentagon violates the vertex rule, and a red pentagon with only red edges cannot be satisfied without violating the edge rule. Knowing these two facts the only possible coloring are the following (to within congruence):
Since I knew that all of these colorings had to exist based on arithmetic using the number of edges and faces of the 120-cell, I set initial conditions so that the first type of pentagon was rigidly defined (including the distinguishing between it and its mirror, which appears the same when only looking at the edges, but are different when considering the faces that are required to define it). Because I knew this construct had to exist, I was not throwing out any information about what types of paths can exist. Exactly as I had hoped, after traversing the entire search tree, my program came up with only 2 consistent solutions. One corresponded to what I ended up calling the red carpeting, and one corresponded to the green carpeting. Simply swapping colors would produce the other one to within congruence; therefore I concluded that there was in fact only one possible overall carpeting.
Upon further inspection if we call the red carpeting the one with 6 loops of length 100 and the green carpeting the one with 8 loops of length 30 and 6 loops of length 60, those three different loops corresponded to different loop constructions. This can be seen in the schematic diagram and program screen-shots on the next page.
Furthermore, the green type 2 path always has a red counter part that it fits into. For example, from the image above, the bottom-left and top-right paths combine to form the bottom-right image.
There are clearly more questions to be asked; however, as my time working on the 120-cell is at an end, I don’t foresee myself being the one to answer them.