9
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ Well I did try it. And for this example there are many such pairings of the multiset of the corresponding 16 points. Maybe it is a misunderstanding? The sums of this configuration for three triangles with one point at the center and the matching is obvious - just matching the center with the furthest point with the center and the rest is obvious. $\endgroup$
    – TOM
    Oct 19, 2014 at 4:11
  • 1
    $\begingroup$ Wait a moment, if your open ball has radius 1, not diameter 1, your 4 points don't satisfy the condition. $\endgroup$
    – Wolfgang
    Oct 19, 2014 at 7:35
  • 1
    $\begingroup$ and how do you define "sums of points"? Is there an origin specified, and you mean the vectors? $\endgroup$
    – Wolfgang
    Oct 19, 2014 at 7:38
  • $\begingroup$ I am sorry, in the example it was supposed to be said that the 3 points are at distance 2, not 1 (thanks Wolfgang). I will edit the question. $\endgroup$
    – TOM
    Oct 19, 2014 at 9:30
  • $\begingroup$ @Wolfgang: the sums are defined adding vectors coordinatewise. I modified the question and hope it will be clearer what I mean now. $\endgroup$
    – TOM
    Oct 19, 2014 at 9:34

3 Answers 3

2
+50
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Say $A$ is a $2m$-set, no $(m+1)$-clusters, $A$ contained in the open ball with radius $2$ at some $v\in A$. (More than one $v$ may have this property.) Then there is no $m$-cluster $B$ contained in $A\setminus \{v\}$: For otherwise $B\cup\{v\}$ would be an $(m+1)$-cluster. Also, at least $m$-many members of $A$ are distance $1$ or more away form $v$. If $d(v,x)\ge1$ then $v+v$ and $x+x$ could be paired. If $p+q$ was paired with $s+t$ (at the induction step) then we could perhaps break this pairing, and pair $x+v$ with $p+q$, and $v+x$ with $s+t$. Wolog $v$ is the origin, so $A\subset A+A$. $\endgroup$
    – Mirko
    Oct 24, 2014 at 22:02
  • $\begingroup$ @Mirko: Yes, that's true (except perhaps for the last step), but it seems that it is not enough. Also, you need to pair $x$ not only with itself, but also with other `centers'... $\endgroup$ Oct 24, 2014 at 22:09
  • $\begingroup$ Right, it does not seem to be enough, but I didn't know what else to say (trying to get something new). I also wonder if the above ideas are about sufficient so one could perhaps prove the weaker conjecture that $k=3$ might be enough. If $A+\cdots+A$, $k$-times is paired, does that automatically provide a pairing for $A+\cdots+A+A$, $(k+1)$-times (if true should be easy)? Or perhaps $k=4$ is enough, think of it as $(A+A)+(A+A)$, would it always be true that $(A+A)$ satisfies the easy case of the induction? But, it seems that $k=2$ might work, and it would be the most interesting case to prove. $\endgroup$
    – Mirko
    Oct 24, 2014 at 22:26
2
$\begingroup$

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)?

$\endgroup$
1
  • $\begingroup$ A minor point concerning the 4-point example showing that $k=1$ is not enough, so take $3$ points distance $2$ apart, and "a point in the middle" as the OP said, or "the centroid" in my answer: Any point in the interior of the Reuleaux triangle determined by the $3$ vertices would work. $\endgroup$
    – Mirko
    Oct 27, 2014 at 14:22
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Did you notice the word `multiset'? It means that the multiplicities are taken into account. $\endgroup$ Oct 21, 2014 at 17:33
  • $\begingroup$ I see. I didn't know multisets so my mind somehow read just "set". Of course, my answer makes no sense then. I will edit it accordingly. $\endgroup$
    – B K
    Oct 21, 2014 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.