Remote Access Transactions of the American Mathematical Society
Green Open Access

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?)

  • [1] Miklós Ajtai, János Komlós, and Endre Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980), no. 3, 354-360. MR 600598 (82a:05064),
  • [2] Noga Alon, János Pach, Rom Pinchasi, Radoš Radoičić, and Micha Sharir, Crossing patterns of semi-algebraic sets, J. Combin. Theory Ser. A 111 (2005), no. 2, 310-326. MR 2156215 (2006k:14108),
  • [3] Noga Alon and Joel H. Spencer, The probabilistic method, 3rd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., Hoboken, NJ, 2008. With an appendix on the life and work of Paul Erdős. MR 2437651 (2009j:60004)
  • [4] Saugata Basu, Richard Pollack, and Marie-Françoise Roy, Algorithms in real algebraic geometry, 2nd ed., Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006. MR 2248869 (2007b:14125)
  • [5] Tom Bohman, The triangle-free process, Adv. Math. 221 (2009), no. 5, 1653-1677. MR 2522430 (2010h:05271),
  • [6] Tom Bohman and Peter Keevash, The early evolution of the $ H$-free process, Invent. Math. 181 (2010), no. 2, 291-336. MR 2657427 (2011f:05285),
  • [7] B. Bukh and M. Matoušek, Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1, preprint, arXiv:1207.0705.
  • [8] David Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of Math. (2) 170 (2009), no. 2, 941-960. MR 2552114 (2011i:05146),
  • [9] David Conlon, Jacob Fox, and Benny Sudakov, Hypergraph Ramsey numbers, J. Amer. Math. Soc. 23 (2010), no. 1, 247-266. MR 2552253 (2010m:05192),
  • [10] David Conlon, Jacob Fox, and Benny Sudakov, An improved bound for the stepping-up lemma, Discrete Appl. Math. 161 (2013), no. 9, 1191-1196. MR 3030610,
  • [11] Vida Dujmović and Stefan Langerman, A center transversal theorem for hyperplanes and applications to graph drawing, Computational geometry (SCG'11), ACM, New York, 2011, pp. 117-124. MR 2919602,
  • [12] M. Eliáš and J. Matoušek, Higher-order Erdős-Szekeres theorems, in Proc. 28th ACM Symposium on Computational Geometry (2012), 81-90.
  • [13] P. Erdös, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292-294. MR 0019911 (8,479d)
  • [14] P. Erdős, A. Hajnal, and R. Rado, Partition relations for cardinal numbers, Acta Math. Acad. Sci. Hungar. 16 (1965), 93-196. MR 0202613 (34 #2475)
  • [15] P. Erdős and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc. (3) 2 (1952), 417-439. MR 0065615 (16,455d)
  • [16] P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compos. Math. 2 (1935), 463-470. MR 1556929
  • [17] Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and János Pach, Overlap properties of geometric expanders, J. Reine Angew. Math. 671 (2012), 49-83. MR 2983197
  • [18] Jacob Fox, János Pach, Benny Sudakov, and Andrew Suk, Erdős-Szekeres-type theorems for monotone paths and convex bodies, Proc. Lond. Math. Soc. (3) 105 (2012), no. 5, 953-982. MR 2997043,
  • [19] P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357-368. MR 647986 (84g:05085),
  • [20] Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., New York, 1990. A Wiley-Interscience Publication. MR 1044995 (90m:05003)
  • [21] Jeong Han Kim, The Ramsey number $ R(3,t)$ has order of magnitude $ t^2/\log t$, Random Structures Algorithms 7 (1995), no. 3, 173-207. MR 1369063 (96m:05140),
  • [22] Jiří Matoušek and Emo Welzl, Good splitters for counting points in triangles, J. Algorithms 13 (1992), no. 2, 307-319. MR 1160056 (93m:68173),
  • [23] J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275-280. MR 0161339 (28 #4547)
  • [24] I. G. Petrovskiĭ and O. A. Oleĭnik, On the topology of real algebraic surfaces, Izvestiya Akad. Nauk SSSR. Ser. Mat. 13 (1949), 389-402 (Russian). MR 0034600 (11,613h)
  • [25] F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. S2-30, no. 1, 264. MR 1576401,
  • [26] Joel Spencer, Turán's theorem for $ k$-graphs, Discrete Math. 2 (1972), 183-186. MR 0297614 (45 #6668)
  • [27] René Thom, Sur l'homologie des variétés algébriques réelles, Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), Princeton Univ. Press, Princeton, N.J., 1965, pp. 255-265 (French). MR 0200942 (34 #828)

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

Jacob Fox
Affiliation: Deparment of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

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

Benny Sudakov
Affiliation: Department of Mathematics, ETH, 8092 Zürich, Switzerland – and – Department of Mathematics, University of California, Los Angeles, Los Angeles, California 90095

Andrew Suk
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

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.

American Mathematical Society