Borel liftings of graph limits. (English) Zbl 1346.05274

Summary: The cut pseudo-metric on the space of graph limits induces an equivalence relation. The quotient space obtained by collapsing each equivalence class to a point is a metric space with appealing analytic properties. We show the equivalence relation admits a Borel lifting: There exists a Borel-measurable mapping that maps each equivalence class to one of its elements. The result yields a general framework for proving measurability properties on the space of graph limits. We give several examples, including Borel-measurability of the set of isomorphism classes of random-free graphons.


05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI arXiv Euclid