Topological Graph Theory and Graphs of Positive Combinatorial Curvature

Topological Graph Theory and Graphs of Positive Combinatorial Curvature A thesis submitted in partial fulfillment of the requirements for graduation with Honors in Mathematics. 2016 ii Contents Acknowledgements iv Abstract v List of Figures vi 1 Introduction 1 2 Topological Graph Theory 2.1 Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Graphs and Embeddings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Euler Characteristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 9 11 3 Combinatorial Curvature 3.1 Definitions and Motivations . . . . . . . . . . 3.2 Graphs of Positive Combinatorial Curvature . 3.3 Open Problem: Largest PCC graph . . . . . . 3.4 Face Vector Notation . . . . . . . . . . . . . . 3.5 Upper Bounds . . . . . . . . . . . . . . . . . 3.6 Lower Bounds: Gallery of Large PCC graphs 3.7 Graph Operations . . . . . . . . . . . . . . . 18 18 21 24 27 30 33 35 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Conclusion 42 References 44 Index 46 iii Acknowledgments iv Abstract This thesis considers the open problem in topological graph theory: What is the largest connected graph of minimum degree 3 which has everywhere positive combinatorial curvature but is not in one of the infinite families of graphs of positive combinatorial curvature? This problem involves the generalization of the notion of curvature (a geometric concept) to graphs (a combinatorial structure). The thesis present past progress on the upper and lower bounds for this problem as well as graph operations that may be used in the future for improving the lower bound. v List of Figures 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 Projection of the sphere onto the plane R2 with the north pole projected to a point at infinity [20]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Three common surfaces: the plane, a sphere, and a torus (from left to right). 4 The g-holed torus is the connected sum of g tori [19]. . . . . . . . . . . . . . 4 The gluing diagram for a torus and how it would fold into a torus. . . . . . 4 The projective plane, RP 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 The Klein bottle [22] and its gluing diagram. . . . . . . . . . . . . . . . . . 6 Construction of the Klein bottle by the connected sum of two projective planes. 7 The connected sum of a torus and a projective plane is the connected sum of three projective planes, which is equivalent to the connected sum of a Klein bottle K and a projective plane . . . . . . . . . . . . . . . . . . . . . . . . . 8 A simple graph G with four vertices and four edges. . . . . . . . . . . . . . 9 The complete graph K4 embedded in the plane. . . . . . . . . . . . . . . . . 11 Two different two-cell embeddings on the torus have the same Euler Characteristic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 The complete graph K7 embedded on a torus. . . . . . . . . . . . . . . . . . 15 The complete graph K6 embedded on a projective plane. . . . . . . . . . . . 15 A graph with vertices of positive, negative, and zero combinatorial curvature. 19 (n−2)π An n-gon has interior angle 2( (n−2)π . . . . . . . . . . . . . . . . . 20 2n ) = n Prism and antiprism graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Projective planar analogues to prism and antiprism graphs . . . . . . . . . 25 Transformation of G on the left to G0 on the right by adding parallel edge e0 , where the dashed lines denote the rest of the graph . . . . . . . . . . . . 26 Transformation of H on the left to H 0 on the right by adding loop e0 , where the dashed lines denote the rest of the graph . . . . . . . . . . . . . . . . . 27 The great rhombicosidodecahedron has 120 vertices and is a PCC graph. . . 33 A PCC graph on 138 vertices constructed by Reti, Bitay, and Koszotlany called the RBK graph, where the left and right sides of the figure are connected[14]. 34 A PCC graph on 208 vertices constructed by Nicholson and Sneddon, where the left and right sides of the figure are connected [14] . . . . . . . . . . . . 35 PCC graphs with more than 138 vertices, each labeled with the number of vertices [14] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Graph operation turning a vertex into a triangle. . . . . . . . . . . . . . . . 36 Transformation of an edge to a rectangle that turns the truncated dodecahedron into the great rhombicosidodecahedron. . . . . . . . . . . . . . . . . . 36 The dodecahedron [25] can be transformed into the truncated dodecahedron [24] by turning each vertex into a triangle. The truncated dodecahedron can be transformed into the rhombicosidodecahedron [23] by flattening each edge between triangles into a rectangle. . . . . . . . . . . . . . . . . . . . . . . . 37 A PCC graph on 120 vertices constructed from the RBK graph as a possible graph Reti et al. started with. . . . . . . . . . . . . . . . . . . . . . . . . . . 37 The great rhombicosidodecahedron with 12 added vertices to form a graph with 132 vertices (because of the limited perspective of this image, only 4 of the added vertices and 2 of the added edges are shown. . . . . . . . . . . . . 39 The PCC graphs on 192 (left) and 208 (right) vertices presented in [14]. . . 40 vi 30 31 32 The operation performed between the PCC graphs of 192 vertices and 208 vertices [14]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The PCC graphs on 192 (left) and 208 (right) vertices presented in [14] but with numbers imposed on the faces to show their sizes. . . . . . . . . . . . . Construction of a graph with 80 vertices from the truncated dodecahedron on 60 vertices using the edge thickening operation. . . . . . . . . . . . . . . vii 40 41 42 1 Introduction In this thesis we are looking at an open problem in topological graph theory which generalizes the notion of curvature (a geometric concept) to graphs (a combinatorial structure). To that end, we will look at topological surfaces and what it means to embed a graph on a surface. We will then define combinatorial curvature, examine properties of combinatorial curvature, and finally, consider progress on the open problem: What is the largest connected graph of minimum degree 3 which has everywhere positive combinatorial curvature but is not in one of the infinite families of graphs of positive combinatorial curvature? In the section following the introduction, we first introduce the topological concept of surfaces and the combinatorial concept of graphs. We then explore how graphs can embed in surfaces and an a combinatorial invariant of graph embeddings known as the Euler characteristic. The next section begins by defining combinatorial curvature and providing motivation for out interest in graphs with everywhere positive combinatorial curvature. We then present the infinite faimilies of graphs with everywhere positive combinatorial curvature. Next, the open problem is explained, followed by progress on the upper bound of the problem and then the lower bound of the problem. Then we explore operations on graphs of positive combinatorial curvature that might help improve the lower bound in future work. Finally, the conclusion provides a few closing remarks and thoughts for future work on problems relating to combinatorial curvature. 1 2 Topological Graph Theory This section will provide a brief introduction to topological graph theory to serve as motivation and background for the later discussion of the open problem regarding combinatorial curvature. First, I define surfaces and present a statement of the classification theorem of compact surfaces. Next, I introduce graphs and graph embeddings on surfaces. Finally, the Euler characteristic is defined and related to graph embeddings and the classification of surfaces. 2.1 Surfaces The following is a formal definition of surfaces. While this definition is included for the sake of completeness, this paper will focus more on an intuitive grasp of surfaces as the focus of the paper is graphs embedded on surfaces, rather than surfaces and their properties. Therefore a more approachable definition of a surface is provided in Definition 3 after the formal definition and two examples. Definition 1. A topological space is a set X along with a collection of subsets of X called open sets that satisfy the following: 1. The empty set and X itself are open, 2. Any union of a collection of open sets is open, and 3. The intersection of finitely many open sets is open. A Hausdorff space is a topological space X with the following property: for all points a, b ∈ X where a and b are distinct, there exists disjoint open sets Ua and Ub such that a ∈ Ua and b ∈ Ub . Let n be a positive integer. A Hausdorff space is said to be an n-dimensional manifold , or n-manifold, if every point has an open neighborhood homeomorphic to an open n-dimensional disk. A surface is a connected 2-manifold[13]; a compact surface is one for which every open cover has a finite subcover[8]. Example 2. A sphere and R2 are both 2-manifolds, or surfaces. Note that while both are connected, a sphere is bounded (and therefore compact) while R2 is not. We can also realize 2 Figure 1: Projection of the sphere onto the plane R2 with the north pole projected to a point at infinity [20]. the sphere as a plane with a point at infinity. Figure 1 shows how the sphere can project onto the plane with the north pole of the sphere projecting to a point at infinity. Definition 3. A surface is a topological space with the same local properties as the plane in Euclidean geometry (R2 )[12]. As Massey notes, “the topological concept of a surface is a mathematical abstraction of the familiar concept of a surface made of paper, sheet metal, plastic, or some other thin material... An intelligent bug crawling on a surface would not distinguish it from a plane if he had a limited range of visibility” [12, p. 1]. As Example 2 mentioned, the sphere and the plane are both surfaces. Another important surface is the torus. A torus is any surface that can be deformed to look like the exterior of a doughnut. Figure 2 shows, from left to right, a plane, a sphere, and a torus. Note that a torus can be deformed into a sphere with a handle on it as well and is also compact. We can use this to extend the idea of the torus: we call a sphere with g handles a g-holed torus, or a g-torus and denote it Tg (g ≥ 1). This g-torus can also be constructed as the connected sum of g tori, where the connected sum of two surfaces is taken by cutting a disc out of each surface and gluing the surfaces together along the boundary of the discs (Figure 3). The connected sum of surface S1 and surface S2 is denoted S1 #S2 . As it is difficult to draw surfaces such as the g-torus, we construct 2-dimensional ‘gluing diagrams’ of surfaces as well, where matching arrows along the edges of the surface are 3 Figure 2: Three common surfaces: the plane, a sphere, and a torus (from left to right). Figure 3: The g-holed torus is the connected sum of g tori [19]. identified and glued together with the heads and tails of the arrows corresponding to each other. Figure 4 shows the gluing diagram for the torus and how it would fold into the torus. Figure 4: The gluing diagram for a torus and how it would fold into a torus. We can note that for any closed path on the sphere, the plane, or the torus, if our imaginary bug were to walk around the path, her orientation would be preserved, that is, her left and right would remain her left and right. We call any closed path on a surface that preserves orientation, an orientation-preserving path and any surface where all closed paths are orientation-preserving is said to be orientable. On the other hand, we call any closed path on a surface that reverses orientation, i.e. swaps left and right, an orientationreversing path. Any surface with at least one orientation-reversing path is nonorientable [12]. We can obtain a compact, nonorientable surface called the projective plane, denoted RP 2 , with the gluing diagram shown in Figure 5a. Any closed path that goes off of the square of the gluing diagram and then back on through the matched edge is an orientationreversing path. This surface is much more difficult to visualize as it is not a subset of Euclidean 3-space [12]. Figure 5b provides one option for visualizing the projective plane. 4 (a) The gluing diagram for the projective plane. (b) An attempt at visualization of the projective plane [21]. Figure 5: The projective plane, RP 2 . We can construct other nonorientable surfaces by taking the connected sum of projective planes, as was done with tori. The surface obtained by taking the connected sum of n projective planes is denoted Nn (n ≥ 1). The following classification theorem is offered without proof as the proof for this theorem is lengthy and relatively technical. Proof for the theorem is available in Chapter 1 of [13] and Chapter 17 of [7]. Theorem 4 (Classification Theorem for Compact Surfaces). Any compact surface is homeomorphic to the sphere, the g-holed torus Tg (g ≥ 1), or the connected sum of n projective planes Nn (n ≥ 1). As noted previously, no proof of this theorem is offered in this paper, but this example will consider a compact surface called the Klein bottle and show that the Klein bottle is the connected sum of two projective planes. Example 5. Figure 6 shows the Klein bottle surface and its gluing diagram. Figure 7 shows the construction of the Klein bottle as the connected sum of two projective planes. Figure 7a shows the two projective planes and Figure 7b shows the removal of a disk from each projective plane. Figure 7c has the association of the boundaries of the disks and and then the gluing along half of that boundary in Figure 7d. Figures 7e and 7f show the transformation of the gluing diagram to resemble the gluing diagram of the projective plane which is shown in Figure 7g and matches the gluing diagram presented in Figure 6. Example 6. One might now ask what happens when we take the connected sum of a torus 5 Figure 6: The Klein bottle [22] and its gluing diagram. T1 and a projective plane N1 . Intrestingly, we can show the following: T1 #N1 = N1 #N1 #N1 . In Example 5 we showed that the connected sum of two projective plans is a Klein bottle K, so we can alternatively show that T1 #N1 = N1 #K. Figure 8 shows this transformation. In Figure 8a we begin with a torus and a projective plane and remove a disk from each, identifying the boundaries of the disks to get Figure 8b. We then make a cut along the dotted line in Figure 8c and then glue along the purple and green edges, resulting in Figure 8d. A new cut along the dashed line in Figure 8e and gluing along the black edge gives us Figure 8f. Now we can perform a cut through the center of our hexagon gluing diagram in Figure 8g and glue along the red edges in Figure 8h to get Figure 8i. Next we turn each of the black edges with double arrows into two edges, turning out hexagon gluing diagram into a octagon gluing diagram in Figure 8j. Finally, we cut across the center in Figure 8k to find a Klein bottle and a projective plane, each with a disk removed. While these examples are in no way a proof of the Classification Theorem of Compact Surfaces, they do present an intuition about how different compact surfaces can be formed from the connected sum of tori and projective planes. 6 N1 N1 (a) (b) (c) (d) (e) (f) K (g) Figure 7: Construction of the Klein bottle by the connected sum of two projective planes. 7 T1 N1 (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) N1 K (l) (k) Figure 8: The connected sum of a torus and a projective plane is the connected sum of three projective planes, which is equivalent to the connected sum of a Klein bottle K and a projective plane 8 2.2 Graphs and Embeddings Now that we have established the different surfaces, in this section we will consider graphs and their embeddings on surfaces. This thesis assume the reader has a basic understanding of graph theory but begin this section with a review of graph theory. A more extensive discussion of graph theory and clarification on any of these topics can be found in a basic graph theory text such as [5]. First we define a graph: Definition 7. A graph G = (V, E) is a set of vertices V and a set of edges E where elements of E are subsets of V of size 2. Example 8. Let G = (V, E) where V = {v1 , v2 , v3 , v4 } and E = {{v1 , v2 }, {v2 , v3 }, {v3 , v1 }, {v4 , v1 }}. A drawing of this graph is shown in Figure 9. v2 v1 v4 v3 Figure 9: A simple graph G with four vertices and four edges. Let e = (x, y) be an edge in a graph G, where x, y ∈ V (G). We call an edge e a loop if x = y [11]. Furthermore, if e1 and e2 are non-loop edges in a graph G, we say that e1 and e2 are parallel if they have the same end vertices. If a graph G contains parallel edges, it is said to have multiple edges. We define a simple graph as one with no multiple edges and no loops [11]. For a vertex v, d(v) refers to the degree of v, or the number of edges incident to v. We will call a graph finite if it has a finite number of vertices and a finite number of edges. We denote the set of vertices and the set of edges as V (G) and E(G), respectively. A cycle 9 C in a graph G is a sequence of vertices x0 , x1 , x2 , . . . , xn , x0 such that {xi , xi+1 } ∈ E(G) for 0 ≤ i ≤ n and x0 = xn+1 . The length of a cycle is the number of distinct vertices in the sequence. A graph that is connected and has no cycles is called a tree. The reader can confirm that for a graph G on n vertices to be connected but have no cycles, we must have |E(G)| = n − 1. With these notions of graphs in mind, we can discuss graph embeddings: Definition 9. We say that a graph G can be embedded on a surface S if there is a drawing on G on S such that edges intersect only at their endpoints. Given a graph G with an embedding on a surface S, we can define the faces with respect to the embedding. The space S \ G is a set of disconnected regions. Each of these regions we call a face with respect to the embedding [11, 5]. We denote the set of faces F (G). For each face f ∈ F (G), we can easily see that f must be bounded by some cycle in G. The size of the face |f | refers to the length of the cycle bounding f . Some embeddings have special properties with respect to the faces. Definition 10. A two-cell embedding is an embedding with the additional property that the closure of each face is a topological disk. A graph with an embedding on the plane is called a planar graph. Recall from Example 2 that a sphere is a plane with a point at infinity. Therefore, any finite graph that embeds in the plane can also embed in the sphere. Any finite planar graph will have an outside face that is not a topological disk, however, any finite graph that embeds on the sphere and has at least two faces can be two-cell embedded in the sphere. Note that the condition of at least two faces is necessary because if the graph has only an outside face, the closure of that face is the entire sphere, which is not a topological disk. Example 11. The simple graph on n vertices with all possible edges is called the complete graph, Kn . We will note that K4 can be embedded in the plane, and also the sphere as it is finite. Figure 10 shows a drawing of K4 that embeds in the plane or the sphere. On the sphere, this would be a two-cell embedding. We will note that there are 4 faces in this embedding, each of size 3. While there also exists cycles of length 4, these cycles do not bound faces in R2 \ K4 . 10 Figure 10: The complete graph K4 embedded in the plane. 2.3 Euler Characteristic Graphs embedded on surfaces display some combinatorial invariants. One such invariant is the Euler characteristic. Definition 12. Let G be a graph. We define the Euler characteristic of G, χ(G), as χ(G) = |F (G)| − |E(G)| + |V (G)|. Example 13. For an easy computational example, consider K4 , as in Figure 10. Since the exterior of the graph counts as a face, we have |F (K4 )| = 4, |E(K4 )| = 6, and |V (K4 )| = 4. Then χ(K4 ) = 4 − 6 + 4 = 2. In general, we can show that χ(G) = |F (G)| − |E(G)| + |V (G)| = 2 for all planar graphs. Theorem 14. If G is a connected, planar graph drawn with no edges crossing, then χ(G) = 2. Proof. We will prove the statement by inducting on the number of edges on a graph G. Let |V (G)| = n. The minimum number of edges in G, since G is connected, is n − 1. Therefore, consider the base case of |E(G)| = n − 1. We will recall that a graph on n vertices with n − 1 edges is a tree so G has only the exterior face. Then χ(G) = 1 − (n − 1) + n = 2. Now suppose G has k > n − 1 edges and m faces. Then G has at least one cycle. We can remove an edge e from that cycle, decreasing the number of edges by 1 and the number of faces by 1 as well. Let G0 be this graph with n vertices, k − 1 edges, and m − 1 faces. 11 Applying the induction hypothesis, we find 2 = χ(G0 ) = m − 1 − (k − 1) + n = m − k + n = χ(G). Thus every connected planar graph has Euler characteristic 2. An easy corollary is that any graph with a two-cell embedding on the sphere has Euler characteristic 2, since any such graph will also be planar. Remember that the plane does not have any finite graphs with a two-cell embedding, as the closure of the exterior face will never be a topological disk. However, if G1 and G2 are graphs that two-cell embed in a bounded surface S, we can show that G1 and G2 have the same Euler characteristic. A rigorous proof of this statement will not be included, but we can look at the idea behind the proof. The ideas for this proof come from a similarly non-rigorous “proof” in [1]. Consider G1 and G2 , two graphs that two-cell embed on a bounded surface S. Now we can place G1 and G2 on the surface S at the same time such that no vertices of G1 and G2 are on top of each other. We will construct a new graph H that “contains” both G1 and G2 and show that χ(G1 ) = χ(H) = χ(G2 ). For the purposes of this non-technical “proof,” we will assume that the edges of G1 intersect the edges of G2 a finite number of times. As [1] notes, there is a technical proof that justifies this statement, but this proof is time consuming and would take us far afield from our goal. Figure 11 is an example of how the “proof” would be performed with two graphs that embed on the torus. We build the graph H starting with G1 . Add to the vertices of G1 a new set of vertices corresponding to every place that the edges of G1 and G2 cross (Figure 11b). Call this graph H and note that the addition of each vertex splits an edge into 2. Therefore, if H has |V (H)| = |V (G1 )| + k, then |E(H)| = |E(G1 )| + k and |F (H)| = |F (G1 )| so χ(H) = χ(G1 ). Figure 11a has this operations performed for two graphs with two-cell embeddings on the torus. Next, add each vertex of G2 to H along with an edge that runs from that vertex to a vertex already in H. Choose each of these new edges to be a subset of an edge in G2 . For some vertices of G2 we may need to add chain of edges from a vertex already in H. Since each added vertex also adds a new edge, we now have that |V (H)| = |V (G1 )| + |V (G2 )| + k, 12 |E(H)| = |E(G1 )| + |E(G2 )| + k, and |F (H)| = |F (G1 )|. Therefore the Euler characteristic of H remains the same as the Euler characteristic of G1 . Figure 11c again shows this operation for the example graphs on the torus. Finally, we add the remaining pieces of the edges from G2 , noticing that each such added edge piece increases |E(H)| by 1 and thereby increases |F (H)| by 1. This too leaves the Euler characteristic unchanged so we end with χ(G1 ) = χ(H). The same graph H can be constructed from the graph G2 while leaving the Euler characteristic unchanged so χ(G1 ) = χ(H) = χ(G2 ), as desired. Thus we have shown that two graphs that two-cell embed on a bounded surface have the same Euler characteristic. Figure 11d finishes the construction of the graph H for our graphs embedded on the torus. This allows us to define an Euler characteristic for a surfaces: Definition 15. Let S be a surface and G be any graph with a two-cell embedding on S. We define the Euler characteristic of S as χ(S) = |F (G)| − |E(G)| + |V (G)|. Example 16. Considering Figure 12, we can see that there are 7 vertices, 21 edges, and 14 faces. Therefore, χ(T1 ) = 7 − 14 + 21 = 0. Similarly, looking at Figure 13, we have 6 vertices, 15 edges and 10 faces for χ(N1 ) = 6 − 15 + 10 = 1. Now we can prove the following theorem, which links Euler characteristics of graphs with two-cell embeddings and the Classification Theorem of Compact Surfaces. Theorem 17. For a two-cell embedding of a graph G on a sphere, χ(G) = 2. For a two-cell embedding of a graph G on Tg , χ(G) = 2 − 2g. For a two-cell embedding of a graph G on Nn , χ(G) = 2 − n. To prove this theorem, we need the following lemma from [13]: Lemma 18. Let S and T be compact surfaces. The Euler characteristic of S, T , and their 13 (a) (b) (c) (d) Figure 11: Two different two-cell embeddings on the torus have the same Euler Characteristic. 14 v7 v6 v5 v4 v3 v2 v1 Figure 12: The complete graph K7 embedded on a torus. v3 v4 v2 v1 v5 v6 Figure 13: The complete graph K6 embedded on a projective plane. connected sum, S#T , are related by the formula χ(S#T ) = χ(S) + χ(T ) − 2. Proof. Let G1 and G2 be graphs that two-cell embed on S and T , respectively. Choose a face f1 ∈ F (G1 ) and a face f2 ∈ F (G2 ). Suppose, without loss of generality, that |f1 | = |f2 | + k, where k is a non-negative integer. Then add k vertices to G2 along the cycle bounding f2 . Recall that this will preserve the Euler characteristic. Now to form the connected sum S#T , 15 remove f1 from G1 and f2 from G2 and glue along the boundaries of the faces, matching the vertices. The graph that results from this gluing H has a two-cell embedding on S#T . Additionally, we have |V (H)| = |V (G1 )| + |V (G2 )| − |f1 |, |E(H)| = |E(G1 )| + |E(G2 )| − |f1 |, and |F (H)| = |F (G1 )| + |F (G2 )| − 2. Thus χ(S#T ) = |F (H)| − |E(H)| + |V (H)| = |F (G1 )| + |F (G2 )| − 2 − (|E(G1 )| + |E(G2 )| − |f1 |) + |V (G1 )| + |V (G2 )| − |f1 | = (|F (G1 )| − |E(G1 )| + |V (G1 )|) + (|F (G2 )| − |E(G2 )| + |V (G2 )|) − 2 = χ(S) + χ(T ) − 2. With this lemma we can prove the original theorem. Proof. We have already shown the first part, that a graph G with a two-cell embedding on a sphere has a χ(G) = 2. For the second part, suppose G is a graph with a two-cell embedding on the g-holed torus, Tg . Recall that Tg is the connected sum of g tori, so χ(G) = χ(Tg ) = χ(T1 #T1 # · · · #T1 ) = χ(T1 ) + χ(T1 ) + · · · + χ(T1 ) − 2(g − 1). From Example 16 we have that χ(T1 ) = 0 so χ(G) = −2(g − 1) = 2 − 2g. For the third part of the theorem, suppose G is a graph with a two-cell embedding on the connected sum of n projective planes. Similarly, using χ(N1 ) = 1 from Example 16, we have χ(G) = χ(Nn ) = χ(N1 #N1 # · · · #N1 ) = χ(N1 )+χ(N1 )+· · ·+χ(N1 )−2(n−1) = n−2n+2 = 2−n. Theorem 17 gives the Euler characteristic of graphs with two-cell embeddings on surfaces, which is equivalent to the Euler characteristic of the surfaces themselves. Therefore, this theorem can be lets us identify when two compact surfaces are the same: two compact, 16 connected surfaces are the same if and only if they are both orientable or both nonorientable and they have the same Euler characteristic. 17 3 Combinatorial Curvature This section of the paper will introduce an open problem in topological graph theory. It will begin with a definition of combinatorial curvature, properties of combinatorial curvature, and some motivation for interest in graphs of positive combinatorial curvature. We will then consider infinite families of graphs of positive combinatorial curvature. Next, we present the open problem regarding combinatorial curvature which asks: What is the largest connected graph of minimum degree 3 which has everywhere positive combinatorial curvature but is not in one of the infinite families? The following sections will present progress on this problem by first showing proofs of the upper bound and then constructions of large graphs that serve as the lower bound. Finally, I will explore different graph operations that maintain everywhere positive combinatorial curvature and the potential for these operations to help in the construction of a larger lower bound graph. 3.1 Definitions and Motivations Just as the Euler characteristic was a combinatorial invariant of a graph, we can define a combinatorial invariant of a vertex in a graph. Definition 19. Let G be a graph and v ∈ V (G). We define the combinatorial curvature of v as φ(v) = 1 − d(v) X 1 + , 2 |f | f ∼v where the sum is taken over all faces f incident with v To gain a better understanding of combinatorial curvature, consider the following example. Example 20. Let G be the graph in Figure 14. Recalling that the outside of the graph is a face, we can calculate the combinatorial curvature for each of the labeled vertices: φ(v1 ) = 1 − 6/2 + (1/3 + 1/3 + 1/3 + 1/3 + 1/3 + 1/3) = 0 φ(v2 ) = 1 − 4/2 + (1/3 + 1/3 + 1/6 + 1/10) = −1/15 φ(v3 ) = 1 − 2/2 + (1/6 + 1/10) = 4/15. 18 Note that v2 and v3 border the outside face and therefore have a 1/10 term in their calculation. We can also note that for vertices such as v3 with degree at most 2, the combinatorial curvature will always be positive. For example, if d(v) = 2 for a vertex v, then φ(v) = 1 − 2/2 + X 1 X 1 = > 0. |f | |f | f ∼v f ∼v v1 v2 v3 Figure 14: A graph with vertices of positive, negative, and zero combinatorial curvature. In Example 20, one vertex had postitive curvature, another had negative curvature, and a third had zero curvature. We can give condition for zero, positive, and negative combinatorial curvature. Let G be a graph with minimum degree 2. Consider each face of size n of G as a regular n-gon with side length 1. Let v ∈ V (G). Note that the angle of a regular n-gon is (n−2)π n =π− 2π n (see Figure 15) and v is incident to d(v) faces so the sum of angles incident to v is X f ∼v 2π π− |f |    X 1 d(v) = d(v)π − 2π = d(v)π − 2π φ(v) − 1 + = 2π − 2πφ(v). |f | 2 f ∼v Then for all v ∈ G, 1. φ(v) = 0 if and only if the sum of the angles incident to v is 2π, 2. φ(v) > 0 if and only if the sum of angles incident to v is less than 2π, and 3. φ(v) < 0 if and only if the sum of angles incident to v is greater than 2π. In the previous section on topological graph theory, we defined that for a graph G with 19 2π n (n−2)π 2n Figure 15: An n-gon has interior angle 2( (n−2)π 2n ) = (n−2)π . n a two-cell embedding on a surface S, the Euler characteristic of S is χ(S) = |V (G)| − |E(G)| + |F (G)|. The following theorem follows easily from the definition of combinatorial curvature and this definition of the Euler characteristic of a surface. Theorem 21. Let G be a graph with a two-cell embedding on a surface S. Then X φ(v) = χ(S). v∈V (G) Proof. Note that  X v∈V (G) φ(v) = X v∈V (G)    X X X X X 1  d(v) 1  1 − d(v) +  = 1− + . 2 |f | 2 |f | f ∼v v∈V (G) v∈V (G) v∈V (G) f ∼v Now the sum of the degrees of all vertices in G counts the edges twice, so X d(v) 1 X 1 = d(v) = (2|E(G)|) = |E(G)|. 2 2 2 v∈V (G) v∈V (G) Additionally, a face f is incident to |f | vertices. Therefore, for each face f ∈ F (G), 20 1 |f |  X appears |f | times in the sum v∈V (G)  X 1  , so |f | f ∼v  X v∈V (G)  X 1 X 1  = |f | = |F (G)|. |f | |f | f ∼v f ∈F (G) Putting these pieces together, we have X φ(v) = |V (G)| − |E(G)| + |F (G)| = χ(S), v∈V (G) as desired. 3.2 Graphs of Positive Combinatorial Curvature While our discussion up to this point has been on combinatorial curvature, for the remainder of this thesis we will focus on graphs with positive combinatorial curvature at every vertex. A graph G with φ(v) > 0 for all v ∈ V (G) is said to have everywhere positive combinatorial curvature. The condition of positive combinatorial curvature at a vertex is interesting for a few reasons. First, we will note that combinatorial curvature is bounded above for simple graphs. In a simple graph, the size of a face is |f | ≥ 3 for all faces f . Then for a vertex u of degree 1, φ(u) = 1 − 1/2 + 1/|f | = 1/2 + 1/|f | ≤ 1/2 + 1/3 = 5/6 where f is the face incident to v. For a vertex v of degree 2, φ(v) = 1 − 2/2 + 1/|f1 | + 1/|f2 | = 1/|f1 | + 1/|f2 | ≤ 1/3 + 1/3 = 2/3 and for a vertex w of degree 3, φ(w) = 1 − 3/2 + 1/|f1 | + 1/|f2 | + 1/|f3 | ≤ −1/2 + 3(1/3) = 1/2. For vertices of higher degree, we can see that adding a vertex changes the combinatorial 21 curvature by −1/2 + 1/|f | and since |f | ≥ 3, this is always negative. Thus combinatorial curvature at a vertex is bounded above by 5/6 and in particular, bounded above by 1/2 for vertices of degree at least 3. On the other hand, positive combinatorial curvature is only bounded below by zero as a vertex v adjacent to faces of size 3, 3, and k will have combinatorial curvature φ(v) = 1 − 3/2 + 1/3 + 1/3 + 1/k = 1/k. In 2001, Higuchi showed that negative combinatorial curvature is bounded above by −1/1806 [10]. We can also see that negative combinatorial curvature is not bounded below, as we can make a vertex incident to sufficiently many faces of large size to guarantee an arbitrarily large negative combinatorial curvature. Suppose G is a graph with everywhere positive combinatorial curvature and a twoP φ(v) = χ(S), G must embed in a surface with cell embedding on a surface S. Since v∈V (G) positive Euler characteristic. We showed in the previous section on topological graph theory that the only two compact surfaces with positive Euler characteristic are the sphere and the projective plane. There are four important infinite families of everywhere positive combinatorial curvature that embed on either the sphere or the projective plane: the prism graph, the antiprism graph, and the projective planar analogs. Definition 22. Define the prism graph An as follows: V (An ) = {u1 , ..., un , v1 , ..., vn } E(An ) = {{ui , ui+1 }, {vi , vi+1 }, {ui , vi }|1 ≤ i ≤ n} where u1 = un+1 and v1 = vn+1 [17]. Then An can be imagined as the skeleton of an n-sided prism. Figure 16a is an octagonal prism, A8 . For any vertex v ∈ A8 , φ(v) = 1 − 3/2 + (1/4 + 1/4 + 1/8) = 1/8. 22 Generally, for the prism graph An on 2n vertices, for all v ∈ An , φ(v) = 1 − 3/2 + (1/4 + 1/4 + 1/n) = 1/n. Thus, prisms are an infinite family of grahs with everywhere positive combinatoral curvature [17]. Definition 23. Define the antiprism graph Bn as follows: V (Bn ) = {u1 , ..., un , v1 , ..., vn } E(Bn ) = {{ui , ui+1 }, {vi , vi+1 }, {ui , vi }, {ui , vi+1 } | 1 ≤ i ≤ n} where u1 = un+1 and v1 = vn+1 [17]. An n-sided antiprism is a polyhedron composed of two parallel copies of an n-sided polygon, connected by a band of alternating triangles. Then Bn can be imagined as the skeleton of an n-sided antiprism. Figure 16b is an octagonal antiprism, B8 . For any vertex v ∈ B8 , φ(v) = 1 − 4/2 + (1/3 + 1/3 + 1/3 + 1/8) = 1/8. As with the prism graphs, we find that for the antiprism Bn in 2n vertices, for all v ∈ B(n), φ(v) = 1/n. Thus antiprisms are another infinite family of graphs with everywhere positive combinatorial curvature [17]. Definition 24. Define the projective wheel graph Pn as follows: V (Pn ) = {v1 , v2 ..., vn }. For n = 2k + 1, E(P2k+1 ) = {{vi , vi+1 }, {vi , vk+i }, {vi , vk+i+1 } | 1 ≤ i ≤ k + 1} and for n = 2k, E(P2k ) = {{vi , vi+1 }, {vi , vk+i } | 1 ≤ i ≤ k} where vi = vn+i [17]. 23 u3 u3 u4 v4 u5 u2 u2 v3 u4 v2 v5 v1 v6 v7 u1 v4 v3 v5 v8 v1 v6 u5 u1 v2 v7 v8 u8 u8 u6 u7 u6 (a) An ocatgonal prism u7 (b) An octagonal antiprism Figure 16: Prism and antiprism graphs We can view a projective wheel graph on 2k vertices as shown in Figure 17a, where the two edges with arrows are the same edge. We will note that each vertex v in this graph has φ(v) = 1 − 3/2 + (1/4 + 1/4 + 1/(2k)) = 1/(2k). This is similar to the prism graph that can be embedded in the sphere. We can view the projective wheel graph on 2k + 1 vertices as shown in Figure 17b. Again the two edges with the arrows are the same edge and every vertex in this graph has φ(v) = 1 − 4/2 + (1/3 + 1/3 + 1/3 + 1/(2k + 1)) = 1/(2k + 1). This is similar to the antiprism graph which can be embedded in the plane. Interestingly, the projective planar analogue of a prism must have an even number of vertices and the projective planar analogue of an antiprism must have an odd number of vertices. 3.3 Open Problem: Largest PCC graph From the previous results in this paper, we have that positive combinatorial curvature is not bounded below, but that the sum of the combinatorial curvature of all of the vertices in a graph embedded on a surface S is equal to the finite Euler characteristic of the surface S. 24 x1 x2 x3 x4 x4 x5 x6 x1 x1 x4 (a) Projective planar analogue to prism graph x2 x5 x3 x6 x4 x7 x1 (b) Projective planar analogue to antiprism graph Figure 17: Projective planar analogues to prism and antiprism graphs This prompts the question of whether a graph can have infinitely many vertices of positive combinatorial curvature. In 2001, Higuchi [10] was the first to begin discussing this question when he published a paper with results that used combinatorial curvature and showed that negative combinatorial curvature at a vertex is bounded above by −1/1806. At the end of the paper, Higuchi also conjectured that any planar graph G with everywhere positive combinatorial curvature would have finitely many vertices. From the previous section, we know that there are planar graphs of everywhere positive combinatorial curvature of size 2n for all positive integers n, so Higuchi’s conjecture is not entirely correct. In 2007, Devos and Mohar [4] adapted Higuchi’s original conjecture and showed that a graph G with minimum degree 3 and everywhere positive combinatorial curvature is either a prism, an antiprism, the projective planar analogue of one of these, or |V (G)| < 3444. This forms the basis of our definition of PCC graphs. Definition 25. Any simple graph with minimum degree 3 that is not a prism, antiprism, or the projective planar analogues that has everywhere positive combinatorial curvature is a PCC graph [14]. The condition of minimum degree 3 is necessary, as we can make a graph arbitrarily large by adding vertices of degree one or two while maintaining everywhere positive combinatorial curvature. We will also recall that prisms, antiprisms, and the projective planar analogues are infinite families of everywhere positive combinatorial curvature, so we can construct arbitrarily large graphs of everywhere positive combinatorial curvature if we include graphs 25 from these families. We will also show that the assumption of simplicity in PCC graphs is not significant by showing that multiple edges and loops do not change the combinatorial curvature of a graph. For the situation of multiple edges, consider a graph G and a vertex v ∈ V (G). Let e ∈ E(G) be any non-loop edge incident to v. Form G0 by adding an edge e0 to G that is parallel to e, as in Figure 18. Let dG (v) be the degree of v in G, dG0 (v) be the degree of v in G0 , φG (v) be the combinatorial curvature of v in G, and φG0 (v) be the combinatorial curvature of v in G0 . Note that the only additional face incident to v in G0 is the face with two edges formed by the parallel edges, e and e0 , and dG0 (v) = dG (v) + 1. Let f ∼ v denote G the faces incident to v in G and similarly let f ∼0 v denote the faces incident to v in G0 . G Then φG0 (v) = 1 − dG (v) + 1 X 1 dG0 (v) X 1 + = 1− + + 1/2 = φG (v) − 1/2 + 1/2 = φG (v). 2 |f | 2 |f | f ∼v f ∼v G0 G Thus adding and removing multiple edges does not change the combinatorial curvature of a vertex, and does not change the number of vertices in a graph. v e ⇒ e v e0 Figure 18: Transformation of G on the left to G0 on the right by adding parallel edge e0 , where the dashed lines denote the rest of the graph For the situation of loops, consider a graph H and a vertex v ∈ V (H). Form H 0 by adding an edge e0 to H that is a loop at v, as in Figure 19. Note that the only additional face incident to v in H 0 is the one of size 1 and dH 0 (v) = dH (v) + 2. Then we have φH 0 (v) = 1 − dH 0 (v) X 1 dH (v) + 2 X 1 + =1− + + 1 = φH (v) − 1 + 1 = φH (v). 2 |f | 2 |f | f ∼v f ∼v H0 H 26 Thus adding and removing loops does not change the combinatorial curvature of a vertex or the number of vertices in the graph. This means we can focus on simple graphs of everywhere positive combinatorial curvature. v ⇒ e0 v Figure 19: Transformation of H on the left to H 0 on the right by adding loop e0 , where the dashed lines denote the rest of the graph This leads us to the open problem: Problem 26. What is the largest connected graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism, an antiprism, or a projective planar analogue? That is, what is the largest PCC graph? In the context of the problem, “largest” refers the the greatest number of vertices. In 2008, Zhang improved on Devos and Mohar’s upper bound and showed that |V (G)| < 580 if G is a PCC graph [17]. The rhombicosidodecahedron (Figure 20) has 120 vertices and is a PCC graph. Reti, Bitay, and Kosztolanyi found a PCC graph with 138 vertices[15], and then in 2011, Nicholson and Sneddon found a PCC graph with 208 vertices [14]. Solutions to, or progress on, the problem will involve the construction of large PCC graphs or improvements on the upper bound on the number of vertices in a PCC graph. 3.4 Face Vector Notation The following theorem allows us to begin classifying vertices in PCC graphs: Theorem 27. Let G be a PCC graph. Then for all v ∈ V (G), 3 ≤ d(v) ≤ 5. Proof. Let v ∈ V (G). By definition of G, d(v) ≥ 3. To see that d(v) ≤ 5, note that since G is simple, each face is of size at least 3. Then for all f ∈ F (G), 27 1 |f | ≤ 13 . Also because G is simple, we have that v is incident to d(v) faces. Now d(v) X 1 d(v) 0 < φ(v) = 1 − + ≤1− + d(v) 2 |f | 2 f ∼v It follows that d(v) 6   1 . 3 < 1 so d(v) ≤ 5, as desired. Geometrically, this also makes sense. We have said that a vertex v has positive combinatorial curvature if and only if the sum of angles incident to v is less than 2π, where each face of size n is considered as a regular n-gon with side length 1. The smallest angle in a face of size n is in a triangle, where the angle is π/3 or 60◦ . If we try to squeeze six or more regular n-gons around a vertex, since n ≥ 3, the sum of the angles is greater than 6(π/3) = 2π. Thus each vertex can have at most 5 faces incident to it, and therefore degree at most 5. For ease of notation, we define the face vector [17]: Definition 28. Let G be a graph and v ∈ V (G) be a vertex. Further suppose that f1 , f2 , ..., fd(v) are the faces of G incident to v, where |f1 | ≤ |f2 | ≤ ... ≤ |fd(v) |. The face vector of G at v is f (v) = (|f1 |, |f2 |, ..., |fd(v) |). The following lemma is a modification by Zhang [17] of a lemma proved by Chen [3] that classifies the face vectors and combinatorial curvature at vertices in a PCC graph based on the degree of the vertex: Lemma 29. If G is a positive curvature graph and v ∈ V (G), then the face vectors and curvatures for each of the cases are characterized into the following patterns: 1. For d(v) = 3, 28 f (v) (3, 3, k), k ≥ 3 (3, 4, k), k ≥ 4 (3, 5, k), k ≥ 5 (3, 6, k), k ≥ 6 (3, 7, k), 7 ≤ k ≤ 41 (3, 8, k), 8 ≤ k ≤ 23 (3, 9, k), 9 ≤ k ≤ 17 (3, 10, k), 10 ≤ k ≤ 14 (3, 11, k), 11 ≤ k ≤ 13 (4, 4, k), k ≥ 4 (4, 5, k), 5 ≤ k ≤ 19 (4, 6, k), 6 ≤ k ≤ 11 (4, 7, k), 7 ≤ k ≤ 9 (5, 5, k), 5 ≤ k ≤ 9 (5, 6, k), 6 ≤ k ≤ 7 2. For d(v) = 4, f (v) (3, 3, 3, k), k ≥ 3 (3, 3, 4, k), 4 ≤ k ≤ 11 (3, 3, 5, k), 5 ≤ k ≤ 7 (3, 4, 4, k), 4 ≤ k ≤ 5 φ(v) 1/6 + 1/k 1/12 + 1/k 1/30 + 1/k 1/k 1/k − 1/42 ≥ 1/1722 1/k − 1/24 ≥ 1/552 1/k − 1/18 ≥ 1/306 1/k − 1/15 ≥ 1/210 1/k − 5/66 ≥ 1/858 1/k 1/k − 1/20 ≥ 1/380 1/k − 1/12 ≥ 1/132 1/k − 3/28 ≥ 1/252 1/k − 1/10 ≥ 1/90 1/k − 2/15 ≥ 1/105 φ(v) 1/k 1/k − 1/12 ≥ 1/132 1/k − 2/15 ≥ 1/105 ≥ 1/30 3. For d(v) = 5, f (v) = (3, 3, 3, 3, k) with 3 ≤ k ≤ 5 and φ(v) ≥ 1/30. The proof of this lemma is largely enumerative so we will only do a few cases of the proof here. Consider the following example: suppose a vertex v in a graph G has degree 3 and the face vector of v is f (v) = (3, 3, k) where k ≥ 3 by the definition of the face vector. Now φ(v) = 1 − 3 + 1/3 + 1/3 + 1/k = 1/6 + 1/k. 2 Thus, φ(v) > 0 for all values of k if f (v) = (3, 3, k). We will note that k is the size of the largest face incident to v. We can also consider a vertex u with degree 4, f (u) = (3, 3, 4, k), and φ(u) > 0. Then the combinatorial curvature is φ(u) = 1 − 4/2 + 1/3 + 1/3 + 1/4 + 1/k = −1/12 + 1/k. Thus for φ(u) > 0, we must have 1/k > 1/12 so k ≤ 11. For all vertices u with face vector (3, 3, 4, k) and φ(u) > 0, φ(u) ≥ −1/12 + 1/11 = 1/132. 29 On the other hand, if a vertex w has degree 3 and f (w) = (5, 7, k), then φ(w) = 1 − 3/2 + (1/5 + 1/7 + 1/k) = 1/k − 11/70. However, we will recall that k ≥ 7, by convention in face vector notation, so 1/k ≤ 10/70 < 11/70 so a w cannot have positive combinatorial curvature. Also, for ease of notation, we will refer to the combinatorial curvature of a vertex v, φ(v), and the combinatorial curvature of the corresponding face vector, φ(|f1 |, |f2 |, ..., |fd(v) |), interchangably for the remainder of this paper. 3.5 Upper Bounds There are papers by Zhang [17], Chen et al. [3], and Devos et al. [4] which regard the finiteness of PCC graphs. Here, finiteness refers to a finite number of vertices. Each proves that a PCC graph must be finite. Interestingly both Chen et al. and Devos et al. find that for any PCC graph, |V (G)| < 3444. Zhang improves on the upper bound and finds |V (G)| < 580 if G is a PCC graph. Devos and Mohar’s approach is geometric, using that the if a graph G is embedded on a closed 2-manifold S, then S is a polygonal surface and the embedding is geodesic [4]. In this paper, we will focus on the result and proofs from [3] and [17]. Chen et al. prove the following, which is a strengthening of Higuchi’s original conjecture: Theorem 30. Let G be a graph embedded in a closed 2-manifold. Define the absolute total curvature of G as |φ(G)| = X |φ(v)|. v∈V (G) Then G has finite number of vertices of non-vanishing combinatorial curvature (φ(v) 6= 0) if and only if |φ(G)| < ∞. From this theorem, it follows easily that a PCC graph must be finite. Trivially, if G has a finite number of vertices of non-zero curvature, then the absolute total curvature of G is finite. To prove the converse, Chen et al. utilize the classification of vertices by face vectors and combinatorial curvature (see Lemma 29). Similarly, to prove the following theorem, 30 Zhang utilizes the classification of vertices by face vectors. Theorem 31. Let G be a finite graph embedded in a compact surface without boundary, and 3 ≤ d(x) < ∞ and φ(x) > 0 for all x ∈ V (G). a) If G is embedded in the projective plane with n ≥ 290 vertices, then G is isomorphic to the projective wheel graph on n vertices Pn . b) If G is embedded in the sphere with n ≥ 580 vertices, then G is isomorphic to either the prism graph on n vertices, An , or the antiprism graph on n vertices, Bn . Directly from Lemma 29 we have the following corollary: Corollary 32. If v is a vertex with φ(v) > 0 and k is the size of the largest face incident to v, then φ(v) ≥    1/1722, if 3 ≤ k ≤ 41;   1/k, if k > 41. Another consequence of Lemma 29 is the following lemma that is adapted from [3]: Lemma 33. Let f be a face in a graph G with |f | ≥ 42, φ(v) > 0 for all v ∈ G, and define P φ(v) ≥ 1. ∂f as the boundary of f . Then v∈V (∂f ) Proof. Let |f | = k. By Lemma 29, if v ∈ V (∂f ), then v must have one of the following face vectors: (3, 3, k), (3, 4, k), (3, 5, k), (3, 6, k), (4, 4, k), (3, 3, 3, k). Note that φ(v) ≥ 1/k for each vertex with a face vector of this form. Then X v∈V (∂f ) φ(v) ≥ X 1/k = k(1/k) = 1. v∈V (∂f ) Chen et al. then show that if there are two faces f1 and f2 with |f1 |, |f2 | ≥ 42, then ∂f1 and ∂f2 , the cycles that bound f1 and f2 , are disjoint cycles in G. I do not include the 31 details of that proof here but if we accept this lemma, an intuitive explanation of the proof of Theorem 30 by Chen et al. is as follows: For a contradiction, suppose there are infinitely many vertices of non-zero curvature. A vertex v with φ(v) < 0 is bounded above by φ(v) ≤ −1/1806 by Higuchi [10], so if a graph has finite absolute total curvature, then we must have finitely many vertices of negative curvature. Then there are infinitely many vertices of positive combinatorial curvature.We can find a vertex v1 such that 0 < φ(v1 ) < 1/1722. By Corollary 32, v1 is incident to a face f1 such that |f1 | ≥ 42. Since there are infinitely many vertices of positive combinatorial curvature, and |V (∂f1 )| < ∞, there must be a vertex v2 such that v2 6∈ V (∂f1 ) and 0 < φ(v2 ) < 1/1722. Again by Corollary 32, v2 is incident to a face f2 such that |f2 | ≥ 42. In this way, we can iteratively construct a sequence of faces {f1 , f2 , ...}. Note that |fi | ≥ 42 for i ∈ Z+ , so V (∂fi ) ∩ V (∂fj ) = ∅ for all i 6= j. Now applying Lemma 32, X |φ(v)| ≥ v∈G X v∈V ( ∞ S |φ(v)| = ∂fi ) ∞ X X i=1 v∈V (∂fi ) |φ(v)| ≥ ∞ X 1 = ∞. i=1 i=1 This contradicts the initial assumption that P |φ(v)| < ∞, so there must be finitely many v∈G vertices of non-zero curvature. A clear corollary of this is that if G is a planar graph, with φ(v) > 0 for all v ∈ G, then |V (G)| is finite, since φ(v) = |φ(v)| for all v ∈ G and we have P φ(v) = 2 for planar graphs. shown v∈V (G) Zhang proves part (b) of her theorem using the following lemma, which uses Chen et al.’s lemma regarding disjoint cycles: Lemma 34. Let G be a finite graph embedded in a sphere such that φ(x) > 0 for all x ∈ V (G). If |V (G)| ≥ 580, then all vertices of G are exactly on two disjoint cycles bounding two faces. Again accepting this lemma without proof and the fact that every vertex on these cycles has degree at most 3, we can sketch Zhang’s proof of part b of Theorem 31: Let G be a graph with |V (G)| ≥ 580 and φ(v) > 0 for all v ∈ V (G). Then all vertices are on two disjoint cycles C1 and C2 . Define G0 as the graph with vertex set V (G) and edge set E(G) − E(C1 ) − E(C2 ). Now G0 is bipartite graph with vertex sets C1 and C2 . Each vertex 32 in G was of degree at most 3, so in G0 , each vertex is of degree 1 or 2. Now Zhang asserts, any cycle in G0 must be a Hamilton cycle connecting all vertices of G0 and using all edges of G0 (I have yet to understand why this is true). Then |C1 | = |C2 | = n for some positive integer n, and G is the antiprism graph Bn . If there is no cycle in G0 , then all paths must be of length 1, or else we would have a vertex of negative combinatorial curvature. Then |C1 | = |C2 | = n for some positive integer n, and G is the prism graph An . 3.6 Lower Bounds: Gallery of Large PCC graphs One relatively easy large PCC graph is the skeleton of the great rhombicosidodecahedron which has 120 vertices (Figure 20). Each vertex of the great rhombicosidodecahedron has face vector (4, 6, 10) and combinatorial curvature φ(4, 6, 10) = 1 − 3/2 + 1/4 + 1/6 + 1/10 = 1/60. Figure 20: The great rhombicosidodecahedron has 120 vertices and is a PCC graph. In 2005, Reti, Bitay, and Koszotlany constructed a PCC graph on 138 vertices [15], improving on the previous lower bound of 120. The following table summarizes the the face vectors of the vertices used. Figure 21 depicts the graph. 33 P f (v) number of vertices φ(v) (4, 4, 19) 18 1/19 18/19 (3, 4, 4, 5) 24 1/30 4/5 (4, 5, 19) 96 1/380 24/95 Totals: 138 φ(v) 2 Figure 21: A PCC graph on 138 vertices constructed by Reti, Bitay, and Koszotlany called the RBK graph, where the left and right sides of the figure are connected[14]. In 2011, Nicholson and Sneddon constructed six larger PCC graphs [14]. They found graphs with 144, 168, 184, 192, and 208 vertices. To construct their largest graph on 208 vertices, they began by using vertices with face vector (3, 3, 4, 11). Nicholston et al. note that this is the smallest possible curvature of a vertex of degree 4 other than vertices with f (v) = (3, 3, 3, n) and φ(v) = 1/n. Vertices of the form (3, 3, 3, n) are the vertices in the antiprism. Using vertices with face vector (3, 3, 4, 11), Nicholson et al. note that vertices with face vector (3, 11, 13) would fit nicely and such vertices have combinatorial curvature 1/858. The only smaller curvatures on three vertices are φ(3, 7, 41) = 1/1722 and φ(4, 4, n) = 1/n. This leads to the graph described in the table below, as seen in Figure 22. P f (v) number of vertices φ(v) (3, 11, 13) 96 1/858 16/149 (3, 3, 4, 11) 40 1/132 10/33 (3, 11, 11) 64 1/66 32/33 (3, 3, 3, 13) 8 1/13 8/13 Totals: 208 34 φ(v) 2 Figure 22: A PCC graph on 208 vertices constructed by Nicholson and Sneddon, where the left and right sides of the figure are connected [14] Figure 23: PCC graphs with more than 138 vertices, each labeled with the number of vertices [14] 3.7 Graph Operations To construct the large PCC graph on 208 vertices, Nicholson and Sneddon created a sequence of graphs of increasing size, as seen in Figure 23. Graph operations, such as those implemented between the panels in Figure 23 that add vertices to PCC graphs and keep positive combinatorial curvature at each vertex, have the potential to assist in the construction of large PCC graphs. Looking at Platonic and Archimedian solids also provided ideas for graph operations, based on the transformation of different Platonic solids to Archimedian solids and Archimedian solids to other Archimedian solids. For example, the truncated dodecahedron, as its name suggests, is a truncated version 35 of the dodecahedron, which has faces of size 5 and vertices of (5, 5, 5). The truncated dodecahedron be created by “flattening” each of the 20 vertices of the dodecahedron into a triangle to give 60 vertices in the truncated dodecahedron. Figure 24 shows this operation on a single vertex. Recalling that any vertex of a graph with postive combinatorial curvature is of degree 3,4, or 5, we can extend this operation to flattening vertices of degree 3 to triangles, vertices of degree 4 to squares, and vertices of degree 5 to pentagons. Figure 24: Graph operation turning a vertex into a triangle. The transformation from the truncated dodecahedron to the great rhombicosidodecahedron is also a potential PCC preserving graph operation. In this transformation, an edge between two triangles becomes a rectangle and the triangles at either end become 4-cycles as well. Figure 25 shows this operation and how it can potentially add 2 vertices to a PCC graph. In the case of the transformation from the truncated dodecahedron to the great rhombicosidodecahedron, each vertex is essentially split into two vertices as every edge between two triangles becomes a rectangle, resulting in 120 vertices in the great rhombicosidodecahedron. Figure 26 shows the transformation from dodecahedron to truncated dodecahedron to great rhombicosidodecahedron. ⇒ Figure 25: Transformation of an edge to a rectangle that turns the truncated dodecahedron into the great rhombicosidodecahedron. 36 Figure 26: The dodecahedron [25] can be transformed into the truncated dodecahedron [24] by turning each vertex into a triangle. The truncated dodecahedron can be transformed into the rhombicosidodecahedron [23] by flattening each edge between triangles into a rectangle. Returning to the RBK graph (Figure 21), we will notice a “ladder” that moves throughout the graph. I hypothesize that the RBK graph began with a graph with 120 vertices with face vectors (4, 5, 16) and (3, 4, 4, 5). This could result in a graph summarized by the following table and seen in Figure 27. P f (v) number of vertices φ(v) (4, 5, 16) 96 1/80 96/80 (3, 4, 4, 5) 24 1/30 24/30 Totals: 120 φ(v) 2 Figure 27: A PCC graph on 120 vertices constructed from the RBK graph as a possible graph Reti et al. started with. The operation that Reti et al. seemed to have performed was adding two vertices and an edge connecting them to divide a face of size 4 into two faces of size 4. This operation was then performed multiple times, essentially cutting the rectangles into multiple rectangles. However, as this increases the size of the faces of size 16, this operation cannot be repeated 37 infinitely. Vertices with face vector (4, 5, k) have φ(4, 5, k) = 1 − 3/2 + 1/4 + 1/5 + 1/k = 1/k − 1/20 so we must have 5 ≤ k ≤ 19 for the vertex to have positive curvature. Thus the RBK graph can have the rectangle dividing operation performed at most 3 times in all of the rectangles adjacent to each 16-gon, which will make the 16-gon into a 19-gon. The table below summarizes the vertices of the RBK graph after the rectangle cutting operation was performed. P f (v) number of vertices φ(v) φ(v) (4, 4, 19) 18 1/19 18/19 (3, 4, 4, 5) 24 1/30 4/5 (4, 5, 19) 96 1/380 24/95 Totals: 138 2 Now consider this operation on the great rhombicosidodecahedron, which has 120 vertices each with face vector (4, 6, 10). We will note that for a vertex with face vector (4, 6, k), we find φ(4, 6, k) = 1 − 3/2 + 1/4 + 1/6 + 1/k = 1/k − 1/12 so 6 ≤ k ≤ 11 for the vertex to have positive curvature. Therefore, we can perform our rectangle splitting operation at most once in the set of rectangles adjacent to a face of size 10 on the great rhombicosidodecahedron. Figure 28 shows the operation performed. The resulting graph has face vectors (4, 4, 11) and (4, 6, 11), and is summarized in the following table. P f (v) number of vertices φ(v) φ(v) (4, 4, 11) 12 1/11 12/11 (4, 6, 11) 120 1/132 120/132 Totals: 132 2 Another graph operation is motivated by a transitions that occurs in the panel of 6 graphs in Nicholson and Sneddon [14]. They are able to add 16 vertices (Figure 29) by 38 Figure 28: The great rhombicosidodecahedron with 12 added vertices to form a graph with 132 vertices (because of the limited perspective of this image, only 4 of the added vertices and 2 of the added edges are shown. what seems to be a“thickening” of an edge that has triangles at either end that turns it into a 4-sided face and adds 4 triangles. Figure 30 zooms in on the area of change between the 192 vertex graph and the 208 vertex graph. Each such operation adds 4 vertices and is performed 4 times to get from the 192 vertex graph to the 208 vertex graph. Performing this operation takes the graph from one with 72 vertices of (3, 11, 11), 24 vertices of (3, 3, 4, 11) and 96 vertices of (3, 11, 12) to a graph with 8 vertices of (3, 3, 3, 13), 64 vertices of (3, 11, 11), 40 vertices of (3, 3, 4, 11) and 96 vertices of (3, 11, 13). To gain a better understanding of how the graph is changed by this operation, Figure 31 shows the same two graphs with 192 vertices and 208 vertices but this time, every face of size greater than 4 is labeled with its size. This allows us to see that the operation of “thickening” an edge and adding 4 triangles always occurs on an edge between two faces of size 11 but with the triangle ends towards a face of size 12. We will note that a face of size 12 becomes a face of size 13 when the operation is performed, as one of the additional triangles adds an extra vertex in the cycle that makes up the boundary of the 12-gon. The next question would be: what makes the operation stop? Why can we not repeat this operation indefinitely? First we will note that this “thickening” operation cannot be performed on the edge of the new 4-gon as this would result in a vertex of face vector (3, 3, 3, 4, 4). Such a face vector has combinatorial curvature φ(3, 3, 3, 4, 4) = 1 − 5/2 + 1/3 + 1/3 + 1/3 + 1/4 + 1/4 = 0, 39 Figure 29: The PCC graphs on 192 (left) and 208 (right) vertices presented in [14]. Figure 30: The operation performed between the PCC graphs of 192 vertices and 208 vertices [14]. so the graph would no longer be a PCC graph. Second, we will note that for a vertex with face vector (3, 11, k), the combinatorial curvature is φ(3, 11, k) = 1 − 3/2 + 1/3 + 1/11 + 1/k = 1/k − 5/66. For 1/k − 5/66 to be positive, we must k ≤ 13. We also find that there can be no vertices with face vector (3, 12, k), since φ(3, 12, k) = 1 − 3/2 + 1/3 + 1/12 + 1/k = 1/k − 1/12. These two limits begin limiting how large the faces adjacent to certain vertices can be. Finally, this operation always creates a vertex of (3, 3, 4, k) where k is the size of the face adjacent to the original edge that was “thickened.” The curvature of this vertex is φ(3, 3, 4, k) = 1 − 4/2 + 1/3 + 1/3 + 1/4 + 1/k = 1/k − 1/12, so k ≤ 11. With all of these considerations, if we were to try to find another edge in the graph that can be “thickened,” the edge cannot be around one of the faces of size 13 nor can it 40 Figure 31: The PCC graphs on 192 (left) and 208 (right) vertices presented in [14] but with numbers imposed on the faces to show their sizes. be such that the triangle ends of the “thickened” edge are in the cycle of the 13-gon. With these conditions, there are no edges in the graph with triangles at the ends that can be “thickened” in this manner, so the operation must stop. Just as the rectangle cutting operation was applied to the great rhombicosidodecahedron, we can apply the edge thickening operation to the truncated dodecahedron. The truncated dodecahedron is a good candidate for this graph because it has vertices of (3, 10, 10) so every edge is a potential candidate for this operation. The graph shown in Figure 32 has the operation performed 5 times, adding 20 vertices and resulting in a graph on 80 vertices. Each face of size greater than 4, including the outside face, is labeled with its size. The table below show the different types of vertices that appear in the graph, along with their combinatorial curvature. φ(v) f (v) number of vertices φ(v) (3, 3, 3, 11) 10 1/11 10/11 (3, 10, 11) 20 4/165 80/165 (3, 11, 11) 30 1/66 30/66 (3, 3, 4, 11) 20 1/132 20/132 Totals: 80 2 41 Figure 32: Construction of a graph with 80 vertices from the truncated dodecahedron on 60 vertices using the edge thickening operation. 4 Conclusion The open problem regarding the largest connected PCC graph remains unanswered, and the bounds on the largest PCC graph are still relatively wide. The largest known PCC graph has 208 vertices but the smallest upper bound on the number of vertices is 580. This leaves a lot of space to either lower the upper bound or construct large PCC graphs. In this paper, we considered this problem within the context of topological graph theory and graph embeddings. We attempted to contribute to the problem by considering what operations can be applied to PCC graphs that maintain the everywhere positive combinaotorial curvature but increase the number of vertices in the graph. Such operations may be very helpful in the construction of large PCC graphs, as they allow us make larger PCC graphs from known graphs. Future work on this topic could focus on identifying additional PCC preserving operations, especially focusing on when such operations can be applied to graphs, so as to increase the lower bound on the size of the largest PCC graph. There also still remains the question of whether the upper bound on the size of PCC graphs can be improved. Another interesting topic might be to consider graphs of everywhere negative combinatorial 42 curvature. What surfaces would these graphs embed on and what is the largest such graph? Higuchi [10] showed in 2001 that negative combinatorial curvature is bounded above by -1/1806, unlike positive combinatorial curvature which is not bounded below. However, is there a graph with combinatorial curvature that is everywhere -1/1806? These, and other questions, remain open regarding combinatorial curvature of graphs. 43 References [1] Adams, Colin C. 2001. The Knot Book an elementary Introduction to the Mathematical Theory of Knots. (1st print. ed.). New York: W.H. Freeman. [2] Barnette, D. 1991. Polyhedral embeddings in the projective plane. Israel Journal of Mathematics 73(1): 91-95. [3] Chen, Beifang, & Chen, Guantao. 2008. Gauss-Bonnet Formula, Finiteness Condition, and Characterizations of Graphs Embedded in Surfaces. Graphs and Combinatorics 24(3): 159-183. [4] Devos, Matt & Bojan Mohar. 2007. An analogue of the Descartes-Euler formula for infinite graphs and Higuchi’s conjecture. Transactions of the American Mathematical Society 359(7): 3287-3300. [5] Diestel, R. 2005. Graph theory (3rd ed., Graduate texts in mathematics; 173). Berlin: Springer. [6] Frechet, M., Fan, Ky, and Eves, Howard. 1967. Initiation to combinatorial topology. Boston: Prindle, Weber & Schmidt. [7] Fulton, W. 1995. Algebraic topology: A first course (Graduate texts in mathematics; 153). New York: Springer-Verlag. [8] Gordon, R. 2002. Real analysis: A first course (2nd ed.). Boston: Addison-Wesley. [9] Guichard, David. Combinatorics and Graph https://www.whitman.edu/mathematics/cgt online/. Theory. Available at [10] Higuchi, Y. 2001. Combinatorial curvature for planar graphs. Journal of Graph Theory 38(4): 220-229. [11] Lint, J., & Wilson, R. M. 2001. A course in combinatorics (2nd ed.). Cambridge, U.K.; New York: Cambridge University Press. [12] Massey, W. 1989. Algebraic topology, an introduction (8th corr. print. ed., Graduate texts in mathematics; 56). New York: Springer-Verlag. [13] Massey, W. 1991. A Basic Course in Algebraic Topology (8th corr. print. ed., Graduate texts in mathematics; 127). New York: Springer-Verlag. [14] Nicholson, Ruanui and Jamie Sneddon. 2011. New Graphs with Thinly Spread Positive Combinatorial Curvature. New Zealand Journal of Mathematics 41:39-43. [15] Reti, T., E. Bitay, and Zs. Kosztolany. 2005. On the polyhedral graphs with positive combinatorial curvature. Acta Polytechnica Hungarica 2(2): 19-37. [16] Sun, L., and X. Yu. 2004. Positively curved cubic plane graphs are finite. Journal of GraphTheory 47(4): 241–274. [17] Zhang, Lili. 2008. A result on combinatorial curvature for embedded graphs on a surface. Discrete Mathematics 308: 6588-6595 44 [18] http://www.openproblemgarden.org/category/topological graph theory [19] http://toroidalsnark.net/torsn.html [20] http://sites.middlebury.edu/fyse1229hunsicker/the-riemanns-sphere/ [21] https://en.wikipedia.org/wiki/Real projective plane [22] https://en.wikipedia.org/wiki/Klein bottle [23] https://en.wikipedia.org/wiki/Truncated icosidodecahedron [24] https://en.wikipedia.org/wiki/Truncated dodecahedron [25] https://en.wikipedia.org/wiki/Dodecahedron 45 Index simple, 9 two-cell embedding, 10 great rhombicosidodecahedron, 33 g-holed torus, 3, 5 n-dimensional manifold, 2 antiprism, 23 antiprisms, 23 Hausdorff space, 2 combinatorial curvature, 20 definition of, 18 combinatorial durvature bounds, 22 compact, 2 compact surface, 2–4 classification theorem, 5, 6, 13 complete graph, 10 connected sum, 3, 5, 6 connected sum of n projective planes, 5 cycle, 9, 10 Klein bottle, 5, 6 loop, 9, 26 multiple edges, 9, 26 nonorientable, 4 orientation-reversing path, 4 orientable, 4 orientation-preserving path, 4 PCC graph, 25, 27, 30 classification of vertices, 28 prism, 22, 23 projective plane, 4–6 projective wheel, 23 Euler characteristic, 11–13, 24 of a connected sum, 15 of a surface, 13, 20 of compact surface, 13 of the projective plane, 13 of the torus, 13 sphere, 5 surface, 2, 3 gluing diagram, 3 graph definition, 9 embedding, 10 finite, 9 planar, 10, 11 topological space, 2 torus, 3, 6 tree, 10 vertex degree, 9 46