A Study of Definition, Motivation and Properties of Combinatorial Curvature

A graph is only a combinatorial structure over a finite set communicating a binary connection, so graph theory is normally viewed as one of branches in combinatorics or discrete mathematics. Be that as it may, individuals dependably draw a photo comprising of \points" and \lines" on paper to display a graph. Albeit such a photo isn't fundamental to talk about a unique structure of a graph, it fortifies the instinct of geometors and lead them to attemption of setting up a sort of geometry managing pictures or states of graphs. Topological graph theory is one of the results of such attemption. One of fundamental subjects in topological graph theory is \embeddings of graphs on surfaces". Any nonplanar graph can't be drawn on the plane or the circle so any two edges don't cross each other, so we require another phase to put graphs without edge intersections. The torus, the projective plane, the Klein container et cetera are such stages and topological graph scholars are occupied with what occurs with those graphs set on them. Graphs can be spoken to in various routes: by arrangements of edges, by incidence relations, by adjacency matrices, and by other comparable structures. These portrayals are appropriate to computer algorithms. Truly, be that as it may, graphs are geometric items. The vertices are points in space and the edges are line fragments joining select pairs of these points. For instance, the points might be the vertices and edges of a polyhedron. Or then again they might be the convergences and movement courses of a guide. All the more as of late, they can speak to computer processors and correspondence channels. These photos of graphs are outwardly engaging and can pass on basic data effortlessly. They reflect graph theory's youth in "the ghettos of topology." The study 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 graplis that serve as the lower bound. Finally, I will explore different graph operations that maintain everywhere positive combinatorial curvature and the potential for

Topological graph theory manages approaches to speak to the geometric realization of graphs, regularly; this includes beginning with a graph and delineating it on different kinds of planning phases: 3-space, the plane, surfaces, books, and so on. The field utilizes topology to think about graphs. For instance, planar graphs have numerous extraordinary properties. The field likewise utilizes graphs to contemplate topology. For instance, the graph theoretic verifications of the Jordan Curve Theorem, or the theory of voltage graphs delineating fanned covers of surfaces, provide a naturally engaging and effortlessly checked combinatorial elucidation of unpretentious topological ideas.

Just as the Euler characteristic was a combinatorial invariant of a graph, we can define a combinatorial invariant of a vertex in a graph. 1. Definition: Let G be a graph andWe define the combinatorial curvature of v as where the sum is taken over all faces / incident with To gain a better understanding of combinatorial curvature, consider the following example. 2. Example: Let G be the graph in Figure 4.1. Recalling that the outside of the graph is a face, we can calculate the combinatorial curvature for each of the labeled vertices: Note thatandborder the outside face and therefore have a 1/10 term in their calculation. We can also note that for vertices such aswith degree at most 2, the combinatorial curvature will always be positive. For example, iffor a vertexthen

In Example 2, 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. LetNote that the angle of a regular n-gon is(see Figure 4.2) andis incident tofaces so the sum of angles incident tois Then for all 1. if and only if the sum of the angles incident tois 2. if and only if the sum of angles incident tois less thanand 3. if and only if the sum of angles incident tois greater than In the previous section on topological graph theory, we defined that for a graph G with

a two-cell embedding on a surface S, the Euler characteristic of S is

of combinatorial curvat ure and this definition of the Euler characteristic of a surface.

Pwof. Note that Now the sum of the degrees of all vertices in G counts the edges twice, so Additionally, a face f is incident tovertices. Therefore, for each face appearstimes in the sum, so Putting these pieces together, we have as desired.

While our discussion up to this point has been 011 combinatorial curvatures, for the remainder of this thesis we will focus on graphs with positive combinatorial curvature at every vertex. A graph G

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 isfor all faces f. Then for a vertex u of degree 1, degree 2, and for a vertexof degree 3, For vertices of higher degree, we can see that adding a vertex changes the combinatorial curvature by and since 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 adjacent to faces of size 3, 3, and k will have combinatorial curvature In 2001, Higuchi showed that negative combinatorial curvature is bounded above by —1/1806. 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 two cell embedding on a surface S. SinceG must embed in a surface with 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 ant prism graph, and the projective planar analogs. 1. Definition: Define the prism graphas follows: whereand. Thencan be imagined as the skeleton of an n- sided prism. Figure 4.3a is an octagonal prism, For any vertex ,

Generally, for the prism graphon 2n vertices, for all Thus, prisms are an infinite family of grahs with everywhere positive combinatorial curvature. 2. Definition: Define the ant prism graphas follows: whereand. An n-sided antiprism is a polyhedron composed of two parallel copies of an n-sided polygon, connected by a band of alternating triangles. Thencan be imagined as the skeleton of an n-sided antiprism. Figure 4.3b is an octagonal antiprism,For any vertex As with the prism graphs, we find that for the antiprismin 2n vertices, for all Thus antiprisms are another infinite family of graphs with everywhere positive combinatorial curvature. 3. Definition: Define the projective wheel graphas follows: For and for where.

We can view a projective wheel graph on 2k vertices as shown in Figure 4.4a. Where the two edges with arrows are the same edge. We will note that each vertex v in this graph has 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 4.4b. Again the two edges with the arrows are the same edge and every vertex in this graph has 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.

In this study, 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. The open problem regarding the largest connected Positive Combinatorial Curvature (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.

A. Georgakopoulos (2009). Infinite Hamilton cycles in squares of locally finite graphs, Adv. Math, pp. 670–705.

Euler tours in locally finite graphs, Electronic. J. Comb, #R40. Alec Radford, Luke Metz, and Soumith Chintala (2015). Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv:1511.06434. Alec Radford, Luke Metz, and Soumith Chintala (2015). Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv:1511.06434. C. Thomassen and A. Vella (2009). Graph-like continua and Menger‘s theorem, Combinatorica. C. Thomassen and A. Vella (2009). Graph-like continua and Menger‘s theorem, Combinatorica. E. Berger & H. Bruhn (2011). Eulerian edge sets in locally finite graphs, Combinatorica, 21–38. H. Bruhn & A. Georgakopoulos (2008), Bases and closures under infinite sums, preprint. H. Bruhn and M. Stein (2007). On end degrees and infinite circuits in locally finite graphs, Combinatorica, pp. 269–291. H. Bruhn, R. Diestel, and J. Pott (2011), Dual trees must share their ends, preprint . Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio (2014). Generative adversarial nets. pp. 2672–2680.

Research Scholar of OPJS University Churu Rajasthan