Graphon space is totally bounded #
On the canonical carrier (I, volume) the space of graphons is totally bounded: for every ε
there are finitely many graphons within ε in cut distance of every graphon. The graphon space
over an arbitrary probability carrier embeds isometrically in the unit-interval one
(isometry_toGraphonSpaceI), so it is totally bounded as well.
The net is finite because a Frieze--Kannan approximation is a finite weighted graph on a vertex set
whose size depends only on ε, and both of its weightings can be pushed onto a grid at a controlled
cost: the block values by rounding down (exists_gridValue_cutDist_le) and the vertex weights by
rounding all but one of them down and letting the remaining vertex absorb the slack
(exists_gridWeightMeasure_cutDist_le). Finitely many grid weightings of a fixed finite vertex set
remain, each read onto (I, volume) by unitIntervalModel, along a measure-preserving map out of
the unit interval (Janson, Theorem A.9).
Total boundedness is one of the two halves of the Lovász--Szegedy compactness theorem, the other being completeness.
Main results #
TauCeti.DenseGraphLimits.totallyBounded_graphonSpaceI--GraphonSpaceIis totally bounded.TauCeti.DenseGraphLimits.totallyBounded_graphonSpace-- the graphon space over an arbitrary probability carrier is totally bounded.
References #
- L. Lovász, Large Networks and Graph Limits, AMS Colloquium Publications 60 (2012), §9.3.
- S. Janson, Graphons, cut norm and distance, couplings and rearrangements, NYJM Monographs 4 (2013), Theorem A.9.
Graphon space over the unit interval is totally bounded.
Graphon space over an arbitrary probability carrier is totally bounded: it embeds isometrically in the totally bounded unit-interval graphon space.