Paths on Three Circles

Year: 2020 Authors: H. A. Verrill

Core claim

Three-circle path configurations can be exhaustively classified up to symmetry, yielding 165 cases and 75 Euler cycles, with a complete representative set drawn using octahedral correspondence.

Topics

Euler cycles, symmetry classes, three-circle motifs, path enumeration, Celtic knot variations

Domains

graph theory, combinatorics, group actions, Burnside’s Lemma, symmetry enumeration, Celtic knots, form drawing, pattern design

Methods

exhaustive enumeration, D3 symmetry reduction, Burnside’s Lemma, Python program, TikZ figure generation

Media

intersecting circles, arc drawings, Python, tikzpicture output

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2020 Conference Proceedings

Paths on Three Circles

H. A. Verrill Warwick University, UK; H.A. Verrill@warwick.ac.uk

Abstract

This article investigates ways to trace out the path around three intersecting circles. This is a study of symmetry and combinatorics.

Euler cycles and Celtic knots

Our starting point is the three circles motif, a fundamental symbol, for example, as a simple Venn diagram, or in combining colours.

Can you trace out the three circles, on the left in Figure 1, without your pen leaving the paper, drawing along each arc only once? This is an Euler cycle, passing through every edge of a graph exactly once [6, §4.4]. The second picture in Figure 1 shows one way. Pull the paths apart a little, to see more clearly what’s going on, as in the third diagram of Figure 1. It turns out there are 75 Euler cycles, up to rotations and reflections. If you are allowed to take the pen off the paper, making the path consist of a union of cycles, covering each edge only once, there are 165 ways. These arcs are in bijective correspondence with the edges of an octahedron, so finding an Euler cycle equates to finding an Euler cycle for an octahedron. For the octahedron, up to rotational and reflectional symmetries, there are just 38 ways, as shown in Figure 7.

This study began with form drawing [1]. In particular drawing variations of the triquestra symbol also known as the trinity knot [3] and trefoil knot. This knot appears in the center of the leftmost diagram in Figure 3. The three exterior arcs added to this figure lead to the three-circle pattern. This study exhaustively enumerates all other possible configurations obtained from these three circles.

Counting paths

The basic configuration of a path can be specified by what happens at each “vertex” - point of intersection of the circles - go left, right, straight ahead. Since “left” and “right” are ambiguous, I label the vertices type “o”, “g” or “p”, as in Figure 1. I am discussing classes of patterns - the string $c_1{c}_2{c}_3{c}_4{c}_5{c}_6$ , where $c_i\in \{o,p,g\}$ , determines the class of the pattern, i.e., $v_i$ has crossing type $c_i$ . The right half of Figure 3 shows 3 figures, all of which have type goppg. Since each vertex has 3 possible cases, and there are 6

Figure 1: First three figures show tracing out three circles. Where the circles cross is a vertex, $v_i,i=1,\dots ,6$ . At vertices, the direction of the path may change. There are three cases, as in the figures on the right, which have type “o”, “g” and “p” respectively

Verrill

Figure 2: Configurations poggpg, gpgogp, ggppog, gpppg, gppgg, pggop are all the same up to $D_3$ symmetries of rotation and reflection

Figure 3: Celtic knot variation shown left. Generally, paths must lie on circles, centered $p_1$ , $p_2$ or $p_3$ , as in the second figure, and not overlap. The third is a “badly drawn” type goppg configuration; the remaining three figures are “good” representations of the goppg configuration.

vertices, there are a total of $3^6=729$ cases. However, many will be the same after rotation or reflection. To count the configurations up to symmetry, associate each configuration with a number: For each 6-tuple of the letters $o$ , $g$ , $p$ , replace by $g\to 0$ , $p\to 1$ , $o\to 2$ , and read in base 3. Find this number for each rotation and reflection, and choose the configuration with the least number as representative A Python program computed there are 165 cases, 75 being Euler cycles. The number of cases up to symmetry can also be computed using Burnside’s Lemma. [4], [5], which says that for a group $G$ acting on a set $X$ , the number of orbits of the action is $|X/G|=\frac{1}{|G|}{\sum }_{g\in G}|X^g|$ , where $X^g=$ set of elements of $X$ unchanged by $g\in G$ . In our case, $G=D_3=\{1,r,r^2,f_1,f_2,f_3\}$ , the dihedral group of symmetries of a regular triangle, where $f_i$ are reflections and $r$ is a rotation. An example of an orbit is given in Figure 2. Rotations fix $3^2$ elements, with configurations of the form $c_1{c}_2{c}_1{c}_2{c}_2{c}_1$ , and reflections fix $3^4$ elements, for example $c_1{c}_2{c}_1{c}_4{c}_4{c}_6$ for the reflections in the vertical axis. Substitution in the formula gives that the total number of configurations is 165

Drawing the configurations

Where possible, I wanted to draw representative cases satisfying the following rules:

• All arcs must lie on circles, with centers at a choice from three points, $p_1,p_2,p_3$ as in Figure 3
• Arcs that are not joined must not overlap, as in Figure 3

Specifying the radii of the arcs between pairs of joined vertices almost completely determines what happens at a vertex, as for example in Figure 4. In this example, the circles have centers distance 1 apart, and the arc from vertex ${\nu }_i$ to ${\nu }_j$ has radius $1+\frac{1}{4}{ϵ}_{ij}$ . These are given in a symmetric matrix. How the arc radii determine vertex type is given in an example in Table 1. A python program worked through the possible cases.

Up to $D_3$ symmetry, 8 cases can not be drawn according to these rules. Up to octahedral symmetry, these are the cases in row, column, 2, 6 and 4, 1 in Figure 7.

Figure 5 illustrates the relationship between the three circles configuration and the octahedron. Imagine the figure on a sphere. The seven finite regions are stretched round the sphere, and then straightened to obtain

Paths on Three Circles

• Underlying circles radius $R=2$ . Arc from ${\nu }_i$ to ${\nu }_j$ has radius $R+\alpha {ϵ}_{ij}$ , where $\alpha =0.5$ .
• E.g., as in this matrix, $E=({ϵ}_{ij})-$ means ${\nu }_i$ and ${\nu }_j$ are not joined.

Figure 4: In most cases, the arcs radii determine vertex type.

Table 1: How ${ϵ}_{2j}$ determines the vertex type of $v_2$ .

the octahedron. The exterior area of the initial face becomes the 8th face of the octahdron. To go from the octahrdon back to the circle figure, we have eight choices of which face will become the exterior region. The group of octahedral symmetries has order 48, so a typical configuration has orbit size 48. For example, Figure 6 shows 8 elements of the same octahedral orbit, obtained from the path in the figure on the right in Figure 5. These correspond to the 8 faces of the octaherdon. The other elements are obtained by applying the $D_3$ symmetries. All cases up to octahedral symmetry are shown in Figure 7, created with a python program writing tikzpicture output. These figures, similar at first glance, are all different; the beauty is in having a complete set up to octahedral symmetry, interesting to compare and contrast. They have been arranged in an ordering of number of components and number of crossings. The count can also be verified by Burnside’s lemma, bearing in mind that the non tetrahedral symmetries in the octahedral group will exchange ‘p’ and ‘g’ type vertices, so the count is not the same as the number of inequivalent vertex colourings.

These methods can be applied to other designs, as for example for 4 circles, as shown in Figure 8, where I have also modified ‘p’, ‘g’ type vertices.

Figure 5: Transformation from the circle configuration to an octahedron

Verrill

Figure 6: 8 of the 48 elements in the octahedral orbit of the poggg configuration.

Figure 7: Complete set of representative paths around the three circles up to octahedral symmetry.

References

[1] Angela Lord. Creative form drawing, Workbooks 1 and 2, ISBN: 978-1-907359-98-9 and 978-1-907359-70-5. [2] Bernard Meehan, The Book of Kells, Oct 2012, ISBN: 0500238944 [3] https://www.gaelicmatters.com/celtic-knot-symbols.#gallery[pageGallery]/2/ [4] W. Burnside. “Theory of Groups of Finite Order”, Cambridge University Pres. 2012. §119. https://web.math.rochester.edu/people/faculty/doug/otherpapers/burnside1911.pdf [5] Art of Problem Solving online. Burnside’s Lemma. https://artofproblemsolving.com/wiki/index.php/Burnside%27s_Lemma [6] Oscar Levin. Discrete Mathematics An Open Introduction http://discrete.openmathbooks.org/dmoi2/sec_paths.

Figure 8: Variations on four circle configurations.