Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Ramsey-type results for semi-algebraic relations


Authors: David Conlon, Jacob Fox, János Pach, Benny Sudakov and Andrew Suk
Journal: Trans. Amer. Math. Soc. 366 (2014), 5043-5065
MSC (2010): Primary 14P10, 05D10
Published electronically: March 5, 2014
MathSciNet review: 3217709
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A $ k$-ary semi-algebraic relation $ E$ on $ \mathbb{R}^d$ is a subset of $ \mathbb{R}^{kd}$, the set of $ k$-tuples of points in $ \mathbb{R}^d$, which is determined by a finite number of polynomial inequalities in $ kd$ real variables. The description complexity of such a relation is at most $ t$ if $ d,k \leq t$ and the number of polynomials and their degrees are all bounded by $ t$. A set $ A\subset \mathbb{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 $ \mathbb{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 upon a direct application of Ramsey's theorem by one exponential and extends a result of Alon, Pach, Pinchasi, Radoičić, 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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 14P10, 05D10

Retrieve articles in all journals with MSC (2010): 14P10, 05D10


Additional Information

David Conlon
Affiliation: Mathematical Institute, University of Oxford, Oxford, OX1 3LB, United Kingdom
Email: david.conlon@maths.ox.ac.uk

Jacob Fox
Affiliation: Deparment of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: fox@math.mit.edu

János Pach
Affiliation: École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland — and — Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary
Email: pach@cims.nyu.edu

Benny Sudakov
Affiliation: Department of Mathematics, ETH, 8092 Zürich, Switzerland – and – Department of Mathematics, University of California, Los Angeles, Los Angeles, California 90095
Email: benjamin.sudakov@math.ethz.ch

Andrew Suk
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: asuk@math.mit.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-2014-06179-5
PII: S 0002-9947(2014)06179-5
Received by editor(s): January 1, 2013
Received by editor(s) in revised form: May 7, 2013
Published electronically: March 5, 2014
Additional Notes: The first author was supported by a Royal Society University Research Fellowship
The second author was supported by a Packard Fellowship, by a Simons Fellowship, by an Alfred P. Sloan Fellowship, by NSF grant DMS-1069197, and by an MIT NEC Corporation Award
The third author was supported by Swiss National Science Foundation Grants 200021-137574 and 200020-144531, by Hungarian Science Foundation Grant OTKA NN 102029 under the EuroGIGA programs ComPoSe and GraDR, and by NSF grant CCF-08-30272
The fourth author’s research was supported in part by NSF grant DMS-1101185 and by a USA-Israel BSF grant
The fifth author was supported by an NSF Postdoctoral Fellowship and by Swiss National Science Foundation Grant 200021-125287/1
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.