Separating points in the plane II

Question

Let A be a set of $2m$ points on the plane so that no open set of diameter $2$ has more than m of them. Define $A+A+...+A$ ($k$ times) to be the multiset of $k$-sums from $A$. That is, we consider all possible $(2m)^k$ sums.

Question. Does there exists a number $k$ independent of $m$ such that the points in the latter multiset can be paired so that the distance between the points each pair is at least 2?

Conjecture. $k=2$ is enough.

Comment. $k=1$ is not enough for the following reason. Take three points at distance $2$ and a point in the middle of them - then there is no such pairing. The intuition here is that the points get further and further apart when we are summing and hence we shall have the desired pairing.

One remark: The claim is true if $k$ is large enough for the following reason - the number of points in any open bounded open set divided by the total number of points goes to zero (concentration function bounds from probability) and so for $k$ large enough one can make any set of diameter 4 to have at most half of the points. But now notice that the graph on the multiset of the sums formed by adding an edge between two sums iff the distance between them is at least 2 has degree at least half the number of the sums as otherwise we would have more than half of the points would fit in a set of diameter 4 (the neighbourhood of that point with low degree). But this is Dirac's condition as so we have a perfect matching and are done.

Answer 1

Let me make the next step after Mirko Swirko.

In quite a beautiful paper A. Hajnal proves the following.

Theorem. Let $G$ be a $m$-saturated graph --- that is, $G$ does not contain a complete $(m+1)$-subgraph, but it does after adding any new edge. Then either $G$ has a vertex connected to each vertex, or the degree of every vertex in $G$ is at least $2(m-1)$.

Now take our $2m$ points and connect with an edge any two at distance $<2$. Then this graph does not contain a complete $(m+1)$-subgraph. Assume that there is no vertex connected to all other vertices.

Let us add the edges to this graph making no complete $(m+1)$-graph; by Hajnal's theorem, it is possible while all the degrees are less than $2(m-1)$; thus at the end we will get a vertex $x$ of degree exactly $2(m-1)$ and still no complete $(m+1)$-subgraph (maybe, this holds at the very beginning). Thus $x$ is connected to all but one other vertices; let $y$ be this exceptional vertex. Then even the obtained graph contains no complete $m$-subgraph after deleting $x$ and $y$: otherwise this subgraph augmented by $x$ forms a complete $(m+1)$-subgraph. Thus one may use these $x$ and $y$ in the induction step (they are not connected!).

The only case remaining is when there initially exists a vertex connected to all --- that is, all the points lie in an oper ball of radius 2 centered at this vertex. Maybe, this case is left for some third answer?

Answer 2

This is not an answer, only a detailed description of an idea that I do not know how to make work.

Attempt to prove the Conjecture that $k=2$ is enough, by induction on $m$. Say $A'$ has $2n$ points where $n=m+1$. A plane $m$-set (i.e. a set of $m$-many points) will be called an $m$-cluster if all pairwise distances of its points are $<2$. (Clearly an $m$-set $B$ is an $m$-cluster if and only if it is contained in some open set of diameter $2$.)

Case 1. There are points $x,y\in A'$ distance $2$ or more apart, such that the set $A=A'\setminus \{x,y\}$ contains no $(m+1)$-cluster. Then, by induction hypothesis, we could pair the points in $A+A$ as required. Next, for each $z\in A$, pair $z+x$ with $z+y$ (and formally also pair $x+z$ with $y+z$). Finally, pair $x+x$ with $x+y$, and pair $y+x$ with $y+y$. Thus, all points of $A'+A'$ were paired, which completes the proof for this easy Case 1.

Case 2. The negation of Case 1, namely: Whenever $x,y\in A'$ are distance $2$ or more apart, then there is an $(m+1)$-cluster $C_{x,y}$ contained in $A'\setminus \{x,y\}$. I do not know how to deal with this case (I thought one might perhaps employ Helly's theorem, but could not come up with anything specific). Case 2 does occur: Take $A'$ to be the $4$-set (here $m=1$ and $n=2$) described by the OP in the comment that $k=1$ is not enough (e.g. the vertices of an equilateral triangle with side $2$, and its medicenter (=centroid)).

As a side remark I wonder what the analogue of this problem for larger dimensions would be (perhaps only for larger even dimensions, since I do not know how to make an example in $3$-dimensions of a tetrahedron and its barycenter (= center of gravity): This makes $5$ points which is not even)?

Answer 3

Edit: This answer originally claimed to falsify the conjecture, for the trivial reason that there exists an example where the set $A+A$ does not have an even number of elements. However, since we are considering the multiset $A+A$, which takes multiplicities into account, the example does not falsify the conjecture.