Graphons, cut norm and distance, couplings and rearrangements

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.

72 pages. This version contains a new section on pure graphons and some other minor additions, including a new appendix and new references

References in corpus (8)

• Graph limits and exchangeable random graphs
• Limits of compact decorated graphs
• A measure-theoretic approach to the theory of dense hypergraphs
• Monotone graph limits and quasimonotone graphs
• Limits of permutation sequences
• Random Graphons and a Weak Positivstellensatz for Graphs
• Interval graph limits
• Multigraph limits and exchangeability

Cited by in corpus (10)

• Sparse exchangeable graphs and their limits via graphon processes
• On edge exchangeable random graphs
• Monotone graph limits and quasimonotone graphs
• An example of graph limits of growing sequences of random graphs
• A classification of orbits admitting a unique invariant measure
• Invariant measures via inverse limits of finite structures
• Interval graph limits
• Probabilistic programming interfaces for random graphs: Markov categories, graphons, and nominal sets
• Probability-graphons: Limits of large dense weighted graphs
• Approximate Fréchet Mean for Data Sets of Sparse Graphs