## On well separated point sets in the plane

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

## 2 Answers

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

-

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 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 at 20:04

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
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 at 3:55

1
If you choose the diameter of the circle appropriately, then it is, imo, but of course I might be wrong. – domotorp Dec 7 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 at 17:02
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 25, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9591383337974548, "perplexity_flag": "head"}