SCIENCE@home

On the computability of graphons

N. Ackerman,J. Avigad,Cameron E. Freer,Daniel M. Roy,Jason M. Rute

Published 2018 in arXiv.org

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'$ suffices to move between computable such representations. We show that $0'$ 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.

PUBLICATION RECORD

  • Publication year

    2018

  • Venue

    arXiv.org

  • Publication date

    2018-01-31

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1801.10387
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-10 of 10 references · Page 1 of 1

CITED BY

Showing 1-5 of 5 citing papers · Page 1 of 1