Necklaces and triangulations of quadrilaterals

Created at 2023-08-27

I enjoy to find surprising connections between seemingly disparate problems. Here is a cool example. Miriam Goetze, a friend of mine, who is writing her dissertation in the field of graph theory, has come up with a really fascinating problem for which I found a cool solution after taking a detour to a strange puzzle about necklaces.

Are there even triangulations of quadrilaterals?

Consider some planar embedding of $C_4$, the graph of a quadrilateral, into the plane.

There are lots of more or less interesting ways to triangulate such a quadrilateral.

If you interpreted "even" as an adverb, like in "Have you even tried?", you might think, these drawings answer the question in the heading: Yes, there are triangulations of quadrilaterals! But what I meant was the *adjective* "even", and this leads to a less obvious problem: Are there any triangulations such thay every vertex is of even degree, i.e. has an even number of incident edges? The exemplary triangulations do not help because both of them have two vertices of odd degree.

Anna's necklaces

Say hi to Anna. Anna's hobby is to collect necklaces with at least three pearls, all of which are either red or blue. However, Anna gets bored really quickly when she notices that two of her necklaces are not as different as they seem.

Anna's necklaces are circles with pearls on them, but they can be temporarily opened at arbitrary points to add or remove pearls. She considers two necklaces *extremely similar* if one necklace can be obtained from the other by changing the colors of two adjacent pearls and inserting a blue one in between. She considers two necklaces *similar* if one necklace can be obtained from the other by repeatedly replacing it by one that is extremely similar to it.

Because Anna gets so bored by similar necklaces, no two necklaces in Anna's collection are similar. How large can Anna's collection get?

What do necklaces have to do with triangulations?

Every triangulation can be obtained by starting with a single triangle and pasting triangles to it.

There are two ways to paste a triangle to an existing triangulation:

• (a) We can add a new vertex to our triangulation and connect it to two adjacent boundary points of the old triangulation.
• (b) If we choose a boundary vertex, we can connect the two boundary vertices that are adjacent to the chosen vertex.

Using only these two operations, we can "grow" every triangulation from a single triangle, as illustrated by the following example.

We start with a triangle. The dotted/dashed lines give a preview of the triangle that will be added to the triangulation in the next step. In the triangulations, I colored the vertices either blue or red, depending on whether their degree is even or odd. Note that if we want to grow a triangulation that exclusively has even degrees, we can apply operation (b) only if the chosen boundary vertex has even degree: It will become an inner vertex of the triangulation and we won't be able to adjust its degree afterwards.

So, if there is a triangulation of the square with only even degrees, then it can be obtained starting from a single triangle (three blue vertices on the boundary), pasting triangles onto it according to operation (a), or operation (b) for blue vertices. Every intermediate triangulation only has inner blue points, and at the end, it has four boundary points, which are blue.

How do operations (a) and (b) affect the arrangement of boundary points?

• (a) changes the colors of two adjacent boundary vertices and inserts a new blue boundary vertex in between.
• (b) removes a blue boundary vertex and changes the color of its two adjacent boundary vertices.

If we think of the boundary vertices as pearls on a necklace, (a) and (b) amount exactly to replacing a necklace with an extremely similar one, in Anna's terminology. Since any triangulation with inner vertices of even degree can be grown this way, its boundary vertices must form a necklace that is similar to the blue-blue-blue (000) necklace that corresponds to a simple triangle. (For the sake of a nice notation, we encode a blue pearls as a zero (0) and a red pearl as a (1).)

If we can show that the 000 (blue-blue-blue) necklace is *not* similar to the 0000 (blue-blue-blue-blue) necklace, we have shown that it is impossible to grow an even triangulation of a quadrilateral from a triangle, so that such a triangulation cannot exist.

Conversely, if 000 *is* similar to 0000, then an even triangulation of a quadrilateral exists -- given a recipe to obtain 0000 from 000 by replacing it with extremely similar necklaces repeatedly, we obtain a recipe to grow an even triangulation of a quadrilateral from a triangle.

Interesting observations about the necklaces

The necklace problem allows us to view the original question from a different point of view. It allows us to forget geometry and just think abstractly about an awkward rewriting system on circular words, the necklaces.

First, observe that every necklace is similar to one of the three 000, 001 or 011.The reason is that any necklace of length $n > 4$ is similar to a necklace of length $n-1$, as I will argue. If the necklace contains a blue pearl, we can remove the blue pearl and change the color of its adjacent pearls to obtain a very similar necklace. If, however, the necklace contains no blue pearl, we proceed as follows:

$\cdots 1111 \cdots \overset{\text{add 0 in the middle}}{\longrightarrow} \cdots 10001 \cdots \overset{\text{remove left 0}}\longrightarrow \cdots 0101 \cdots \overset{\text{remove right 0}}\longrightarrow \cdots 000 \cdots.$

Using three replacements, we have replaced 1111 with 000, producing a similar necklace of length $n-1$. Repeating this procedure, we finally arrive at a necklace of length three.

From the necklaces of length three, 010 is similar to 111: $010 \to 0001 \to 111$. An analogous argument shows that 001 and 100 are similar to 111. It can also be shown that 011, 101 and 110 are similar, and we conclude that every necklace is similar to either 000, 001 or 011.

So Anna's necklace collection cannot have more than three necklaces before Anna gets bored by similar necklaces. But can it really consist of three necklaces, or are there even less similarity classes of necklaces? In other words, are 000, 001 and 011 all dissimilar?

It is easy to see that 001 is dissimilar to 000 and 011 because it has an odd number of red pearls and any similar necklace must have the same parity of red pearls. It remains to decide whether 000 and 011, both having an even number of red pearls, are similar. Could there be an extremely convoluted way to transform, say, 000 into a very long necklace and back into 011, showing that they are similar, too?

I wrote a program that tries to find as many necklaces similar to 011 as possible. It outputs a list of necklaces that are similar, and hopefully finds all small similar necklaces, but it cannot determine that the list is exhaustive. Nevertheless, the list can help to find interesting patterns that nudge us into the direction of a proof. The list we obtain starts like this (sorted by length of necklaces, leaving out necklaces that are rotations or mirror images of each other):

011, 0000, 0011, 00000, 00101, 01111, 000011, 000101, 001111, 011011, 0000000, 0000011, 0001001, ...

So the program was unable to prove that 011 is similar to 000. Can we find interesting patterns in the data? Tinkering around, I found out that every repetition of 0011, such as 00110011 or 001100110011, is also similar to $011$. In fact, this is true for every other item on the list! Even more strangely, if a word is not on the list, and so probably not similar to 011, then exactly every second or every third repetition is on the list, depending on whether the number of red (1) pearls is odd or even. I found this quite surprising!

The insight to rule both problems at once

Playing around with the necklaces, I finally found out what distinguishes the necklaces (with an even number of red (1) pearls) that are similar to 011 from those similar to 000.

Start at with an arbitrary pearl of the necklace and sift all pearls in clockwise order. Mark all blue pearls with a +1 until you find a red pearl. Then mark all blue pearls with a -1 until you find another read pearl. Conutinue alternating between +1 and -1 for streaks of blue pearls until you have processed all pearls. Then sum up all +1's and -1's you found on the way. The necklace is similar to $000$ if and only if this sum is a multiple of $3$. (The sum is only well-defined up to sign, but we can decide whether it is a multiple of $3$ regardless of the sign.)

For the necklace 000, the sum is $3$, so indeed 000 is similar to 000. In the illustration on the right, the sum is $-2$, so the illustrated necklace is dissimilar to $000$.

This works because if two necklaces are very similar, one can be obtained from the other by applying one of the following four replacements:

$000 \to 11, \quad 001 \to 10, \quad 100 \to 01, \quad 101 \to 00$.

It's easy to verify for each of these four cases that if one necklace results in a multiple of $3$, so does the other. (If we start the counting algorithm at the beginning of the three-pearl pattern, the first two replacements reduce the sum by $3$, while the last two increase it by $3$.) By induction, this shows that every necklace that is similar to 000 must also result in a multiple of $3$.

Now we can easily solve the necklace problem. The necklace 011 results in the sum $1$, so it is dissimilar to 000. Hence the the necklaces 000, 001 and 011 form a collection of dissimilar necklaces and we have seen before that there is no larger one because every other necklace is similar to one of these.

We can also solve the quadrilateral problem. If there was an even triangulation of a quadrilateral, then we could grow it from a single triangle. But then the necklace 0000, that corresponds to the even triangulation, was similar to 000, contradicting the fact that 0000 results in the sum $4$, which is not a multiple of $3$.

Just for curiosity, are there even triangulations of an arbitrary polygon with $k$ vertices? If $k$ is not a multiple of $3$, the same argument shows that there cannot be such a triangulation. However, if $k$ is a multiple of $3$, then the necklace calculus leaves open the possibility of such a triangulation. For example, 000000 is similar to 000, and evenly triangulated hexagons exist indeed.

Can you find an algorithm to construct even triangulations of $3k$-polygons? And are you now able to explain the curious pattern for repetitious necklaces that I found in the data produced by my program?