Sage And Superposition
Welcome back to my blog!
Progress On Coding
Last time, I began investigating an algorithm by Brinkmann that would determine when a graph had a polyhedral embedding. Unfortunately, I could not find an implementation of the algorithm. I also had trouble getting the proper packages installed (in particular nauty) since I use Windows, while the installation procedure is listed for Mac and Linux.
I might revisit installing nauty in the future, but for now I have a better alternative. Sage is an open-source mathematics software system that gives access to many math libraries. The best is that I can use it on the cloud through cocalc.com so no installation is required! Furthermore, it runs on Python so I don’t need to learn a whole new programming language.
For my purposes, I will attempt to implement a brute-force algorithm that works as follows: first determine the genus of the graph, second determine if the embedding is polyhedral. The genus of a graph is the smallest number g such that the graph embeds on an orientable surface of genus g, which can be thought of as a donut with g holes. Since I am primarily interested in toroidal embeddings (graphs of genus 1), it helps to determine the genus of graphs beforehand. It turns that Sage already has an algorithm for computing genus, and it runs relativalely quickly for cubic graphs, the graphs of interest in this project.
Currently, I am working on code to test if an embedding is polyhedral. In theory, I only need to check if the dual graph is simple, so this should be easy using Sage.
Additionally, I have also finished reading the construction of Kochol’s counterexample for the general conjecture. The brief rundown is that he discovered a snark G22 with special properties, such that superimposing it with another snark G26 would result in a snark that polyhedrally embeds into a surface of genus 5 (donut with 5 holes). To visualize the graph, we have to “glue” the opposite edges of the squares together to obtain the end shape.
The reason the superposition works is because G26 only fails to have polyhedral embedding because the face a1 shares two edges with a2; and similarly for faces b1 and b2. Hence, performing a superposition of G22 on the edges e1 and e2 results in G74, which is a polyhedral embedding.
Following this construction, I believe it may be possible to find counterexamples on genus 3 surfaces as well, but that remains to be seen. In the coming week, I hope to finish my code and explore potential counterexamples!
- Genus – Graph Theory. (N.D.). SageMath Documentation. Https://Doc.Sagemath.Org/Html/En/Reference/Graphs/Sage/Graphs/Genus.Html
- Kochol, M. (2009). Polyhedral Embeddings Of Snarks In Orientable Surfaces. Proceedings Of The American Mathematical Society, 137(5), 1613–1619. Http://Www.Jstor.Org/Stable/20535904