A Recursive Presentation of the Graphon Space

Open Access
Nicodemus, Patrick Blair
Area of Honors:
Bachelor of Science
Document Type:
Thesis Supervisors:
  • Jan Severin Reimann, Thesis Supervisor
  • Nathanial Patrick Brown, Honors Advisor
  • graph theory
  • graphon
  • descriptive set theory
  • effective descriptive set theory
  • graph homomorphisms
  • effective Polish space
  • recursive presentation
Graphons are objects that represent the limits of sequences of finite graphs - the “completion” of the set of graphs under the cut metric. The study of these continuous generalizations of graphs has been very fruitful, resulting in (among other things) elegant generalizations of the Szemeredi Regularity Lemma, advances in graph property testing, and applications to computer science, quantum computation, and statistical physics. This space is complete and separable, so it forms a Polish space. In this paper I show that, furthermore, it is an effective Polish space; that is, an algorithm exists which can decide in finite time whether the distance between members of a certain dense subset is greater than, less than, or equal to any given rational number. The space is naturally divided into equivalence classes of isomorphic graphons which can be transformed into each other through “relabelling” of nodes. The subject of Polish spaces partitioned into equivalence classes (called “singular spaces”) is a topic which is an active research area in descriptive set theory, and so identifying the basic characteristics of the graphon space may be the first step to more interesting results obtained by studying this space through the lens of descriptive set theory and effective descriptive set theory.