MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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}$.

share|cite|improve this answer
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... – domotorp Dec 7 '12 at 20:01
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 – Gerhard Paseman Dec 7 '12 at 20:04

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.

share|cite|improve this answer
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 – Gerhard Paseman Dec 7 '12 at 3:55
If you choose the diameter of the circle appropriately, then it is, imo, but of course I might be wrong. – domotorp Dec 7 '12 at 11:01
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 – Gerhard Paseman Dec 7 '12 at 17:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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