Tag Archives: unavoidable sets

Exploring Unavoidable Sets: A Mathematical Insight

Posted on by
Reply

Notes

Nothing new here, only the app. The rest are stuffs that were understood long ago by Wernicke (1904), Birkhoff (1913), Franklin (1922), Lebesgue (1940). All the them continued the work of Kempe and others.

The app

See it in action here: https://stefanutti.vercel.app/waterworld-colonization.html

Colors have these meanings:

  • Light Red = F5 facing the ocean
  • Dark Red = F5 not facing the ocean
  • Green (light and dark) is for F6
  • Blu (light and dark) is for faces greater than F6
Unavoidable sets on a map with faces greater than 4

Each dot is a vertex of one of these unavoidable configurations.

Unavoidable sets: starting point

For a change 😁 let’s start with a connected cubic map on the sphere with no F2, F3, F4 faces.

Euler’s equality is always the starting point.

V−E+F=2V − E + F = 2

In all maps, every edge has two endpoints, and every vertex has three incident edges, so:

3V=2E3V = 2E

To have a formula that connects faces to vertices, we need to substitute 2E with 3V. Multiply by two the Euler’s formula:

2V−2E+2F=42V − 2E + 2F = 4

And substitute 2E with 3V:

2V−3V+2F=42V – 3V + 2F = 4

Which gives:

3F−E=63F -E = 6

For multiple reasons the canical form is normalized to 12:

6F−3V=126F − 3V = 12

One of the main reason is that the Euler’s other formula that also starts from V – E + F = 2 has the coefficient equal to 12.

∑n(6−n)Fn=12\sum_n (6 – n) F_n = 12

Move the charge from faces to vertices

Faces have a charge uqual to 6 and vertices have a charge of -3.

6F−3V=126F − 3V = 12

Each vertex receives a charge from its three incident faces, and pays a fixed tax of 3. Define:

c(v)=6n1+6n2+6n3−3c(v) = \frac{6}{n_1} + \frac{6}{n_2} + \frac{6}{n_3} – 3

Summing over all vertices:

∑vc(v)=6F−3V=12\sum_v c(v) = 6F – 3V = 12

So the total charge 12 has been redistributed from faces onto vertices without loss. This is the discharging step.

Some vertex must be positive

A sum of finitely many numbers equal to 12 cannot have all terms ≤ 0. Hence at least one vertex has c(v) > 0.

Which corners can be positive?

Without loss of generality, write the three incident face sizes as n₁ ≤ n₂ ≤ n₃, with n₁ ≥ 5 (the initial hypotheses).

c(v)>0⟺6n1+6n2+6n3>3⟺1n1+1n2+1n3>12c(v) > 0 \iff \frac{6}{n_1} + \frac{6}{n_2} + \frac{6}{n_3} > 3 \iff \frac{1}{n_1} + \frac{1}{n_2} + \frac{1}{n_3} > \frac{1}{2}

If the smallest face were a hexagon, the largest possible value would be 1/6 + 1/6 + 1/6 = 1/2, which does not satisfy the strict inequality. So the smallest has to be pentagon.

Solving it, gives the seven configurations the picture above.