On well separated point sets in the plane - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T03:26:31Z http://mathoverflow.net/feeds/question/115477 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115477/on-well-separated-point-sets-in-the-plane On well separated point sets in the plane TOM 2012-12-05T07:44:03Z 2012-12-07T16:39:44Z <p>Let us say that a finite set \$A\$ in the plane is \$1\$-separated if:</p> <p><strong>1)</strong> it has an even number of points;</p> <p><strong>2)</strong> no open ball of diameter \$1\$ contains more than \$|A|/2\$ points.</p> <p>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\$.</p> <blockquote> <p><em>Question</em>: 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?</p> </blockquote> <p><em>Comment</em>: 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). </p> http://mathoverflow.net/questions/115477/on-well-separated-point-sets-in-the-plane/115664#115664 Answer by domotorp for On well separated point sets in the plane domotorp 2012-12-07T01:26:01Z 2012-12-07T01:26:01Z <p>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.</p> http://mathoverflow.net/questions/115477/on-well-separated-point-sets-in-the-plane/115725#115725 Answer by Alfred for On well separated point sets in the plane Alfred 2012-12-07T16:39:44Z 2012-12-07T16:39:44Z <p>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}\$.</p>