Decades ago Paul Erdős used randomness to illuminate the weird world of networks — now mathematicians have gone further. #mathematics #graphtheory #randomness

https://www.quantamagazine.org/after-80-years-mathematicians-give-famed-erdos-method-an-upgrade-20260626/?utm_source=flipboard&utm_medium=activitypub

Posted into FLIPBOARD EXCHANGE FEED 🗞️ @flipboard-exchange-feed-Econopass

Bipartite Matching Is in NC

https://scottaaronson.blog/?p=9851

#HackerNews #BipartiteMatching #NC #ComputationalComplexity #Algorithms #GraphTheory

#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