Graph theory-related problem, unit distance graph, pairs of people with restraining orders

Question

This problem is for my own exploration, not for class. The problem goes as follows:

There are $n$ pairs of people with restraining orders against one another. However, all $2n$ people are friends with the other $2n-2$ people (does not include the person they have the restraining order against). So, all $2n$ people are at a party. Each person wants to stand closer than $1$ to every person he is friends with. However, he must stand further than $1$ from the person who has a restraining order against him. We assume that the party is held in $\mathbb{R}^2$.

How large can $n$ be before this becomes impossible?

I conjecture than $n$ must be finite. However, it would also be useful if $n$ could be proven to be strictly countable.

EDIT: This can be done for all positive integers $n$. Can this be done for uncountably many pairs?

Answer 1

I shall prove that this task is not possible if there are uncountably many persons. Let $J$ be an (uncountable) index set, and for $j \in J$, $x_j$ and $y_j$ are two people with a restraining order against one another. Suppose that it is possible to put these people on $\mathbb{R}^d$ for some $d\in\mathbb{N}$ so that the required distance conditions are met.

Let $S$ be the set of points where these people are situated. By abuse of notation, the points of $S$ are also called $x_j$ and $y_j$, where $j\in J$. Clearly, no two persons can be placed at the same location.

We first claim that there exists a point $p$ in $S$ such that, for any positive real number $\epsilon$, the open ball $B(p,\epsilon):=\left\{q\in\mathbb{R}^d\,\Big|\,\|p-q\|_2<\epsilon\right\}$ contains a point in $S$ other than $p$. We shall prove this claim by contradiction. If the opposite of the claim above is true, then for every $p\in S$, there exists $\epsilon_p>0$ such that $B\left(p,\epsilon_p\right)\cap S=\{p\}$. Clearly, for each $p\in S$, there exists a point $q_p\in B\left(p,\epsilon_p\right)$ with rational coordinates. Hence, the map $S\to \mathbb{Q}^d$ sending $p\in S$ to $q_p$ is an injective function from an uncountable set to a countable set, which is a contradiction. Therefore, there exists a point $p \in S$, which we shall assume without loss of generality that $p=y_\alpha$ for some $\alpha \in J$, such that any ball $B(p,\epsilon)$, where $\epsilon>0$, contains a point in $S$ other than $p$.

Now, we look at $x_\alpha$. Let $r:=\left\|x_\alpha-y_\alpha\right\|_2$. By the assumption, $r>1$. Take $\varepsilon:=\frac{r-1}{2}$ so that $\varepsilon>0$. The ball $B\left(y_\alpha,\varepsilon\right)$ contains a point $q \in S$ with $q\neq p$, which must be friends with $x_\alpha$. However, by the Triangle Inequality, $$\left\|x_\alpha-q\right\|_2\geq \left\|x_\alpha -y_\alpha\right\|_2 - \left\|y_\alpha-q\right\|_2>r-\epsilon=\frac{r+1}{2}>1\,.$$ This is a contradiction. Ergo, the task is impossible.

Now, what is left is when there are infinitely but countably many persons. I conjecture that the task is still impossible.

P.S. In my proof, I used the $2$-norm $\|\bullet\|_2$ (also known as the Euclidean norm). However, you can use any metric on $\mathbb{R}^d$ that is equivalent to the metric associated to the Euclidean norm.

---

EDIT: This is my attempt to prove that the task is impossible when $J$ is countable, say $J:=\mathbb{N}$. Suppose contrary that it is possible, and we use the same settings as before.

We now observe that $S$ is a bounded set, whence, due to the Heine-Borel Theorem, its topological closure $\bar{S}$ is compact, making it also sequentially compact. Therefore, the sequence $\left\{x_i\right\}_{i\in\mathbb{N}}$ has a subsequence $\left\{x_{i_j}\right\}_{j\in\mathbb{N}}$ converging to a point $u$ in $\bar{S}$. Now, the sequence $\left\{y_{i_j}\right\}_{j\in\mathbb{N}}$ has a subsequence $\left\{y_{i_{j_k}}\right\}_{k\in\mathbb{N}}$ converging to a point $v\in\bar{S}$. We denote $u_k$ for $x_{i_{j_k}}$ and $v_k$ for $y_{i_{j_k}}$ for all $k\in\mathbb{N}$. Hence, $\displaystyle\lim_{k\to\infty}\,u_k=u$ and $\displaystyle\lim_{k\to\infty}\,v_k=v$.

Note that $\left\|u_i-v_i\right\|_2 >1$ and $\left\|u_i-v_j\right\|_2<1$ for all $i,j\in\mathbb{N}$ such that $i \neq j$. Thus, $$\left\|u-v_j\right\|_2=\displaystyle \lim_{k\to\infty}\,\left\|u_k-v_j\right\|_2\leq 1 \text{ and }\left\|u_i-v\right\|=\displaystyle\lim_{k\to\infty}\,\left\|u_i-v_k\right\|_2\leq 1$$ for all $i,j \in \mathbb{N}$. Ergo, $\|u-v\|_2=\displaystyle\lim_{j\to\infty}\,\left\|u-v_j\right\|_2\leq 1$. However, $$\|u-v\|_2=\displaystyle\lim_{i\to\infty}\,\left\|u_i-v_i\right\|_2\geq 1\,.$$ That is, $\|u-v\|_2=1$.

I shall leave the rest to smart individuals.

Answer 2

This can be done for all $n$. Order the $2n$ people so that person $k$ has a restraining order against person $k + n$ (and vice versa) for every $k$. Then put person $k$ on a circle centered at the origin; more specifically, position them at $r e^{2\pi k i/ 2n}$, with $r$ to be decided later. Then on the opposite side of the circle from the person whom they have a restraining order against, and is thus a distance of $2r$ away. The person they are second furthest from they are a distance of $$ |r e^{2\pi ki /2n} - r e^{2 \pi i (k + n + 1)/2n} | = r| - 1 - e^{i \pi /n} |.$$

We thus must choose $r$ so that $2r > 1$ and $r| - 1- e^{i\pi/n}| < 1$. We thus can pick $$ r = \frac{1}{2}\left(\frac{1}{2} + \frac{1}{| - 1- e^{i\pi/n}|}\right).$$ Then since $| - 1- e^{i\pi/n}| < 2$, we have

$$ r = \frac{1}{2}\left(\frac{1}{2} + \frac{1}{| - 1- e^{i\pi/n}|}\right) > \frac{1}{2}\left(\frac{1}{2} + \frac{1}{2}\right) = \frac{1}{2}$$ and $$ r = \frac{1}{2}\left(\frac{1}{2} + \frac{1}{| - 1- e^{i\pi/n}|}\right) < \frac{1}{2}\left(\frac{1}{| - 1- e^{i\pi/n}|} + \frac{1}{| - 1- e^{i\pi/n}|}\right) = \frac{1}{| - 1- e^{i\pi/n}|}$$ as desired.