Unknown's avatar

About stefanutti

V: "Do you know me?" S: "yes." V: "No you don't." S: "Okay." V: "Did you see my picture in the paper?" S: "Yes." V: "No you didn't." S: "I don't even get the paper."

Lonely pentagons: Digging arbitrarily deep wells on a sphere


Another wild goose chase.

I was convinced that cubic maps on the sphere without F2, F3, and F4 faces were forced to have large clusters of F5 faces. But I’ve actually found an infinite family of counterexamples showing that it is possible to build maps of arbitrary size, with faces of arbitrary size, with no face smaller than a pentagon, and with every pentagon kept strictly isolated from every other.

Anyway, I don’t mind chasing wild geese, quite the contrary actually, because this wonderful theorem keeps showing me things I didn’t know, bringing me to the work of people I didn’t know.

Surgery on a sea of hexagons

Everything below happens far out in the hexagonal ocean of a giant Goldberg map. See Fullerene structure or Goldberg polyhedron for details.

The basic act of surgery is brutal and simple: delete one edge together with its two endpoints, and smooth the two resulting degree-two corners. Four faces feel it. The two faces that shared the edge merge into one face of size a+b−4 (6+6−4=8 sides); the two flanking hexagons drop to pentagons. This is the famous 5-8-5 defect of graphene physics (a reconstructed divacancy: two missing atoms) Volterra studied. Net charge: +1−2+1=0. Crucially, the surrounding ring of hexagons is combinatorially untouched. The defect is invisible from one ring away.

From there, the whole game is choosing the right edge so that the F5 face glides over the ocean to be kept as isolated as wanted.


I was already familiar with Paul Wernicke and Philip Franklin, who hunted the Four Color Theorem by proving unavoidability results: in any cubic spherical map with all faces of size at least five, some pentagon must sit next to a face of size at most six (Wernicke), in fact, next to two such faces (Franklin). Their method, discharging, the art of letting positive charge flow along edges until a contradiction surfaces, is the ancestor of the 1976 computer proof of the Four Color Theorem.

Victor Eberhard, a German geometer who lost his sight as a young man and did all of this work blind, proved in 1891 that any face-count sequence satisfying the law of twelve can be realized by an actual polyhedron, provided you are allowed to throw in enough neutral hexagons. Eberhard’s theorem is the existential backbone of everything here: the hexagons are the silent majority that makes any charge distribution geometrically possible

Vito Volterra, the great Italian analyst, supplied the deepest tool without knowing it. His theory of distorsioni in elastic bodies, cut the material, shift one lip of the cut by a lattice step, re-glue, is exactly the theory of dislocations that crystallographers and graphene physicists use today. On a hexagonal map, a Volterra cut-and-shift leaves a pentagon at one end of the seam and a heptagon at the other, with unharmed hexagons everywhere in between: a +1+1 and a -1-1, created in pairs, separable at will.

Michael Goldberg classified the highly symmetric cubic maps made of twelve pentagons and any number of hexagons, the Goldberg polyhedra, rediscovered by chemists as fullerenes and by virologists in virus capsids. A giant Goldberg map is the perfect blank canvas: a near-infinite sea of neutral hexagons with twelve pentagonal hills parked at the corners of an icosahedron, as far from each other as you please.

Learn from previously colored maps


Stay with me 👀, because this is going to like you.

I came up with an idea that feels so simple and obvious that I can’t help but wonder why I hadn’t thought of it earlier. Maybe difficult to implement 😭 but the idea it is good and simple.

I’m curious if anyone has explored something similar, or if there are known related results 🤔

Would love to hear your thoughts!

I’ve been working on the Four Color Theorem 🎨, specifically on reducing planar 3-regular graphs down to a minimal configuration and then back reconstructing them step by step using, when necessary, different color Kempe chain switches techniques.

The challenge is that while my reduction strategy works in most cases ✅, there are configurations where the reconstruction gets stuck ❌ and Kempe switches don’t resolve the conflict. Only by shuffling the order of face selection 🔀 I’ve always been able to eventually color the map.

Here’s the idea 🚀: instead of trying to design the perfect reduction strategy upfront, why not start from the opposite direction?

Since I can already color arbitrarily complex graphs (even if it requires trial, backtracking, and random Kempe switches 🎲), I can treat successful colorings as “ground truth”.

From there, I can analyze the sequence of reductions on an already colored graph and observe which choices preserve a valid path back to a full coloring 🔍

In other words, rather than guessing the best reduction strategy, I can learn it from examples of graphs that have already been four-colored.

Let’s leave the beach: pentagonal regions and the Four Color Theorem (2/2)


F5-Fn

Case F5-F5

By removing an edge between two F5 faces, you obtain an F6 face. The two adjacent faces that shared the removed vertices each lose one edge. If the two adjacent faces are actually the same face, the number of edges decreases by two.

General case F5-Fn

By removing an edge between an F5 face and a Fn face, you obtain an F(n+1) face. The two adjacent faces that shared the removed vertices each lose one edge. If the two adjacent faces are actually the same face, the number of edges decreases by two.

The problem is that maps on the sphere can exist:

Let’s go to the beach: pentagonal regions and the Four Color Theorem


I need relax. Let’s go to the beach!

Personal note: I don’t know where I am headed, so don’t follow me. I am just wandering around taking notes.

Suppose that there exist maps that are not four-colorable, perhaps only one, perhaps a few, or even infinitely many.

Now, remove from this set all maps that have regions with 2, 3, or 4 borders. For the scope of the four color theorem and without lack of generality, we can skip them. 🤞🏻 I am confident it is true, but not completely sure I can do this step of removing these maps with no further considerations. Or at least it should be proved.

Now select a pentagonal region and regard it as the outer boundary: the ocean that surrounds all other lands.

And now walk along the shoreline.

What can we say about the five regions that face the ocean?

Can one of them be always an F5?

The answer is no, not always. Fullerene graphs show that it is possible for all F5 faces to be isolated, with no two pentagons sharing an edge. The standard example is the Buckminsterfullerene. Or, more commonly a soccer ball.

C60

Can one of them be always an F6?

Euler’s formula neither guarantees nor rules out this possibility.

1 F5 – 0 F6 – 1 F7 – 2 F8 – 3 F9 – … = 12

👉 I don’t know if there are studies done to analyze these maps. F5 always surrounded by F7 or higher.

To be continued …

  • Remove an edge between F5-F5, or F5-F6 or 😦 F5-F7+
  • Analyze all combinations of colors along the new shoreline of the reduced maps, and search for a contradiction to the hypothesis that there exist maps that cannot be colored with four colors

C6000 Fullerene: a playground for the Four Color Theorem coloring algorithm


On this great website https://networks.skewed.de/net/fullerene_structures, you can view and download fullerene structures in various formats.

Fullerenes are a perfect playground to test my four color algorithm.

I used the C6000 fullerene. 6000 atoms! A fullerene is an allotrope of carbon. Its molecules consist of carbon atoms connected by single and double bonds. A perfect 3-regular planar graphs ready to be tested.

And this is the four colored version you can play with, created using:

# python3 4ct.py -p planar_inputs/C6000.planar -c 2354 -o C6000

Actually, it is the Tait edge three colored version of the graph. This is equivalent to the four colored version of the faces.

This zip file includes the C6000.dot + C6000.edgelist files.

.

See you around!

Boosting performance: Sage to Python/Networkx transition


I converted the Sage implementation to a pure Python / Networkx solution.

  • sage 4ct.py -r 2000
  • python3 4ct_without_sage.py -r 2000
SagePython3 + Networkx
Random graph creation17 min 59 s
* RandomTriangulation
22 s
* Custom
Planar embedding16 min 09 s
* dual + set_embedding=True
0 s
* Not necessary
Elaboration2 min 12 s1 min 58 s

Here is the file:

Other run:

  • sage 4ct.py -r 1000
  • python3 4ct_without_sage.py -r 1000
SagePython3 + Networkx
Random graph creation3 min 19 s6 s
Planar embedding2 min 44 s0 s
Elaboration14 s23 s

Optimizing Graph Coloring with Reinforcement Learning


This is what I will be working for a while. Restart is difficult, but necessary.

Why use Reinforcement Learning for Graph coloring?

In my Python application, that works on 3-regular planar graph, deciding which is the order of the edges to remove can be non-trivial. A naive approach randomly picks edges from F2 faces, F3, F4 or F5. This is the approach I used :-(. It leads to impasses when rebuilding the map. See https://4coloring.wordpress.com/2014/08/27/four-color-theorem-experimenting-impasses-as-in-life/

But a reinforcement learning agent can learn to make better selections over time to reduce color conflicts, I hope :-), and shed light on some properties of the graph that can be used in the proof.

The code will be here: https://github.com/stefanutti/maps-coloring-python

Remove one edge at a time from F2, F3, F4, or F5 faces. These faces represent the basic unavoidable set. This process will reduce the map to three faces, including the ocean as the external area. Afterward, I will restore the edges in reverse order, consistently working with 3-regular planar graphs. I will consider Tait coloring of the edges and apply, when necessary, Kempe’s chain color switching to the edges.

Remove edges a then restore them

For the Agent:

  • Environment initialization = The starting uncolored 3-regular planar graphs
  • Action = Select the edge to remove from the 3-regular planar graphs
  • State = The updated 3-regular planar graphs
  • Reward = +1 if Random Kempe’s chain color switching was not necessary, -1 otherwise

Color Voronoi graphs


To color Voronoi graphs using the algorithm here https://github.com/stefanutti/maps-coloring-python, it is necessary to do some adjustments first:

  • Transform it into a 3-regular graph, by adding a frame and modifying the vertices with more than 3 edges, as shown below
  • Consider the surrounding area (out of the frame) as part of the map (the ocean) and color also that

It is known that we can also suppose that exactly three edges meet at each vertex since maps that have vertexes with more than three edges can be easily simplified without affecting the search of the coloring. In other words, if you can find a coloring for the map on the right, you can use the same coloring for the original map on the left.

Here is an example of these steps applied to the following Voronoi diagram. Three vertices have a degree greater than three.

Voronoi to 3-regular graph

3-regular planar graph decomposition in cycles and 4CT


If you can prove that it is possible to decompose a 3-regular graph into cycles, all with even length, you have also proved the four color theorem.

I think this fact is already known, but I never paid too much attention to it before.

Naturally, also the opposite is true: since the 4CT is true, it means that it is possible to color it, and also get the Tait coloring. And for any two colors you choose (for example Red and Green), the related Kempe cycles form a partition of the graph and each cycle has an even number of edges.

Once the decomposition is found, since the cycles have an even number of edges, it is possible to color the edges of a cycle with two alternate colors (for example Red and Green), forming this way Kempe cycles. When all cycles are colored (with R and G), it is possible to use a third color (for example Blue) to color the remaining edges.

The resulting graph will have a Tait coloring for all edges, which is equivalent to coloring all faces with four different colors.

But, how difficult is it to find all cycles?

This one has 6 Red-Green cycles (all of even length), that form a division on the 3-regular planar graph into cycles.