Let $(X,\tau)$ be a topological space. We say that $x\neq y\in X$ are close if every neighborhood of $x$ intersects every neighborhood of $y$. We associate to $(X,\tau)$ a graph $G(X,\tau)=(V,E)$ with $V = X$ and $$E=\big\{\{x,y\}: x\neq y \in X \text{ and } x,y \text{ are close}\big\}.$$

Given an infinite simple graph $G=(V,E)$, is there a topology $\tau$ on $V$ such that $G(V,\tau) = G$?

  • $\begingroup$ You could take a look at the work on the modal logics of spaces by amongst other Benthem. I believe he axiomatizes topological spaces from a modal logic point of view. See e.g. Modal Logic of Spaces, Benthem and Bezhanishvili. $\endgroup$ – Pål GD Dec 11 '16 at 15:07
  • $\begingroup$ What do you mean by a "topological surface". The usual definition assumes it is a Hausdorff space. $\endgroup$ – Alexandre Eremenko Dec 11 '16 at 16:03

I think the answer is (sadly) no : take a complete graph $K_n = (V, E)$ and remove an edge, say between $x$ and $y$. Then assume you have such a topology $\tau$. Take any $U, W\in \tau$ such that $x\in U$, $y \in W$ and $U\cap W=\emptyset$ (two such open sets exist,otherwise $x$ would be close to $y$). Since any point in $U$, different from $x$ is close to $y$, if there were any, say $z$, we would have that $U$ is a neighbourhood of $z$, and $W$ a neighbourhood of $y$, so that $U\cap W \neq \emptyset$. That's a contradiction, so $U=\{x\}$. For sufficiently large $n$, this is obviously impossible ($n=4$ for instance)

Edit :Bof was quicker than me

2nd edit : there was a mistake in my argument : the last part where I say it's impossible : well it's not. There needs to be at least 4 points so that you can remove 2 edges with no common endpoint, apply the same reasoning to another $a$, so that both $\{a\}$ and $\{x\}$ are open sets, and $a,x$ are connected by an edge, which then brings us a contradiction. Sorry about that. (However the answer is still no)

| cite | improve this answer | |
  • 1
    $\begingroup$ No, you beat me by 52 seconds. $\endgroup$ – bof Dec 11 '16 at 11:00

Counterexample. Let $V$ be an infinite set. Choose four distinct points $a,b,c,d\in V.$ Let $G$ be the graph on the vertex set $V$ in which every pair of distinct points is an edge except $\{a,b\}$ and $\{c,d\}.$ Assume for a contradiction that $\tau$ is a topology on $V$ such that $G(V,\tau)=G.$

Since $a$ and $b$ are not close they have disjoint open neighborhoods, call them $A$ and $B.$ Then $b$ is close to no point of $A.$ Since $b$ is close to every point except $a,$ it follows that $A=\{a\},$ i.e., $\{a\}$ is an open set. A similar argument shows that $\{c\}$ is an open set. But then $a$ and $c$ are not close, although they are joined by an edge.

More generally, let $G=(V,E)$ be any graph. If $G=G(V,\tau)$ for some topology $\tau,$ then the following condition must hold:

If $a,b,a',b'$ are four distinct vertices such that $ab\in E$ and $aa',bb'\notin E,$ then there is a vertex $v\notin\{a',b'\}$ such that $va'\notin E$ and $vb'\notin E.$

(Clearly, there are many infinite graphs $G$ which do not satisfy this condition.)

Proof. Since $aa',bb'\notin E,$ there are open sets $A,A',B,B'$ such that $a\in A,a'\in A',A\cap A'=\emptyset,b\in B,b'\in B',B\cap B'=\emptyset.$ Since $ab\in E,$ we have $A\cap B\ne\emptyset;$ choose a vertex $v\in A\cap B.$ Since $A,A'$ are disjoint open sets with $v\in A$ and $a'\in A',$ we have $v\ne a'$ and $va'\notin E.$ Similarly, $v\ne b'$ and $vb'\notin E.$ Thus we have $v\notin\{a',b'\}$ and $va',vb'\notin E,$ Q.E.D.

| cite | improve this answer | |
  • $\begingroup$ An interesting question would be : how can we refine your last claim in order to get a sufficient condition ? $\endgroup$ – Maxime Ramzi Dec 11 '16 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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