UVictoria Discrete Math Seminar: Gary MacGillivray

A 1935 problem of Erdos and Szekeres asks for the smallest number, r(n), such that given any collection of r(n) points in the plane there exist n points no 3 of which are the vertices of a right triangle. It is known that r(4) = 8, 9, or 10, and in general r(n) \leq 1 + (n-1)^2. We ask for the smallest number, T(n), such that given any collection of T(n) lattice points there exist n lattice points no 3 of which are the vertices of a right triangle with legs parallel to the coordinate axes. It is clear that T(n) \leq r(n). We show that T(n) = 1 + \lfloor (n^2 + 1) / 4 \rfloor, which in turn implies that r(n) = \Theta(n^2). This is an old paper with Sheila Ferneyhough, Denis Hanson and Ruth Haas.