Skip to main content
2 of 2
replaced http://mathoverflow.net/ with https://mathoverflow.net/

In the theory of Borel equivalence relations under Borel reducibility (see this MO answer, also Greg Hjorth's excellent survey article), which is concerned with general questions surrounding the relative difficulty of isomorphism relations and other relations arising in mathematics, particularly of the difficulty of their classification problems---the theory ultimately arranges these relations into a complex hierarchy under Borel reducibility---the class of countable graphs $\Gamma=\langle\mathbb{N},E\rangle$ is considered by identifying the graph $\Gamma$ with its edge relation $E\in 2^{\mathbb{N}^2}$, and using the ordinary product topology, and is thereby realized as a standard Borel space, which enjoys various uniqueness properties. See for example page 2 of these notes by Simon Thomas and Scott Schneider. The basic open sets of this topology on the space of countable graphs are therefore determined by specifying finitely many edges and finitely many non-edges.

(Note, however, that for the purpose of the Borel reducibility theory, the principal focus is on the resulting $\sigma$-algebra of Borel sets, rather than on the topology of open sets.)

The isomorphism relation on all countable graphs is a complete analytic relation, rather than Borel, but when you restrict to the case of locally finite graphs, then it becomes a Borel relation, and these exhibit various universal and completeness properties in the hierarchy.

Joel David Hamkins
  • 236.4k
  • 44
  • 777
  • 1.4k