#Higraph #Python #GraphTheory

One more small feature, and some housekeeping, and I will have a "minimum viable product" of a higraph editor!

(This picture was directly copied and pasted from the tool - not a screenshot 🤓)

In the last post I introduced the "dual complement" idea for polyhedral graphs. I'm not sure if it has any mathematical significance, but I've made a fun discovery: the dual complement of a spanning tree is another spanning tree.

This result is rather intuitive and I don't have a rigorous proof for it yet, but here are the main supporting ideas. First, a spanning tree over v1 vertices has v1 - 1 edges. We can then show, using basic duality relations and Euler's polyhedral formula, that the dual complement has v2 - 1 edges that connect all of its v2 vertices. The complement doesn't have any cycles, since those would "capture" parts of the original graph, which we know is a single component.

The original polyhedron here is a {3,5+}_2,1 geodesic, so the dual is a Goldberg polyhedron.

No AI, no apps, just my original Python + OpenGL code.

#graphtheory #dualpolyhedron #dualcomplement #spanningtree #geodesicpolyhedron #goldbergpolyhedron #3dgraphics #digitalsculpture #pythoncode #numpy #opengl #creativecodeart #algorithmicart #algorist #mathart #laskutaide #computerart #ittaide #kuavataide #iterati

Back in the day, I made a couple of demos where a Hamiltonian path is carved out on a polyhedron. Looking back, I started to wonder about the shape left around the path, and what it means in terms of graph theory. I call this shape the "dual complement" of the path.

The dual of a polyhedron is essentially the result of turning faces into vertices and vice versa. This is shown in the first clip with a snub dodecahedron and its dual, the pentagonal hexecontahedron; to keep the view cleaner, I'm only showing the edges of one at a time.

The duality transformation also affects the edges, but their number remains the same, and there's a 1:1 mapping between the original and dual edges. Each dual edge "cuts through" the original. To make the dual complement of a path, I remove the dual counterpart of each edge in the path, leaving only the stuff on the sides. It's like driving a snow plough along the path, leaving walls of snow on the sides.

For the final view, I combine original Hamiltonian paths with their dual complements.

#graphtheory #hamiltonianpath #hamiltoniancycle #dualpolyhedron #dualcomplement #snubdodecahedron #pentagonalhexecontahedron #3dgraphics #digitalsculpture #pythoncode #numpy #opengl #creativecodeart #algorithmicart #algorist #mathart #laskutaide #computerart #ittaide #kuavataide #iterati

🧠 What if missing data is not a flaw, but one of the most informative parts of a complex system?

🔗 Informative Missingness in Nominal Data: A Graph-Theoretic Approach to Revealing Hidden Structure. Computational and Structural Biotechnology Journal (CSBJ). DOI: https://doi.org/10.34133/csbj.0099

📚 CSBJ - A Science Partner Journal: https://spj.science.org/journal/csbj

#DataScience #BigData #GraphTheory #ComputationalBiology #NetworkScience #Bioinformatics #SystemsBiology #BiomedicalResearch #MissingData

Say a graph G has the Ramsey property if every 2-coloring of G contains a monochromatic triangle.

It's well-known that 𝐾₆ has this property, and therefore so does any G containing 𝐾₆. But this math SE question observes that a graph can have the Ramsey property even if it does not contain any 𝐾₆.

Question: is there a finite family F of graphs such a graph G has the Ramsey property if and only if it contains some graph from F?

https://math.stackexchange.com/q/5137768/25554

#graphTheory #ramseyTheory