Borel liftings of graph limits. (English) Zbl 1346.05274

Orbanz, Peter; Szegedy, Balazs

Electron. Commun. Probab. 21, Paper No. 65, 4 p. (2016).

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.

MSC:

05C80

Random graphs (graph-theoretic aspects)

Keywords:

graph limits; random graphs