On the computability of graphons

MaRDI QIDQ6297157zbMATH OpenFDO

Authors Nathanael Ackerman, Jeremy Avigad, Cameron E. Freer, Daniel M. Roy, Jason Rute

Publication date 31 January 2018

Abstract: We investigate the relative computability of exchangeable binary relational data when presented in terms of the distribution of an invariant measure on graphs, or as a graphon in either $L^1$ or the cut distance. We establish basic computable equivalences, and show that $L^1$ representations contain fundamentally more computable information than the other representations, but that $0^{\prime }$ suffices to move between computable such representations. We show that $0^{\prime }$ is necessary in general, but that in the case of random-free graphons, no oracle is necessary. We also provide an example of an $L^1$-computable random-free graphon that is not weakly isomorphic to any graphon with an a.e. continuous version.

This page was built for publication: On the computability of graphons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6297157)