A maximal cardinality subset of n lattice points so that all points in the subset have distance at least 4

Question

If we have some random set of $n$ lattice points what is the maximum cardinality of a subset in which all points have distance at least $4$ (or some other number). I really hope the best bound is not the trivial $n/16$. I'm not asking for a proof that this bound is the best possible, just provide the best bound you can.

Answer 1

I’ll try to provide a framework for the question. Let $d$ be a fixed distance $d$ (equal to $4$ in our case). A set $A’$ of lattice points we shall call $d$-separated, if any two distinct points of $B$ are placed at distance at least $d$. We are interested in a smallest $r=r(d)$ such that any finite set $A$ of lattice points has a $d$-separated subset $B$ of size at least $|A|/r$. I guess Empy2 obtained a bound $r\le 15$ by constructing a coloring of $\Bbb Z^2$ into $15$ colors such that each monochromatic subset is $d$-separated. Indeed, in this case as $B$ we can chose a largest monochromatic subset of $A$, which imply $|B|\ge |A|/15$ . Unfortunately, it can be easily shown that there is no such coloring in $14$ colors. (I’m going to write a proof later.) But this not imply that $r>14$, because a $d$-separated subset $B$ of $A$ may be chosen by different method. So there is sense to look for subsets $A$ of lattice points with the biggest ratio $|A|/|B|$, where $B$ is a maximal $d$-separated subset of $A$.

The following set has ratio $14$.

...
....
....
...

Are there subsets of lattice points with the bigger ratio?

Answer 2

From the $n\times n$ array, the following gives about $ n^2/15$, or one point in every fifteen.

$$x(3,3)+y(-1,4)$$