33
$\begingroup$

I'm trying to figure out the question in the title for a project that I'm working on.
My goal is to find a configuration of five integer points on the plane, where we can overlap any pair of them without it covering the other three points.

For $n=2$ it's trivial, for $n=3$ I believe any acute triangle works.
$n=4$ is slightly trickier, but still easily solvable: enter image description here

Unfortunately $n=5$ is exactly where I'm stuck on. From some doodling around it seems impossible, but maybe I'm missing something. It feels like any configuration of four will be equivalent to the one above, and I don't think there's any way to add another point to it, but I can't tell for sure.

If it is possible, what would be the "smallest" configuration that satisfies this restriction? In other words, the one with the smallest total bounding box.
In case it is not possible, a proof would be nice for closure, but if there's some "dumb" way to brute-force this it'd also be ok.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
51
$\begingroup$

One cannot arrange 5 points in that manner, even if the coordinates are allowed to be any real numbers.

Indeed, assume that the 5 points are $(x_n,y_n)$ with $x_1\leq\dotsb\leq x_5$. By the Erdős-Szekeres theorem, there are $1\leq i<j<k\leq 5$ such that either $y_i\leq y_j\leq y_k$ or $y_i\geq y_j\geq y_k$. In either case, any axis-parallel rectangle covering $(x_i,y_i)$ and $(x_k,y_k)$ will also cover $(x_j,y_j)$.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Recursively any $2^{2^{n-1}}+1$ points in $\mathbb{R}^n$ have some 3 points with monotonic coordinates. I wonder if it is sharp, are there some $2^{2^{n-1}}$ points no 3 of which have monotonic coordinates? It seems like a lot of points. $\endgroup$
    – Zach Teitler
    Commented Apr 26, 2022 at 23:41
  • 6
    $\begingroup$ @ZachTeitler: $2^{2^{n-1}}+1$ is sharp, and this was proved in 1973 independently by Burkill-Mirsky and Kalmanson. Check out the abstract of doi.org/10.37236/9880 $\endgroup$
    – GH from MO
    Commented Apr 27, 2022 at 3:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .