A NOTE ON ORDER-TYPE HOMOGENEOUS POINT SETS

作者：Suk Andrew^*

来源：Mathematika, 2014, 60(1): 37-42.

DOI：10.1112/S0025579313000247

Let OTd(n) be the smallest integer N such that every N-element point sequence in R-d in general position contains an order-type homogeneous subset of size n, where a set is order-type homogeneous if all (d + 1)-tuples from this set have the same orientation. It is known that a point sequence in R-d that is order-type homogeneous, forms the vertex set of a convex polytope that is combinatorially equivalent to a cyclic polytope in R-d. Two famous theorems of Erdos and Szekeres from 1935 imply that OT1(n) = Theta(n(2)) and OT2(n) = 2(Theta(n)). For d >= 3, we give new bounds for OTd(n). In particular, we show that OT3(n) = 22(Theta(n)), answering a question of Elias and Matousek, and, for d >= 4, we show that OTd(n) is bounded above by an exponential tower of height d with O(n) in the topmost exponent.

• 出版日期2014-1