• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 2
  • Tagged with
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Synthetic notions of curvature and applications in graph theory

Shiping, Liu 11 January 2013 (has links) (PDF)
The interaction between the study of geometric and analytic aspects of Riemannian manifolds and that of graphs is a very amazing subject. The study of synthetic curvature notions on graphs adds new contributions to this topic. In this thesis, we mainly study two kinds of synthetic curvature notions: the Ollivier-Ricci cuvature on locally finite graphs and the combinatorial curvature on infinite semiplanar graphs. In the first part, we study the Ollivier-Ricci curvature. As known in Riemannian geometry, a lower Ricci curvature bound prevents geodesics from diverging too fast on average. We translate this Riemannian idea into a combinatorial setting using the Olliver-Ricci curvature notion. Note that on a graph, the analogue of geodesics starting in different directions, but eventually approaching each other again, would be a triangle. We derive lower and upper Ollivier-Ricci curvature bounds on graphs in terms of number of triangles, which is sharp for instance for complete graphs. We then describe the relation between Ollivier-Ricci curvature and the local clustering coefficient, which is an important concept in network analysis introduced by Watts-Strogatz. Furthermore, positive lower boundedness of Ollivier-Ricci curvature for neighboring vertices imply the existence of at least one triangle. It turns out that the existence of triangles can also improve Lin-Yau\'s curvature dimension inequality on graphs and then produce an implication from Ollivier-Ricci curvature lower boundedness to the curvature dimension inequality. The existence of triangles prevents a graph from being bipartite. A finite graph is bipartite if and only if its largest eigenvalue equals 2. Therefore it is natural that Ollivier-Ricci curvature is closely related to the largest eigenvalue estimates. We combine Ollivier-Ricci curvature notion with the neighborhood graph method developed by Bauer-Jost to study the spectrum estimates of a finite graph. We can always obtain nontrivial estimates on a non-bipartite graph even if its curvature is nonpositive. This answers one of Ollivier\'s open problem in the finite graph setting. In the second part of this thesis, we study systematically infinite semiplanar graphs with nonnegative combinatorial curvature. Unlike the previous Gauss-Bonnet formula approach, we explore an Alexandrov approach based on the observation that the nonnegative combinatorial curvature on a semiplanar graph is equivalent to nonnegative Alexandrov curvature on the surface obtained by replacing each face by a regular polygon of side length one with the same facial degree and gluing the polygons along common edges. Applying Cheeger-Gromoll splitting theorem on the surface, we give a metric classification of infinite semiplanar graphs with nonnegative curvature. We also construct the graphs embedded into the projective plane minus one point. Those constructions answer a question proposed by Chen. We further prove the volume doubling property and Poincare inequality which make the running of Nash-Moser iteration possible. We in particular explore the volume growth behavior on Archimedean tilings on a plane and prove that they satisfy a weak version of relative volume comparison with constant 1. With the above two basic inequalities in hand, we study the geometric function theory of infinite semiplanar graphs with nonnegative curvature. We obtain the Liouville type theorem for positive harmonic functions, the parabolicity. We also prove a dimension estimate for polynomial growth harmonic functions, which is an extension of the solution of Colding-Minicozzi of a conjecture of Yau in Riemannian geometry.
2

Synthetic notions of curvature and applications in graph theory

Shiping, Liu 20 December 2012 (has links)
The interaction between the study of geometric and analytic aspects of Riemannian manifolds and that of graphs is a very amazing subject. The study of synthetic curvature notions on graphs adds new contributions to this topic. In this thesis, we mainly study two kinds of synthetic curvature notions: the Ollivier-Ricci cuvature on locally finite graphs and the combinatorial curvature on infinite semiplanar graphs. In the first part, we study the Ollivier-Ricci curvature. As known in Riemannian geometry, a lower Ricci curvature bound prevents geodesics from diverging too fast on average. We translate this Riemannian idea into a combinatorial setting using the Olliver-Ricci curvature notion. Note that on a graph, the analogue of geodesics starting in different directions, but eventually approaching each other again, would be a triangle. We derive lower and upper Ollivier-Ricci curvature bounds on graphs in terms of number of triangles, which is sharp for instance for complete graphs. We then describe the relation between Ollivier-Ricci curvature and the local clustering coefficient, which is an important concept in network analysis introduced by Watts-Strogatz. Furthermore, positive lower boundedness of Ollivier-Ricci curvature for neighboring vertices imply the existence of at least one triangle. It turns out that the existence of triangles can also improve Lin-Yau\''s curvature dimension inequality on graphs and then produce an implication from Ollivier-Ricci curvature lower boundedness to the curvature dimension inequality. The existence of triangles prevents a graph from being bipartite. A finite graph is bipartite if and only if its largest eigenvalue equals 2. Therefore it is natural that Ollivier-Ricci curvature is closely related to the largest eigenvalue estimates. We combine Ollivier-Ricci curvature notion with the neighborhood graph method developed by Bauer-Jost to study the spectrum estimates of a finite graph. We can always obtain nontrivial estimates on a non-bipartite graph even if its curvature is nonpositive. This answers one of Ollivier\''s open problem in the finite graph setting. In the second part of this thesis, we study systematically infinite semiplanar graphs with nonnegative combinatorial curvature. Unlike the previous Gauss-Bonnet formula approach, we explore an Alexandrov approach based on the observation that the nonnegative combinatorial curvature on a semiplanar graph is equivalent to nonnegative Alexandrov curvature on the surface obtained by replacing each face by a regular polygon of side length one with the same facial degree and gluing the polygons along common edges. Applying Cheeger-Gromoll splitting theorem on the surface, we give a metric classification of infinite semiplanar graphs with nonnegative curvature. We also construct the graphs embedded into the projective plane minus one point. Those constructions answer a question proposed by Chen. We further prove the volume doubling property and Poincare inequality which make the running of Nash-Moser iteration possible. We in particular explore the volume growth behavior on Archimedean tilings on a plane and prove that they satisfy a weak version of relative volume comparison with constant 1. With the above two basic inequalities in hand, we study the geometric function theory of infinite semiplanar graphs with nonnegative curvature. We obtain the Liouville type theorem for positive harmonic functions, the parabolicity. We also prove a dimension estimate for polynomial growth harmonic functions, which is an extension of the solution of Colding-Minicozzi of a conjecture of Yau in Riemannian geometry.

Page generated in 0.0408 seconds