1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Do you think it's possible to achieve $n^2/14$? That was actually a bound I was hoping for to solve a problem which led me to this question. The problem says that it's always possible to choose a subset of a set of unit circles having area $S$ so that the area of a chosen subset is at least $2S/9$. If you use a well-known result saying that for a figure of area $S$ it's always possible to set a coordinate system so that the figure contains at least $S$ lattice points it quickly becomes clear that a bound of $n^2/14$ would solve the problem. $\endgroup$ – mr. clock Dec 4 '18 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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