Back to Search
Start Over
Ramsey-type results for semi-algebraic relations
- Source :
- Scopus-Elsevier, arXiv, Symposium on Computational Geometry
- Publication Year :
- 2014
- Publisher :
- American Mathematical Society (AMS), 2014.
-
Abstract
- For natural numbers d and t there exists a positive C such that if F is a family of n[superscript C] semi-algebraic sets in R[superscript d] of description complexity at most t, then there is a subset F' of F of size $n$ such that either every pair of elements in F' intersect or the elements of F' are pairwise disjoint. This result, which also holds if the intersection relation is replaced by any semi-algebraic relation of bounded description complexity, was proved by Alon, Pach, Pinchasi, Radoicic, and Sharir and improves on a bound of 4[superscript n] for the family F which follows from a straightforward application of Ramsey's theorem. We extend this semi-algebraic version of Ramsey's theorem to k-ary relations and give matching upper and lower bounds for the corresponding Ramsey function, showing that it grows as a tower of height k-1. This improves on a direct application of Ramsey's theorem by one exponential. We apply this result 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.<br />Simons Foundation (Fellowship)<br />National Science Foundation (U.S.) (Grant DMS 1069197)<br />NEC Corporation (MIT Award)<br />National Science Foundation (U.S.) (Postdoctoral Fellowship)<br />Swiss National Science Foundation (Grant 200021-125287/1)
- Subjects :
- Matching (graph theory)
General Mathematics
Natural number
0102 computer and information sciences
Disjoint sets
Type (model theory)
01 natural sciences
Upper and lower bounds
Combinatorics
FOS: Mathematics
Mathematics - Combinatorics
0101 mathematics
Finite set
Mathematics
Discrete mathematics
Applied Mathematics
010102 general mathematics
Ramsey theory
Function (mathematics)
16. Peace & justice
Hyperplane
010201 computation theory & mathematics
Bounded function
Combinatorics (math.CO)
Ramsey's theorem
Order type
Subjects
Details
- ISSN :
- 10886850 and 00029947
- Volume :
- 366
- Database :
- OpenAIRE
- Journal :
- Transactions of the American Mathematical Society
- Accession number :
- edsair.doi.dedup.....4614090021570c27ae72abd078c578ae
- Full Text :
- https://doi.org/10.1090/s0002-9947-2014-06179-5