Longest convex lattice chains (Q390150): Difference between revisions

Let \(T\) be a triangle in the plane having two fixed vertices \(v_0,v_1\in{\mathbb Z}^2\), the integer lattice. A convex lattice chain in \(T\) (from \(v_0\) to \(v_1\)) of length \(n\) is a subset of points \(p_0,p_1,\dots,p_n\in{\mathbb Z}^2\cap T\) such that \(p_0=v_0\), \(p_n=v_1\) and the vertices of the convex hull \(\text{conv}\{p_0,\dots,p_n\}\) are precisely \(p_0,\dots,p_n\). Denoting by \(\ell(T)\) the largest \(n\) such that \(T\) contains a convex lattice chain of length \(n\), the authors study the maximum value of \(\ell(T)\) when the area \(|T|\) is given. More precisely, it is proved that there exists \(t_0>0\) such that if \(|T|>t_0\) then \[ \frac{1}{8}\bigl(\ell(T)-1\bigr)\ell(T)^2\leq|T|. \] Another bound on \(\ell(T)\) in terms of the lattice width is also obtained.