Around Erdős-Szekeres problems (Q736016): Difference between revisions

A classic theorem of Erdős and Szekeres asserts that for every \(n\geq 3\), there exists a smallest number \(g(n)\) such that any \(g(n)\) points in the plane in general position (i.e., no 3 collinear) contain the vertices of a convex \(n\)-gon. \textit{A. Bialostocki, P. Dieker} and \textit{B. Voxman} [Discrete Math. 91, 231--238 (1991; Zbl 0769.52014)] suggested the following variant of the Erdős-Szekeres problem: Given arbitrary integer \(n\geq 4\) and \(q\geq 2\), find the smallest positive integer \(h(n, \text{mod} q)\), such that any planar point set \(H\) in general position, of at least \(h(n, \text{mod} q)\) points, contains a subset of cardinality \(n\), whose elements are the vertices of a convex \(n\)-gon \(C\), such that the number of points of \(H\) in the interior of \(C\) is a multiple of \(q\). The paper proves the following new results: (1) If \(n\geq 2q-1\), then \(h(n,\text{mod} q) \leq g(4+(n-4)q)\); (2) If \(n\geq q+2\) and \(q\) is even, then \(h(n,\text{mod} q) \leq R_q^3(n,n,\dots ,n)\); (3) If \(n\geq q+2\) and \(q\) is odd, then \(h(n,\text{mod} q) \leq R_q^3(g(n),n,n,\dots ,n)\). (\(R_k^p\) refers to Ramsey numbers for \(k\)-coloring \(p\)-tuples.)