8
$\begingroup$

The following combinatorial question came up while trying to prove a lemma for my research. Let $[N]$ denote the $N\times N$ grid inside the integer lattice $\mathbb{Z}\times\mathbb{Z}.$ The square corresponding to $(z_1,z_2)\in\mathbb{Z}\times\mathbb{Z}$ is $[z_1-\frac{1}{2},z_1+\frac{1}{2}]\times [z_2-\frac{1}{2},z_2+\frac{1}{2}]\subset\mathbb{R}\times\mathbb{R}.$ If $x\in\mathbb{Z}\times\mathbb{Z},$ denote the corresponding square by $S(x).$

Definition An acute three-tuple $\left\{x_1,x_2,x_3\right\}$ is a collection of three elements $x_i\in \mathbb{Z}\times \mathbb{Z}$ so that for every choice of $y_1\in S(x_1),$ $y_2\in S(x_2),$ and $y_3\in S(x_3),$ the triangle with vertices $y_1, y_2,$ and $y_3$ is acute.

Let $\lambda(N)$ be the size of the largest subset of $[N]$ with no acute three-tuple.

Question Is $\lambda(N) = O(N^{1+\epsilon})$ for all $\epsilon>0$?

I have shown that $\lambda(N) = O(N^{1.5}),$ but the argument is not easily strengthenable.

I initially posted this on stackexchange, and did not get an answer: https://math.stackexchange.com/questions/2356166/stable-acute-triangles-in-a-grid

$\endgroup$
  • $\begingroup$ I wonder if there might be ideas that help in this paper: Bevan, David. "Sets of points determining only acute angles and some related colouring problems." The Electronic Journal of Combinatorics 13.1 (2006): R12. PDF download. $\endgroup$ – Joseph O'Rourke Jul 15 '17 at 17:56
  • 1
    $\begingroup$ Do you have examples where the number of points grows faster than $N$? $\endgroup$ – Anthony Quas Jul 16 '17 at 5:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.