Lower bounds on geometric Ramsey functions

DOI10.1145/2582112.2582146zbMATH Open1395.05180arXiv1307.5157OpenAlexW2038378199MaRDI QIDQ4635583FDOQ4635583

Authors: Marek Eliáš, Edgardo Roldán-Pensado, Zuzana Safernova, Jiří Matoušek 

Publication date: 23 April 2018

Published in: SIAM Journal on Discrete Mathematics, Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in $mathbb{R}^d$. A $k$-ary semialgebraic predicate $Phi(x_1,ldots,x_k)$ on $mathbb{R}^d$ is a Boolean combination of polynomial equations and inequalities in the $kd$ coordinates of $k$ points $x_1,ldots,x_{k}inmathbb{R}^d$. A sequence $P=(p_1,ldots,p_n)$ of points in $mathbb{R}^d$ is called $Phi$-homogeneous if either $Phi(p_{i_1},ldots,p_{i_k})$ holds for all choices $1le{i}_1<cdots<i_{k}len$, or it holds for no such choice. The Ramsey function $R_{P}hi(n)$ is the smallest $N$ such that every point sequence of length $N$ contains a $Phi$-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 $kge4$, they exhibit a $k$-ary $Phi$ in dimension $2^{k-4}$ with $R_{P}hi$ bounded below by a tower of height $k-1$. We reduce the dimension in their construction, obtaining a $k$-ary semialgebraic predicate $Phi$ on $mathbb{R}^{k-3}$ with $R_{P}hi$ bounded below by a tower of height $k-1$. We also provide a natural geometric Ramsey-type theorem with a large Ramsey function. We call a point sequence $P$ in $mathbb{R}^d$ order-type homogeneous if all $(d+1)$-tuples in $P$ have the same orientation. Every sufficiently long point sequence in general position in $mathbb{R}^d$ 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'ar'any, Matouv{s}ek, and P'or, our results imply a tower function of $Omega(n)$ of height $d$ as a lower bound, matching an upper bound by Suk up to the constant in front of $n$.

Full work available at URL: https://arxiv.org/abs/1307.5157

Recommendations

• Some geometric structures and bounds for Ramsey numbers
• Lower bounds for lower Ramsey numbers
• scientific article; zbMATH DE number 26869
• Improved upper and lower bounds on a geometric Ramsey problem
• A lower bound for certain Ramsey type problems
• scientific article; zbMATH DE number 2237376
• Lower bounds for some Ramsey numbers
• Bounding some Ramsey functions
• Lower bounds for hypergraph Ramsey numbers

zbMATH Keywords

Ramsey theoryorder typeRamsey functionsemialgebraic predicatesuper order typesuperorder-type

Mathematics Subject Classification ID

Ramsey theory (05D10) Semialgebraic sets and related spaces (14P10)

This page was built for publication: Lower bounds on geometric Ramsey functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635583)