Let $S_1, S_2 \subseteq \mathbb{R}^2$ be two finite disjoint sets of points in the plane with $\texttt{diam}(S_1) \leq 1$ and $\texttt{diam}(S_2) \leq 1$.

Does there always exist a transformation $f: S_1 \cup S_2 \rightarrow \mathbb{R}^2$ such that:

  1. $\texttt{diam}(f(S_1)) \leq 1$, $\texttt{diam}(f(S_2)) \leq 1$; and
  2. for any pair of points $s_1 \in S_1$ and $s_2 \in S_2$ we have $d(s_1,s_2) \leq 1 \iff d(f(s_1), f(s_2)) > 1$, where $d(x,y)$ is the Eucledean distance between $x$ and $y$?

No, and in fact, most of your conditions are not needed.

Take a unit square, and let $S_1$ be one of its sides, and $S_2$ another side parallel to it. This example has the property that for every $s_1\in S_1$ there is exactly one $s_2\in S_2$ for which $d(s_1,s_2)\le 1$. Consider the uncountably many open sets defined as $H_{s_1}=\{x\mid d(f(s_1),x)>1\}$ for $s_1\in S_1$. Each of these must contain exactly one point of $S_2$. But using that the plane is a Lindelöf space, already countably many of the $H_{s_1}$ must cover the whole plane. This contradicts that $S_2$ has uncountably many points.

  • $\begingroup$ sorry, I forgot to mention that both $S_1$ and $S_2$ are finite sets (I modified the question) $\endgroup$ – Victor Jun 29 '16 at 6:33
  • $\begingroup$ I think you should remove the fa.functional-analysis tag, and rather add co.combinatorics. Probably there is still some simple counterexample, I would start by reading about unit disk graphs. $\endgroup$ – domotorp Jun 29 '16 at 13:54
  • $\begingroup$ In fact, this question came from a conjecture that the class of co-biparite unit disk graphs is 'self-complementary', which was posed in this paper arxiv.org/abs/1602.08148 . Formally, the conjecture says that if one has a unit disk graph with a fixed partition of its vertices into two cliques, then by complementing the edges between the cliques we get a unit disk graph again. $\endgroup$ – Victor Jun 29 '16 at 15:09
  • $\begingroup$ The conjecture was proved for a special case (when the edges between the cliques form a C4-free bipartite graph), and we tend to believe that it is true in general. I just thought that ideas from other areas of mathematics may be helpful here. $\endgroup$ – Victor Jun 29 '16 at 15:09
  • 1
    $\begingroup$ Yeah, I was thinking about the same conjecture (and I thought that it must fail), in fact, this conjecture seems more interesting than the original question. I think in general it's a good idea to give as much motivation as possible when you pose a question on MO, then people might get more interested - like I did just now! $\endgroup$ – domotorp Jun 29 '16 at 16:30

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.