3
$\begingroup$

Take a set of $2n$ points in the plane and assume that no open set of diameter $1$ contains more than $n$ of these points.

Question: can we pair up the points so that the distance between the points in a pair is at least $1$?

$\endgroup$
3
  • 1
    $\begingroup$ Obviously false for $n=1$. For $n=2$ a counterexample is an equilateral triangle of side $1+\epsilon$ and it's center... $\endgroup$ Jun 16, 2012 at 3:00
  • $\begingroup$ Gjergji Zaimi, why false for $n=1$? $\endgroup$ Jun 16, 2012 at 3:50
  • $\begingroup$ Oops, I meant "obviously true for $n=1$". $\endgroup$ Jun 16, 2012 at 4:14

1 Answer 1

4
$\begingroup$

In Gjergi's $n=2$ counterexample, the center is an isolated point of the graph you'd like to match. One way to save your question might simply rule that out.

But consider your question without the hypothesis: When can we pair up $2n$ points so that the distance between the points in a pair is at least 1? General matching theory says yes, one can, whenever there is no Tutte obstruction. That means whenever you can't remove $k$ points and leave a graph with more than $k$ odd components. Now for two points to lie in distinct components is a strong condition: no path with big steps can connect them. In particular the distance between the points cannot be more than 1, and they can't both lie more than 1 unit away from any common third point.

Now one can get many components of size 1 by having many points clustered close together, which is roughly what your hypothesis meant to rule out. But even arranging points along a line, one can get many components and not all of them consisting of isolated points.

Hope that helps...sorry, don't have time to work this out further now.

$\endgroup$
0

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.