Would it be possible to define an order theoretic topology on graphs? I am thinking about the Scott topology. There would be an associated continuous map on graphs.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ I suppose you could build the nerve of a graph and use that as a topology, but it won't be the same thing as the Scott topology in the case of the graph of some arbitrary partial order, for example. I guess the answer is that "yes, you can define many topologies", but the real question is which is the most useful one for your applications? Probably the closest notion to a continuous map for graphs would be a graph homomorphism, but you don't really need a topology to define that.. $\endgroup$– MikolaCommented Jun 24, 2011 at 19:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Jun 25, 2011 at 12:52
-
$\begingroup$ This answer describes a commonly used natural topology on the space of all graphs, rather than a topology on a fixed graph, and I realize now that perhaps this isn't what was desired. $\endgroup$ Commented Jun 25, 2011 at 12:59
-
$\begingroup$ Hi, Yes, I was thinking of the basic relationship between dcpos and directed graphs where an edge is interpreted as the relation in the dcpo. So, the Scott continuous map is defined on an individual dcpo and its language contains reference mainly to the ordering relation. Thus, a similarly defined continuous map for a graph would concern edges. $\endgroup$ Commented Jun 25, 2011 at 19:47
-
$\begingroup$ This comment is coming far too late, but I had a look at the Borel-reducibility notion and I think it is quite interesting. I might have been thinking about functors in terms of Borel reducibility. For instance, an equivalence relation in category theory is over morphisms like $fg=h$ A functor maps diagrams to diagrams, so $F: fg=h \rightarrow F(f)F(g)=F(h)$ I was trying to see functors as equivalence relations going into more or less "simple" (a term used to compare Borel Relations) equivalence relations. Joel's post is actually insightful as to my thinking. Thanks Joel. $\endgroup$ Commented Jul 13, 2011 at 12:32