5
$\begingroup$

Let $(X,\tau)$ be a topological space. We say that $x, y \in X$ are close if for every neighborhood $U$ of $x$ and $V$ of $y$ we have $U\cap V \neq \emptyset$. Let $E$ be the set of $\{x,y\}$ where $x,y\in X$ with $x\neq y$ and $x,y$ are close. We say $G(X,\tau) = (X,E)$ is the closeness graph of $(X,\tau)$.

Given any simple undirected graph $G$, is there a topological space $(X,\tau)$ such that $G\cong G(X,\tau)$?

$\endgroup$
  • $\begingroup$ An initial thought is that it would suffice to do this for connected graphs (since then by adding an open set corresponding to each connected component of the graph would give the desired topology once each component had been dealt with separately). $\endgroup$ – Tobias Kildetoft Oct 6 '15 at 7:03
  • $\begingroup$ Another thought - would be better to clarify the finite case first: is there a preorder on vertices of $G$ such that edges of $G$ are precisely two-element subsets having an upper bound wrt this preorder. $\endgroup$ – მამუკა ჯიბლაძე Oct 6 '15 at 8:55
7
$\begingroup$

There is no topology on 4 elements whose closeness graph is the $4$-cycle.

(Proof: Let's call the elements $\{A,B,C,D\}$. Define a directed graph with these elements as vertices and a directed edge $u\to v$ whenever every open set containing $u$, also contains $v$, this has to be transitive and contain all self loops, lets call this directed graph $H(X,\tau)$. Two vertices $u,v$ in the closeness graph are connected iff there is a $w$ such that $u\to w$ and $v\to w$ in $H$. Now, we see that we can't have edges between $A$ and $C$ or between $B$ and $D$, however any orientation of the $4$-cycle $ABCD$ either includes a diagonal in the transitive closure, or it has edges $A\to B$, $C\to B$, or it has edges $B\to C$, $D\to C$. In each case the closeness graph must contain one of the diagonals.)

Update: Every undirected graph $G$ can be realized as a connected component of the closeness graph of some topological space. To prove this, let $Y=V(G)\sqcup E(G)$, and let $\tau$ be the topology generated by the open sets $\{e\}$ for all edges $e$, and $\{v,e\}$ whenever $v$ is an endpoint of $e$. Then $G$ is a connected component of $G(Y,\tau)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ For the last part - more precisely every connected component of $G$ corresponds to a connected component of $G(Y,\tau)$. $\endgroup$ – მამუკა ჯიბლაძე Oct 6 '15 at 21:02

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.