CR/Gale Search (Basic Description):
a two pronged computer based search for polytopes
Stage 1: (CR Search)
This is a “top down” approach using a technique I call “Clique Replacement”. (This is described in a separate file.) This procedure is purely combinatorial and quite fast. The catalogues produced in this fashion theoretically would include all polytopes of a fixed dimension and number of facets but for larger dimensions it is infeasible to produce the entire catalogue.
The major drawback is that the catalogue produced includes many combinatorial objects that do not correspond convex polytopes.
(Note: For the 3d case, the objects are guaranteed to be polytopes. For the case of 4d polytope with 8 facets, the search procedure correctly replicates the catalogue first produced by Grünbaum and Sreedharan with Brückner’s and Barnette’s Spheres added.)
Stage 2: (Gale Search)
This is a “bottom up” approach using sets of vectors that represent the Gale transforms of polytopes. In this stage, the objects produced are guaranteed to correspond to polytopes.
In some sense, the catalogues produced in this fashion would include all polytopes but assessing whether all possibilities have been produced is much more subtle than in Stage 1. In particular, this approach cannot directly determine whether all the potential “clique replacement neighbors” of a given polytope have been produced. (In contrast, Stage 1 immediately produces all such potential “neighbors” but with no indication of which of these combinatorial objects are realizable as convex polytopes.) Moreover, the Stage 2 technique is likely to be considerably slower than Stage 1.
Interactions:
While each of the programs described above has deficiencies, the two complement each other well. Ultimately, a search can be devised that exploits an interplay between the two approaches.
Short term Goals
A preliminary version of Stage 1 successfully ran in late November. However, there are several important modifications that I will make as soon as time permits. Once I’m confident of the accuracy of the catalogues, the highest priority will be to check the results against all known enumerations of polytopes and topological spheres.
I have included some “preliminary data” from Stage 1. The data is ONLY included to demonstrate that the program is running and to give some indication of what kind of information the search program can produce. There are several more focused “Stage 1 experiments” that I’ll be running in December and January.
I hope to have Stage 2 up and running by March.
Longer term hope
It is my hope that the programs can eventually become a sort of laboratory for polytopes. One possibility would be a series of instructional computer labs but a larger goal would be for the programs to act as a kind of “research laboratory”. This would provide a variety of explorations suitable for undergraduate or Master’s level research.
The investigation will form the basis for a “Research Experience for Undergraduates” (REU) to be held at Lafayette College in the summer of 2008.
Here is an excerpt from the REU description:
This project will mostly have the nature of “Experimental Mathematics”. As researchers, you will use the computer to explore the unknown terrain of these higher dimensions with a variety of possible goals. One goal would be the formation conjectures to be formally decided (i.e. logically proved or counter-examples found). A different goal would be to pose interesting questions then design “experiments” to collect the data needed to answer those questions. A third goal would be the “construction” or “discovery” of polytopes with particularly interesting or beautiful structure.