It is shown that there exist graphons that interpolate between Riemannian manifolds and weighted geometric graphs, and a monotonicity inequality is established which reveals an implicit relationship between numerous combinatorial parameters and geometric quantities on graphons.
Abstract
We show that there exist graphons that interpolate between Riemannian manifolds and weighted geometric graphs. Specifically, the graph-to-manifold approximation used in manifold learning can be regarded as the composition of a graph-to-graphon convergence and a graphon-to-manifold convergence in a certain sense. Furthermore, we establish a monotonicity inequality which reveals an implicit relationship between numerous combinatorial parameters and geometric quantities on graphons. Using this inequality, we find relations among conductance, maxcut problem, capacity, and packing radius, as well as their limiting behaviors under graph-to-graphon and graphon-to-manifold convergences; some of these relations are novel even for simple graphs and closed manifolds.
The findings illustrate that geometric insights grounded in hyperbolic geometry can offer powerful tools for understanding, embedding, and visualizing complex graph structures.
†. SalouaNaama, Kave Salamatian, M. Crovella· 0 citations
Topological graph theory studies graphs in relation to the surfaces on which they can be drawn. This review presents the main classical ideas of the field in a clear and connected framework. It begins with graph embeddings, Euler’s formula, and the basic principles of planar graphs. It then discusses important classica...
Ghadeer Khudhair Obayes, Karrar Khudhair Obayes· Asian journal of mathematics...· 0 citations
This work introduces a principled extension of Ollivier's Ricci curvature to complex-weighted graphs, which encompasses directed graphs as a special case and establishes fundamental theoretical properties of this new notion, including relations to the magnetic Laplacian and combinatorial upper and lower bounds that rel...
Yu Tian, Eleanor P. Wiesler, Melanie Weber· 0 citations
This work compares ball-and weighted graphs and gives a complete comparison in the one-dimensional case, and shows that the minimal dimension for ball graphs can at most be one larger than the minimal dimension for weighted graphs (weighted dimension), but also that the weighted dimension can exceed the ball dimension...
The main objective of this paper is to develop Krein-Milman-type theorems and Ulam-type stability results for graphs. To establish these results, we introduce several meaningful definitions of vertex-weighted convex graphs inspired by the concept of sequential convexity. We also present a close relationship between the...
Angshuman R. Goswami· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
