Type: Article

Lower Bounds on Geometric Ramsey Functions

Elias, Marek; Matousek, Jiri; Roldán-Pensado, Edgardo; Safernova;

Abstract:

The classical theorem of Ramsey claims that, for every k and n, there exists N?N such that if the set of k-tuples of elements of an N-element set X is colored by two colors, then there exists an n-element homogeneous Y?X with all k-tuples of Y having the same color. There exist results and conjectures for bounding from below and from above the smallest number Rk(n) among the N's having this property, which involves the tower function twrk(x) defined by twr1(x)=x and twri+1(x)=2twri(x). The present paper is devoted to the study of semialgebraic colorings. Recall that a k-ary d-dimensional semialgebraic predicate ?(x1,…,xk) is a Boolean combination of polynomial equations and inequalities in the xi,j: there is a Boolean formula ?(X1,…,Xt) in Boolean variables X1,…,Xt and polynomials f1,…,ft in the variables xi,j, 1?i?k, 1?j?d, such that ?(x1,…,xk)=?(A1,…,Ak), where A? is true if f?(x1,1,…,xk,d)?0 and false otherwise. A sequence (p1,…,pn) of points in Rd is ?-homogeneous if either ?(pi1,…,pik) holds for every choice 1?i1<?<ik?n, or it holds for no such choice. The Ramsey function R?(n) is the smallest N such that every point sequence of length N contains a ?-homogeneous subsequence of length n. Bounds are already known for the function R?(n). A nice result of the present paper, which improves results from former works, states that for every d?2 there is a d-dimensional semialgebraic predicate ? of arity k=d+3 such that R?(n)?twrk?1(?(n)) (where f(n)=?(g(n)) means g(n)=O(f(n))). The authors also provide a natural geometric Ramsey-type theorem with a large Ramsey function. They call a point sequence P in Rd order-type homogeneous if all (d+1)-tuples in P have the same orientation. Every sufficiently long point sequence in general position in Rd contains an order-type homogeneous subsequence of length n, and they give a lower bound for the corresponding Ramsey function. An interesting remark is made, which connects the notion of n-point order type homogeneous sequence and the notion of real Chebyshev system (that is, a system of continuous real functions f0,f1,…,fk:A?R, where A is linearly ordered, such that for every choice of elements t0<t1<?<tk in A, the matrix (fi(tj))i,j=0,…,k has a strictly positive determinant).