9
$\begingroup$

Let us say that a finite set $A$ in the plane is $1$-separated if:

1) it has an even number of points;

2) no open ball of diameter $1$ contains more than $|A|/2$ points.

For a $1$-separated set $A$ define $G(A)$ to be a graph where two points $x,y$ in $A$ are joined by an edge iff the distance between them is at least $1$.

Question: can one find a finite set of graphs $G _ 1,\dots,G _ n$ such that any $1$-separated set $A $ can be partitioned into non-empty $1$-separated sets $A _ 1,\dots,A _ k$ such that $G(A _ i)$ is isomorphic to one of the $G _ j$'s?

Comment: The definition makes sense on the real line (the ball of diameter $1$ is replaced by an interval of length $1$). In that case we can take $n=1$ and $G_1$ to be a graph on two vertices joined by an edge (that is, $G(A)$ contains a matching).

$\endgroup$

2 Answers 2

3
$\begingroup$

I think Domotorp is correct. Take a regular $(2n-1)$-gon such that its longest diagonal is 1, along with its center. Then $A$ cannot be partitioned, and $G(A)=C_{2n-1}$.

$\endgroup$
2
  • $\begingroup$ Thx Alfred! ps. I suppose you answered instead of commenting as you did not have enough rep points. But I wonder how come both of our answers have one upvote right now. I have not voted on yours, meaning either you have not voted on mine although you think I am correct, or someone else thinks you're correct but I'm not... $\endgroup$
    – domotorp
    Dec 7, 2012 at 20:01
  • $\begingroup$ I have not voted on either of your or Alfred's answers. My favorite is Alfred's because his description is harder for me to mess up or misconstrue. Gerhard "It Is Just My Opinion" Paseman, 2012.12.07 $\endgroup$ Dec 7, 2012 at 20:04
2
$\begingroup$

No, there is a counterexample. Take a circle, whose diameter is slightly larger than 1 and put |A|-1 points evenly around its boundary and the last point to its center. This set will be 1-separated, but no matter how you partition it, the part containing the center will not be 1-separated.

$\endgroup$
3
  • $\begingroup$ Uh, this example is not 1-separated. (E.g. take 2 or 4 points to start.) Gerhard "Ask Me About System Design" Paseman, 2012.12.06 $\endgroup$ Dec 7, 2012 at 3:55
  • 1
    $\begingroup$ If you choose the diameter of the circle appropriately, then it is, imo, but of course I might be wrong. $\endgroup$
    – domotorp
    Dec 7, 2012 at 11:01
  • $\begingroup$ It is possible I misunderstand. My assumption was that the longest diagonal was less than 1 because the diameter was very close to 1. As Alfred mentions, there is a choice of A following your suggestion in which G(A) is an odd cycle. Gerhard "Having A Problem With Focus" Paseman, 2012.12.07 $\endgroup$ Dec 7, 2012 at 17:02

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.