Ramsey-type results for semi-algebraic relations

DOI10.1145/2462356.2462399MaRDI QIDQ5174491zbMATH OpenOpenAlexFDO

Authors David Conlon, Jacob Fox, János Pach, Andrew Suk, Benny Sudakov

Publication date 17 February 2015

Published in Proceedings of the twenty-ninth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.0074, https://resolver.caltech.edu/CaltechAUTHORS:20190812-163000075

zbMATH Keywords

hypergraphsRamsey theorysemi-algebraic sets

Mathematics Subject Classification ID

Hypergraphs (05C65) Ramsey theory (05D10) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: A k-ary semi-algebraic relation E on R^d is a subset of R^{kd}, the set of k-tuples of points in R^d, which is determined by a finite number of polynomial equations and inequalities in kd real variables. The description complexity of such a relation is at most t if the number of polynomials and their degrees are all bounded by t. A subset A of R^d is called homogeneous if all or none of the k-tuples from A satisfy E. A large number of geometric Ramsey-type problems and results can be formulated as questions about finding large homogeneous subsets of sets in R^d equipped with semi-algebraic relations. In this paper we study Ramsey numbers for k-ary semi-algebraic relations of bounded complexity and give matching upper and lower bounds, showing that they grow as a tower of height k-1. This improves on a direct application of Ramsey's theorem by one exponential and extends a result of Alon, Pach, Pinchasi, Radoiv{c}i'c, and Sharir, who proved this for k=2. We apply our results to obtain new estimates for some geometric Ramsey-type problems relating to order types and one-sided sets of hyperplanes. We also study the off-diagonal case, achieving some partial results.

Recommendations

• Ramsey-type results for semi-algebraic relations
• Semi-algebraic Ramsey numbers
• Semi-algebraic Ramsey numbers
• Crossing patterns of semi-algebraic sets
• Ramsey numbers of semi-algebraic and semi-linear hypergraphs

Cited in

(9)

• Higher-order Erdős-Szekeres theorems
• Crossing patterns of semi-algebraic sets
• Ramsey-type results for semi-algebraic relations
• On dual Ramsey theorems for relational structures
• scientific article; zbMATH DE number 5014478 (Why is no real title available?)
• Ramsey-type theorems for sets satisfying a geometric regularity condition
• Semi-algebraic Ramsey numbers
• Ramsey-Turán numbers for semi-algebraic graphs
• Semi-algebraic Ramsey numbers

This page was built for publication: Ramsey-type results for semi-algebraic relations

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