®®®® SIIA Público

Título del libro: Proceedings Of The Annual Symposium On Computational Geometry
Título del capítulo: Lower bounds on geometric Ramsey functions

Autores UNAM:
EDGARDO ROLDAN PENSADO;
Autores externos:

Idioma:
Inglés
Año de publicación:
2014
Palabras clave:

Polynomials; Towers; Arbitrary height; Boolean combinations; Lower bounds; Order types; Polynomial equation; Ramsey function; Ramsey theory; Semialgebraic predicate; Computational geometry


Resumen:

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in Rd. A k-ary semialgebraic predicatef(x1,.., xk) on Rd is a Boolean combination of polynomial equations and inequalities in the kd coordinates of k points x1,.., xk 2 Rd. A sequence P = (p1,., pn) of points in Rd is called f-homogeneous if eitherf(pi1,.., pik ) holds for all choices 1< i1 =? < ik= n, or it holds for no such choice. The Ramsey function Rf(n) is the smallest N such that every point sequence of length N contains a f-homogeneous subsequence of length n. Conlon, Fox, Pach, Sudakov, and Suk constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function of arbitrary height: for every ?= 4, they exhibit a ?-ary f in dimension 2?-4 with Rf bounded below by a tower of height ? - 1. We reduce the dimension in their construction, obtaining a k-ary semialgebraic predicate f on R?-3 with R f bounded below by a tower of height ? - 1. We also provide a natural geometric Ramsey-type theorem with a large Ramsey function. We call a point sequence P in Rd order-type homogeneous if all (d + 1)-tuples in P have the same orientation. Every suficiently long point se quence in general position in Rd contains an order-type homogeneous subsequence of length n, and the corresponding Ramsey function has recently been studied in several papers. Together with a recent work of Bárány, Matou?ek, and Pór, our results imply a tower function of (n) of height d as a lower bound, matching an upper bound by Suk up to the constant in front of n. Copyright is held by the owner/author(s).


Entidades citadas de la UNAM: