14 papers · ranked by Valyu relevance
Teddy Mishura
The space of L p graphons, symmetric measurable functions w : [0, 1]2 → R with finite p-norm, features heavily in the study of sparse graph limit theory. We show that the triangular cut operator Mχ acting on this space is not continuous with respect to the cut norm. This is achieved by showing that as n → ∞, the norm…
Cédric Simal, Julien Petit, Timoteo Carletti
We define an analogue of the shortest-path distance for graphons. The proposed method is rooted on the extension to graphons of Varadhan's formula, a result that links the solution of the heat equation on a Riemannian manifold to its geodesic distance. The resulting metric is integer-valued, and for step graphons…
Jacob W. Cooper, Tomáš Kaiser, Daniel Kráľ, Jonathan A. Noel
Graphons are analytic objects representing limits of convergent sequences of graphs. Lov´asz and Szegedy conjectured that every finitely forcible graphon, i.e. any graphon determined by finitely many graph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely…
Daniel Glasscock
Large graphs are ubiquitous in mathematics, and describing their structure is an important goal of modern combinatorics. One way to study large, finite objects is to pass from sequences of larger and larger such objects to ideal limiting objects. Done properly, properties of the limiting objects reflect properties of…
Dávid Kunszenti-Kovács, László Lovász, Balázs Szegedy
We study a metric on the set of finite graphs in which two graphs are considered to be similar if they have similar bounded dimensional "factors". We show that limits of convergent graph sequences in this metric can be represented by symmetric Borel measures on [0, 1]2 . This leads to a generalization of dense graph…
Kihun Nam
We study the variation of exchangeable graph-valued process Γ and its graph limit. We used a constructive method using localization technique. Our method provides a specific estimation of variation for exchangeable graph-valued process Γ and its graph limit for different types of metric. As a result, we extend the…
Balázs Szegedy
In this paper we describe a triple correspondence between graph limits, information theory and group theory. We put forward a new graph limit concept called log-convergence that is closely connected to dense graph limits but its main applications are in the study of sparse graph sequences. We present an information…
Gábor Elek
Hyperfiniteness or amenability of measurable equivalence relations and group actions has been studied for almost fifty years. Recently, unexpected applications of hyperfiniteness were found in computer science in the context of testability of graph properties. In this paper we propose a unified approach to…
Garrison Koch, Nathan Shank
The Roman Dominating number is a widely studied variant of the dominating number on graphs. Given a graph G = (V, E), the dominating number of a graph is the minimum size of a vertex set, V ′ ⊆ V , so that every vertex in the graph is either in V ′ or is adjacent to a vertex in V ′ . A Roman Dominating function of G is…
Christian Borgs, Jennifer Chayes, Henry Cohn, Yufei Zhao
We introduce and develop a theory of limits for sequences of sparse graphs based on Lp graphons, which generalizes both the existing L∞ theory of dense graph limits and its extension by Bollob´as and Riordan to sparse graphs without dense spots. In doing so, we replace the no dense spots hypothesis with weaker…
Hamed Hatami, László Lovász, Balázs Szegedy
The colored neighborhood metric for sparse graphs was introduced by Bollob´as and Riordan [8]. The corresponding convergence notion refines a convergence notion introduced by Benjamini and Schramm [6]. We prove that even in this refined sense, the limit of a convergent graph sequence (with uniformly bounded degree) can…
Madhumangal Pal
| Annals of | | | |:-----|:--------------|:--------------| | Pure and Applied | | | | Mathematics | | | | Mathematics | | | | Mathematics | | | | Mathematics | | | | Mathematics | | | | Mathematics | | | | Mathematics | | | | Mathematics | | | | Mathematics | | | | Mathematics | | | | Mathematics | | | | Mathematics |…
Samuel Korsky, Tahsin Saffat, Dhroova Aiylam
In this work we attempt to count the number of integer-valued h-Lipschitz functions (functions that change by at most h along edges) on two classes of sparse graphs; grid graphs Lm,n, and sparse random graphs G (n, d/n). We find that for all n-vertex graphs G with k connected components, the number of such functions…
Leon Bungert, Jeff Calder, Tim Roith
Lipschitz learning is a graph-based semi-supervised learning method where one extends labels from a labeled to an unlabeled data set by solving the infinity Laplace equation on a weighted graph. In this work we prove uniform convergence rates for solutions of the graph infinity Laplace equation as the number of…