Maximally Complete Maps on Orientable Surfaces

Year: 2024 Authors: Yanbing Gu; Connor Stewart; Ajmain Yamin

Core claim

A new disk-removal and boundary-identification method yields explicit, visualizable maximally complete maps on several small-genus orientable surfaces.

Topics

map coloring, orientable surfaces, visualizable constructions, physical models

Domains

topology, graph embeddings, surface genus, chromatic number, mathematical art, crochet models, diagrammatic design, physical modeling

Methods

planar diagrams, edge identifications, disk removal, boundary circle identification

Media

paper diagrams, crochet, polygonal models

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 2024 Conference Proceedings

Maximally Complete Maps on Orientable Surfaces

Yanbing Gu ${}^1$ , Connor Stewart ${}^2$ and Ajmain Yamin ${}^3$

${}^1$ Dartmouth College, Hanover, New Hampshire, USA; yanbing.gu.gr@dartmouth.edu ${}^2$ CUNY Graduate Center, New York, New York, USA; cstewart3@gradcenter.cuny.edu ${}^3$ CUNY Graduate Center, New York, New York, USA; ayamin@gradcenter.cuny.edu

Abstract

A map on an orientable surface $S_g$ of genus $g$ is maximally complete if any two faces share an edge and the number of faces is equal to $H(g)$ , the Heawood number of the surface. Ringel and Youngs’ work on the Map Color Theorem [11] has shown that such maps exist for all $g$ . However, explicit geometric descriptions of these maps are hard to visualize for $g\ge 3$ . In this paper, we construct several maximally complete maps on surfaces of small genus in a manner that is visualizable and can be used to produce physical models.

Introduction

A map is an embedding of a connected graph $X$ into a surface $S$ such that each component of $S\setminus X$ , called a face of the map, is homeomorphic to a disk. Since mid-nineteenth century, mathematicians have been interested in the number of colors required to color the faces of an arbitrary map on a given surface $S$ so that no two faces that share an edge have the same color. This number is called the chromatic number of $S$ and is denoted by $\chi (S)$ .

Interest in the chromatic number originated in 1852 from Francis Guthrie’s observation that four colors suffice to color a map of the counties of England, so that no two bordering countries share the same color [10]. The claim that every map on the sphere is four-colorable remained an open problem for more than a century until Kenneth Appel and Wolfgang Haken completed a computer-assisted proof in 1977, [1] and [2].

The analogous problem for surfaces of higher genus was considered by Percy John Heawood, who in 1890 proved that the chromatic number of $S_g$ is bounded above by the Heawood number $H(g)$ [8], defined below.

Table 1: Heawood numbers.

The Heawood conjecture asserts that $\chi (S_g)=H(g)$ [8]. To prove this conjecture, it suffices to show that for each $g$ , there exists a map on $S_g$ requiring $H(g)$ colors. The Heawood conjecture remained a long-standing open problem, until Gerhard Ringel and J. W. T. Youngs completed a proof in 1968, building on work of many others and utilizing the theory of current graphs [11].

Maps in which any two faces share an edge are called complete maps. Coloring a complete map requires as many colors as the number of faces in the map. Since $\chi (S_g)\le H(g)$ , no complete map on $S_g$ can contain more than $H(g)$ faces. Consequently, complete maps on $S_g$ with $H(g)$ faces are called maximally complete. Simple examples of maximally complete maps are the four-color tetrahedron map on the sphere and the seven-color maximally complete map on the torus, originally developed by Heawood [11].

Gu, Stewart, and Yamin

Maximally complete maps on surfaces of small genus were constructed in early works on the map coloring problem, and descriptions of maximally complete maps on orientable, genus $\le 6$ surfaces were given in an 1891 paper by Lothar Heffter [9]. Descriptions of maximally complete maps for other small genus surfaces appeared in the literature in following decades. However, the maps are usually described by means of an adjacency table, whose $i$ -th row lists the faces adjacent to the $i$ -th face in cyclic order with respect to the orientation of the surface. The adjacency table in Figure 1(a), which appeared in Heffter’s 1891 paper [9], describes a map on $S_3$ consisting of nine pairwise adjacent octagonal faces, labeled 1-9. The first row, for example, corresponds to face 1, and its entries indicate that faces 2, 3, 4, 5, 6, 7, 8, and 9 appear along the boundary of face 1 in that order with respect to the orientation.

(a) (b) Moira Chas’ crochet model of a maximally complete 12-color map on $S_6$ , based on Figure 9.

(b) Figure 1: (a) Adjacency table for a 9-color maximally complete map on $S_3$ by Heffter [9].

The disadvantage of adjacency tables is that it is difficult to use them to reconstruct maps that are easily visualizable or suitable for physical models. In contrast, easily visualizable planar diagrams for maximally complete maps on the sphere, torus, and genus 2 surface are readily found in the literature, for instance, in [6], [7], [11], and [13]. Moira Chas’ AMS Feature article on Crochet Topology ends by challenging readers to construct an easily visualizable maximally complete map on a genus 3 surface [5]. Multiple works in the Bridges conference proceedings in 2023, such as [3], [4], [12], and [14], also discussed various aspects of the 9-color, maximally complete map on the genus 3 surface, and complete maps on surfaces of higher genus.

The aim of this paper is therefore to fill a gap in the literature by providing several maximally complete maps on orientable surfaces of small genus in a manner that is easily visualizable and can be used to create physical models. These maps were constructed by a new method of removing disks from complete maps on surfaces of smaller genus and identifying boundary circles in pairs. We give diagrams of maximally complete maps on the orientable surfaces of genus 3, 4, 5, 6, 7, 10, and 12, and describe their constructions in detail. Using these diagrams, Moira Chas has made crochet models of several maximally complete maps, one of these models is shown in Figure 1(b).

Construction of Maximally Complete Maps

This section gives explicit constructions of maximally complete maps on orientable surfaces of small genus.

Planar Diagrams

Planar diagrams are a convenient way to represent maps on surfaces. In a planar diagram, a surface is represented by a polygon, or a polygon with holes, in which pairs of edges are identified according to a specified orientation.

Maximally Complete Maps on Orientable Surfaces

The planar diagram on the left of Figure 2(a) shows a square whose edges are identified in colored pairs. When the edges of the same color are identified so that the arrows overlap, the resulting surface is a sphere. Similarly, the planar diagram on the right of Figure 2(a) represents a torus. Two other planar diagrams for the torus, obtained from hexagons, are shown in Figure 2(b). A planar diagram for the genus 2 surface is shown in Figure 2(c). To visualize how the edge identifications of this planar diagram result in a genus 2 surface, imagine folding this diagram in half along a vertical line so that its left and right sides are identified, and so that its inner triangular holes are identified in pairs.

(a)

(b)

(c) Figure 2: Planar diagrams for the (a) sphere & torus, (b) torus, obtained from hexagons, (c) genus two surface, obtained from a polygon with holes. Within each planar diagram, edges of the same color are identified in the orientation indicated by the arrows.

Complete Maps on the Sphere, Torus, and Genus 2 Surface

In this section, we give planar diagrams for several complete maps on the sphere, the torus, and the genus 2 surface that will be used in the constructions of maximally complete maps on surfaces of higher genus.

The planar diagrams in Figure 3(a) show complete maps on the sphere of 2, 3, 3, and 4 colors, respectively. In each planar diagram, edges of the same color are identified according to the arrows. One can verify that in each map, any two faces share an edge. The planar diagrams in Figure 3(b) show complete maps on the torus of 6, 6, and 7 colors, respectively. The planar diagram in Figure 3(c) shows an 8-color maximally complete map on a genus 2 surface. It was obtained by physically inspecting Moira Chas’ crochet model [5] of Susan Goldstine’s 8-color map [6].

(a)

(c) Figure 3: Complete maps on (a) the sphere of 2, 3, 3, & 4 colors respectively, (b) the torus of 6, 6, & 7 colors respectively, (c) $S_2$ of 8-colors.

Gu, Stewart, and Yamin

Maximally Complete Maps on Genus 3, 4, 5, 6, 7, 10, and 12 Surfaces

We construct maximally complete maps on the surfaces of genus 3, 4, 5, 6, 7, 10, and 12 as follows:

1. Start with two complete maps on surfaces of smaller genus, called the base maps of the construction.
2. Remove the same number of disks from the two base maps, at vertices or along edges, in a way that the faces in each map remain pairwise adjacent and homeomorphic to disks.
3. Connect the two base maps by identifying the boundary circles of the removed disks in pairs. Identify each boundary circle in the first base map with one in the second, and choose the identifications so that each face in the first base map becomes adjacent to each face in the second.

The result of this procedure is a complete map whose number of faces is the combined number of faces in the two base maps and whose genus is the sum of the genera of the two base maps, plus the number of identified pairs of boundary circles, minus 1. In each construction, the number of faces in the two base maps and the number of identified pairs of boundary circles are chosen so that the resulting complete map on the new surface $S_g$ has $H(g)$ faces, and so is maximally complete.

In the diagrams below, the boundary circles in the base maps are numbered to show which pairs are identified. There are two boundary circles of each number, one black and the other divided into colored arcs. The colors show how the two boundary circles are identified, where the arc on the black circle that bounds a face of a given color is identified with the corresponding arc of the same color on the colored circle.

Genus 3 The diagram in Figure 4(a) shows a maximally complete 9-color map on the genus 3 surface. The base maps of this construction are the 7-color maximally complete map on the torus and a 2-color complete map on the sphere. The edge identifications in the base maps are the same as in Figure 3, and are thus omitted. The base maps are connected along the boundaries of three pairs of removed disks, in such a way that the pink and brown faces of the map on the sphere both become adjacent to all seven faces of the map on the torus.

(a)

Figure 4: (a) A maximally complete 9-color map on the genus 3 surface, obtained from a 7-color maximally complete map on the torus and a 2-color complete map on the sphere. (b) Moira Chas’ crochet model of the same maximally complete 9-color map on $S_3$ .

(b)

The diagram in Figure 5 shows another maximally complete 9-color map on the genus 3 surface. In this construction, the base maps are a 6-color complete map on the torus and a 3-color complete map on the sphere. The orange and yellow faces of the base map on the torus are drawn twice so that the colors on the third boundary circle can be clearly shown.

Genus 4 The diagrams in Figure 6 and 7 show maximally complete 10-color maps on the genus 4 surface. In Figure 6(a), the base maps are a 6-color complete map on the torus and the 4-color tetrahedron map on the sphere. In Figure 6(b), the base maps are the 7-color maximally complete map on the torus and a 3-color

Maximally Complete Maps on Orientable Surfaces

Figure 5: A maximally complete 9-color map on $S_3$ , obtained from a 6-color complete map on the torus and a 3-color complete map on the sphere.

complete map on the sphere, where the tan, blue, and red faces in the 7-color map on the torus are drawn twice so that the colored boundary circles can be clearly shown. In Figure 7, the base maps are an 8-color complete map on $S_2$ and a 2-color complete map on the sphere.

(a) (a) a 6-color complete map on the torus and the 4-color tetrahedron map on the sphere,

(b) Figure 6: A maximally complete 10-color map on $S_4$ , obtained from: (b) a 7-color maximally complete map on the torus and a 3-color complete map on the sphere.

Figure 7: A maximally complete 10-color map on $S_4$ , obtained from an 8-color maximally complete map on $S_2$ and a 2-color complete map on the sphere.

Gu, Stewart, and Yamin

Genus 5 The diagram in Figure 8 shows a maximally complete 11-color map on the genus 5 surface. The base maps are an 8-color maximally complete map on $S_2$ and a 3-color complete map on the sphere.

Figure 8: A maximally complete 11-color map on $S_5$ , obtained from an 8-color maximally complete map on $S_2$ and a 3-color complete map on the sphere.

Genus 6 The diagram in Figure 9 shows a maximally complete 12-color map on $S_6$ . The base maps are two 6-color complete maps on the torus. The faces in each base map have been drawn multiple times so that the colors of boundary circles are clearly shown. See Figure 1(b) for Moira Chas’ crochet version.

Figure 9: A maximally complete 12-color map on $S_6$ , obtained from two 6-color complete maps on $S_1$ .

Genus 7, 10, 12 Figure 10 shows a maximally complete 12-color map on a genus 7 surface. The base maps are two 6-color complete maps on tori, the faces on which have been drawn multiple times so the colors of boundary circles can be clearly shown. Figure 11 shows a maximally complete 14-color map on a genus 10 surface. The base maps are a 12-color maximally complete map on $S_6$ and a 2-color complete map on the sphere. Figure 12 shows a maximally complete 15-color map on a genus 12 surface. The base maps are a 12-color maximally complete map on $S_6$ and a 3-color complete map on the torus.

Maximally Complete Maps on Orientable Surfaces

Figure 10: A maximally complete 12-color map on $S_7$ , obtained from two 6-color complete maps on $S_1$ .

Figure 11: A maximally complete 14-color map on $S_{10}$ , obtained from a 12-color maximally complete map on $S_6$ and a 2-color complete map on the sphere.

Figure 12: A maximally complete 15-color map on $S_{12}$ , obtained from a 12-color maximally complete map on $S_6$ and a 3-color complete map on the torus.

Summary and Conclusions

We hope that the aforementioned method of constructing maximally complete maps, and the corresponding explicit diagrams for maximally complete maps on the genus $3,4,5,6,7,10$, and $12$ surfaces, may be of use to mathematical artists and others who may be interested in creating physical models or visual representations of maximally complete maps. Currently, constructing maximally complete maps by this method is an ad-hoc process. We wish to explore whether this method can be applied to find maximally complete maps for a larger class of surfaces, and to implement a computer program that can carry out the method automatically.

Acknowledgements

This work was conducted under the direction of Moira Chas during the 2019 Summer Workshop on Geometry and Topology at Stony Brook University. We are grateful for the financial support of the Stony Brook Mathematics Department, the Stony Brook RTG, and the Simons Center for Geometry and Physics. We would also like to thank Dennis Sullivan and Anthony Phillips for helpful discussions.

References

• [1] K. Appel and W. Haken. “Every Planar Map is Four Colorable. I. Discharging.” Illinois Journal of Mathematics, vol. 21, 1977, pp. 429–490.
• [2] K. Appel, W. Haken, and J. Koch. “Every Planar Map is Four Colorable. II. Reducibility.” Illinois Journal of Mathematics, vol. 21, 1977, pp. 491–567.
• [3] E. Baker and E. Torrence. “Fabric Models of Maximal Complete Maps on a Three-Holed Torus.” Proceedings of Bridges: Mathematics, Art, Music, Architecture, Culture, 2023, pp. 385–388.
• [4] S. Benzoni-Gavage. “The Rulpidon and 9-Color Maps.” Proceedings of Bridges: Mathematics, Art, Music, Architecture, Culture, 2023, pp. 553–558.
• [5] M. Chas. Crochet Topology. https://www.ams.org/publicoutreach/feature-column/fc-2018-05.
• [6] S. Goldstine. “Capturing Eight-Color Double-Torus Maps.” Bridges Conference Proceedings, 2014, pp. 377–380.
• [7] S. Goldstine. “Eight Heptagons: The Double Torus Revisited.” Proceedings of Bridges: Mathematics, Art, Music, Architecture, Education, Culture, 2020, pp. 413–416.
• [8] P. J. Heawood. “Map Colour Theorem.” Quarterly Journal of Mathematics, vol. 24, 1890, pp. 332–338.
• [9] L. Heffter. “Uber das Problem der Nachbargebiete.” Math. Ann., vol. 38, 1891, pp. 477–508.
• [10] G. Ringel. Map Color Theorem, 1st ed. Grundlehren der mathematischen Wissenschaften, Springer-Verlag, Heidelberg, 1974.
• [11] G. Ringel and J. W. T. Youngs. “Solution of the Heawood Map-Coloring Problem.” Proceedings of the National Academy of Sciences, vol. 60, no. 2, 1968, pp. 438–445.
• [12] C. H. Séquin. “Easy-to-Understand Visualization Models of Complete Maps.” Proceedings of Bridges: Mathematics, Art, Music, Architecture, Culture, 2023, pp. 187–194.
• [13] H. Tietze. Famous Problems of Mathematics, 2nd ed. Graylock Press, New York, 1965.
• [14] E. Torrence. “How to Build an Origami Nine-Color Map on a Genus-Three Torus.” Proceedings of Bridges: Mathematics, Art, Music, Architecture, Culture, 2023, pp. 389–392.