Let $(X,\tau)$ be a topological space. Let us call $x,y\in X$ swappable if there is $f:X\to X$ continuous such that $f(x)=y$ and $f(y)=x$. This relation is obviously reflexive and symmetric, but not necessarily transitive.

What is an example of a set $X$ and a reflexive and symmetric relation $R\subseteq X\times X$ such that there is no topology $\tau$ on $X$ such that $R$ equals the swappability relation of $(X,\tau)$?

  • $\begingroup$ Have you looked at the three element set $\{a,b,c\}$ with the reflexive and symmetric relation spanned by $ab$ and $bc$? Which of the topologies gives that relation ? Is there a clever way to list all topologies? $\endgroup$ – HenrikRüping Feb 16 '17 at 13:17
  • 1
    $\begingroup$ I see its for example the swappability relation for the topology wth basis $\{a\},\{a,b\},\{c\}$. $\endgroup$ – HenrikRüping Feb 17 '17 at 8:49
  • 1
    $\begingroup$ I added a graph theory tag, since this is about reflexive, symmetric relations. $\endgroup$ – Keith Kearnes Feb 19 '17 at 3:56

If ${\mathbf X}=(X,\tau)$ is a topological space with swappability relation $R$, call $(X,R)$ the swappability graph of ${\mathbf X}$. This graph

not a swappability graph

is not the swappability graph of any topological space.


Assume otherwise that this graph, which I will call ${\mathbf G}$, is the swappability graph of the space $(X,\tau)$ where $X=\{A, B, C, D, E, F\}$.

  1. This is a finite graph, so $\tau$ is determined by the specialization preorder on $X$, say $x\leq y$ if $x$ is in the closure of $\{y\}$.

  2. If $x\equiv y$ denotes $x\leq y$ and $y\leq x$, then $x\equiv y$ implies that $x$ is swappable with $y$ and also with exactly the same other elements as $y$. This implies that $x$ and $y$ are equal or adjacent in ${\mathbf G}$ and that they have the same neighborhoods in the swappability graph. By examining ${\mathbf G}$ one sees that $x\equiv y$ iff $x=y$. Thus, the specialization preorder is a partial order.

Now we examine the relationship between the swappability graph and the incomparability graph of the specialization order of $(X,\tau)$.

  1. For $x\neq y$, if $x$ and $y$ are swappable, then they are incomparable in the specialization order. (Maybe the contrapositive statement is more obvious.)

  2. Call a vertex of ${\mathbf G}$ of degree $2$ a corner ($A, D$ or $F$), and call a vertex of degree $4$ an interior vertex ($B, C$ or $E$). Any interior vertex is adjacent or equal in ${\mathbf G}$ to all but one of the other vertices, hence is swappable with all but one of the other vertices, hence is incomparable with all but POSSIBLY $1$ of the other vertices. If an interior vertex is incomparable with ALL other vertices, then it is isolated in the order, so is swappable with all, which is not the case here. Conclusion: each interior vertex is comparable with exactly one other vertex, namely the opposite corner vertex.

  3. We are at the point where we know that the swappability graph ${\mathbf G}$ looks exactly like the incomparability graph of the specialization order, except for the possibility that the incomparability graph has additional edges between the corners. In particular, the $3$ interior vertices (a clique under swappability/incomparability) must be an antichain in the specialization order. Call this the interior clique. Each vertex in this clique is comparable with exactly one corner, while each corner is comparable with exactly one vertex in the interior clique.

  4. There are now a few cases to check: It may be that, under the specialization order, each corner is above its corresponding vertex in the interior clique. (Call it an above-corner.) In this case it is easy to see that the swappability graph is $K_6$ minus a $1$-factor (which is not ${\bf G}$, contradiction). The same happens if each corner is below its corresponding vertex in the interior clique (a below-corner). Now check what happens if, say, $2$ corners are above-corners while the third corner is a below-corner. Even here there are cases, depending on how the corners compare to each other in the specialization order. The two above-corners cannot be comparable to each other, but may be comparable to the below-corner. There are three cases to check: no above-corner is comparable to a below-corner (swappability graph is $K_6$ minus a $1$-factor); exactly one above-corner is above the below-corner (swappability graph has vertices of degree $3$, so is not ${\mathbf G}$); or both above-corners are above the below-corner (the above-corners are swappable, so the swappability graph cannot be ${\mathbf G}$). This covers all cases up to symmetry.

| cite | improve this answer | |

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.