Property of points in the plane where distances are pairwise different. Existence of a pair which has min/max distance in different subsets.

Question

I was trying some exercises to prepare for a graph theory exam and I am stuck on a particular problem, namely:

One must show that given $P$, a set of $N$ points in the plane such that all distances are pairwise different, there is an $N$ such that one can find distinct points $x,y$ and subsets $S,S′$ of $P$, both of size $7$, where $x,y$ are in $S\cap S′$ and $d(x,y)$ is maximal in $S$ and minimal in $S′$. Additionally show that $N$ can be chosen to be less than $2020$.

I know that somehow I can apply results of Ramsey theory, my problem is I can't seem to translate the points to the right graph I need to consider.

Answer 1

Let $S$ be the $7$-set of minimum diameter and let $x,y$ its two points at maximum distance.

Now consider the set of vertices that are at distance at least $d(x,y)$ from $x$ and $y$. There has to be a bunch of them, because there can't be too many points in the the union of the two balls of radius $d(x,y)$ with centers $x,y$. You'll get a constant number $c$ such that at most $c$ points are at distance less than $d(x,y)$ from at least one of $x$ and $y$.

Consider the graph on these at least $N-c$ points that are at distance more than $d(x,y)$ from both $x$ and $y$. We color an edge blue if the distance is less than $d(x,y)$ and red if it is more than $d(x,y)$. this graph cannot have a blue $K_7$. If it has a red $K_5$ then we can take those $5$ points and $x,y$ to form the set $S'$.

Hence if $N$ is at least $R(5,7)+c$ we can guarantee those two numbers. It seems that $R(5,7) \leq 143$.

---

Here is a cheap way to get a $c$: we cover the union of the two open balls of radius $d(x,y)$ and centers $(0,0)$ and $(0,d(x,y))$ using the open balls of radius $d(x,y)/2$ and centers $(id(x,y)/4/4,kd(x,y)/4)$ with $0\leq i,j \leq 8$. So none of these balls can have more than $6$ points, hence there can be at most $9^2\cdot 6=486$ points in the union of those two open balls.

So it seems like $486+143 = 629$ works.

Answer 2

As another approach, take $S$ to be the set of $7$ points with minimum diameter. There may be more than one, but the diameter and the points $x,y$ at the ends of that diameter are fixed. Construct a regular hexagon with diameter $\overline{xy}$ and tile the plane with hexagons of that size. No hexagon except the first one can contain more than six points or that set of seven would have smaller diameter than $d(x,y)$. Each point can only be within $d(x,y)$ of points within seven hexagons. If we have points in $36$ hexagons besides the first we can find five of them at mutual distances greater than $d(x,y)$ and farther than $d(x,y)$ from each of $x,y$. We eliminate the first hexagon and all that surround it, then pick any point, eliminate its hexagon and all that surround it, and keep going. We need $7+6 \cdot 35 +1=212$ points to guarantee we can carry out the construction.