Search for: All records

Abstract Riemann surfaces are among the simplest and most basic geometric objects. They appear as key players in many branches of physics, mathematics, and other sciences. Despite their widespread significance, how to compute distances between pairs of points on compact Riemann surfaces is surprisingly unknown, unless the surface is a sphere or a torus. This is because on higher-genus surfaces, the distance formula involves an infimum over infinitely many terms, so it cannot be evaluated in practice. Here we derive a computable distance formula for a broad class of Riemann surfaces. The formula reduces the infimum to a minimum over an explicit set consisting of finitely many terms. We also develop a distance computation algorithm, which cannot be expressed as a formula, but which is more computationally efficient on surfaces with high genuses. We illustrate both the formula and the algorithm in application to generalized Bolza surfaces, which are a particular class of highly symmetric compact Riemann surfaces of any genus greater than 1. 

Abstract Curvature is a fundamental geometric characteristic of smooth spaces. In recent years different notions of curvature have been developed for combinatorial discrete objects such as graphs. However, the connections between such discrete notions of curvature and their smooth counterparts remain lurking and moot. In particular, it is not rigorously known if any notion of graph curvature converges to any traditional notion of curvature of smooth space. Here we prove that in proper settings the Ollivier–Ricci curvature of random geometric graphs in Riemannian manifolds converges to the Ricci curvature of the manifold. This is the first rigorous result linking curvature of random graphs to curvature of smooth spaces. Our results hold for different notions of graph distances, including the rescaled shortest path distance, and for different graph densities. Here the scaling of the average degree, as a function of the graph size, can range from nearly logarithmic to nearly linear. 

Abstract Dynamic processes on networks, be it information transfer in the Internet, contagious spreading in a social network, or neural signaling, take place along shortest or nearly shortest paths. Computing shortest paths is a straightforward task when the network of interest is fully known, and there are a plethora of computational algorithms for this purpose. Unfortunately, our maps of most large networks are substantially incomplete due to either the highly dynamic nature of networks, or high cost of network measurements, or both, rendering traditional path finding methods inefficient. We find that shortest paths in large real networks, such as the network of protein-protein interactions and the Internet at the autonomous system level, are not random but are organized according to latent-geometric rules. If nodes of these networks are mapped to points in latent hyperbolic spaces, shortest paths in them align along geodesic curves connecting endpoint nodes. We find that this alignment is sufficiently strong to allow for the identification of shortest path nodes even in the case of substantially incomplete networks, where numbers of missing links exceed those of observable links. We demonstrate the utility of latent-geometric path finding in problems of cellular pathway reconstruction and communication security. 

Diameter is one of the most basic properties of a geometric object, while Riemann surfaces are one of the most basic geometric objects. Surprisingly, the diameter of compact Riemann surfaces is known exactly only for the sphere and the torus. For higher genuses, only very general but loose upper and lower bounds are available. The problem of calculating the diameter exactly has been intractable since there is no simple expression for the distance between a pair of points on a high-genus surface. Here we prove that the diameters of a class of simple Riemann surfaces known as generalized Bolza surfaces of any genus greater than 1 are equal to the radii of their fundamental polygons. This is the first exact result for the diameter of a compact hyperbolic manifold. 

Abstract Consider a set of n vertices, where each vertex has a location in $$\mathbb{R}^d$$ that is sampled uniformly from the unit cube in $$\mathbb{R}^d$$ , and a weight associated to it. Construct a random graph by placing edges independently for each vertex pair with a probability that is a function of the distance between the locations and the vertex weights. Under appropriate integrability assumptions on the edge probabilities that imply sparseness of the model, after appropriately blowing up the locations, we prove that the local limit of this random graph sequence is the (countably) infinite random graph on $$\mathbb{R}^d$$ with vertex locations given by a homogeneous Poisson point process, having weights which are independent and identically distributed copies of limiting vertex weights. Our set-up covers many sparse geometric random graph models from the literature, including geometric inhomogeneous random graphs (GIRGs), hyperbolic random graphs, continuum scale-free percolation, and weight-dependent random connection models. We prove that the limiting degree distribution is mixed Poisson and the typical degree sequence is uniformly integrable, and we obtain convergence results on various measures of clustering in our graphs as a consequence of local convergence. Finally, as a byproduct of our argument, we prove a doubly logarithmic lower bound on typical distances in this general setting.