Graphons, cut norm and distance, couplings and rearrangements

2010/09/13 by Janson, Svante · 10 citations
#05C99 #28A20 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1009.2376

Abstract

We give a survey of basic results on the cut norm and cut metric for graphons (and sometimes more general kernels), with emphasis on the equivalence problem. The main results are not new, but we add various technical complements, and a new proof of the uniqueness theorem by Borgs, Chayes and Lovász. We allow graphons on general probability spaces whenever possible. We also give some new results for 0,1-valued graphons and for pure graphons.

Cited by

• Graph Limits via Quotients
• Banach-valued graph limits: Graphon representability and Banach-space structure
• Multiplexons: Limits of Multiplex Networks
• On the Convergence and Size Transferability of Continuous-depth Graph Neural Networks
• Equivalence by coupling for heterogeneous SIS models*
• Learning graphons from data: Random walks, transfer operators, and spectral clustering
• Sparse optimal control for infinite-dimensional linear systems with applications to graphon control
• Stochastic Graphon Games with Interventions
• Convergence of spectra of digraph limits
• Opinion Dynamics on Signed Graphs and Graphons

Related

• Graphons and cut metric on sigma-finite measure spaces
• The cut metric for probability distributions
• A Partial Characterization of Robinsonian L^p Graphons
• A sampling construction of graphon 1-norm convergence
• Regularity partitions and the topology of graphons