0
$\begingroup$

For any set $X$ we define $[X]^2 =\big\{\{a,b\}: a, b \in X\text{ and }a\neq b\big\}$.

Let $$E = \big\{\{(a_1, a_2), (b_1, b_2)\}\in[\omega\times\omega]^2: |a_i-b_i| = 1\text{ for some } i\in\{1,2\}\big\}.$$

Is there a topology $\tau$ on $\omega\times\omega$ such that $A\subseteq (\omega\times\omega)$ is connected with respect to $\tau$ if and only if $A$ is a connected subgraph of $(\omega\times\omega, E)$?

$\endgroup$
4
$\begingroup$

No. There is no topology such that sets with even just two elements are connected if and only if there is an edge between the two vertices for your graph.

To see this consider that a set of two elements $\{ a,b \}$ is topologically connected if and only if all open sets containing $a$ also contain $b$ or all open sets containing $b$ also contain $a$. If the latter condition fails, we can find open sets separating $\{a, b\}$; if the former condition fails, then there must be an open set containing $a$ but not $b$ and another open set containing $b$ but not $a$.

Thus given a topology on our vertex space, we can define a directed graph by $aRb$ when all open sets containing $a$ also contain $b$. Note that this is a transitive relationship, so our directed graph will be transitive as well. Then by forgetting the directionality, we get the graph such that the edge relation is equivalent to topological connectedness of two element sets.

Thus if we start with a graph, and there is no way to turn it into a transitive directed graph, we can see that there is no topology on the vertices that gives equivalent connectedness notions. So for any graph, we simply need to find a subgraph that cannot be made into a transitive directed graph.

In the case of your graph, the problematic subgraph is: $$\{ (0,0), (1,1), (3,2), (2, 3), (4,3), (3,4) \} .$$

This subgraph contains a triangle and three exterior points that are each connected to only one vertex in the triangle. There is no way to turn this into a transitive directed graph, as any directionality on the triangle will cause some vertex in the triangle to have both an incoming and outgoing arrow. Then the exterior point connected to this vertex has no possible direction without adding another edge due to transitivity.

I am unsure of a general characterization of graphs that cannot be made into directed transitive graphs.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.