A combinatorial proof by tesselation of the plane.

193 Views Asked by At

Some days ago the following problem was posed in the site: given a set of $N$ points in the plane such that for each pair of points $p,q$ we have $\lVert p-q\rVert >1$, prove there is a subset of size at least $N/7$ such that every pair of points $p,q$ we have $\lVert p-q\rVert >\sqrt 3$. My idea was to consider a tesselation of the plane by equilateral triangles of side $1$. If one glues two of them by a common side we obtain a rhombus of great diagonal $\sqrt 3$. One then may define a colouring of the set of $N$ points according to this tesselation (for example, coloring ${i,j}$ if they are in triangles that share a common side) and try to obtain a good anticlique using properties of the graph obtained. An observation is that if two points are apart at a distance $1$ or more then they are in different triangles, but two points can be in different triangles but be arbitrarily close. In the colouring defined before, one can see that if there is a $6$-cycle $v_1\cdots v_6$ then for $w\in N(v_1)$, say, we have $w\notin N(v_i)$ for $i\neq 1$.

I am trying to figure out if some finer tesselation (perhaps one should consider the three equilateral subtriangles in each big triangle) or colouring should be used. I insist that the proof should be in the lines of Ramsey theory, colouring and similar combinatorial ideas.