Ramseytype results for semialgebraic relations
Authors:
David Conlon, Jacob Fox, János Pach, Benny Sudakov and Andrew Suk
Journal:
Trans. Amer. Math. Soc. 366 (2014), 50435065
MSC (2010):
Primary 14P10, 05D10
Published electronically:
March 5, 2014
MathSciNet review:
3217709
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A ary semialgebraic relation on is a subset of , the set of tuples of points in , which is determined by a finite number of polynomial inequalities in real variables. The description complexity of such a relation is at most if and the number of polynomials and their degrees are all bounded by . A set is called homogeneous if all or none of the tuples from satisfy . A large number of geometric Ramseytype problems and results can be formulated as questions about finding large homogeneous subsets of sets in equipped with semialgebraic relations. In this paper, we study Ramsey numbers for ary semialgebraic relations of bounded complexity and give matching upper and lower bounds, showing that they grow as a tower of height . 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 . We apply our results to obtain new estimates for some geometric Ramseytype problems relating to order types and onesided sets of hyperplanes. We also study the offdiagonal case, achieving some partial results.
 [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), 10.1016/00973165(80)900308
 [2]
Noga
Alon, János
Pach, Rom
Pinchasi, Radoš
Radoičić, and Micha
Sharir, Crossing patterns of semialgebraic sets, J. Combin.
Theory Ser. A 111 (2005), no. 2, 310–326. MR 2156215
(2006k:14108), 10.1016/j.jcta.2004.12.008
 [3]
Noga
Alon and Joel
H. Spencer, The probabilistic method, 3rd ed.,
WileyInterscience 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 MarieFrançoise
Roy, Algorithms in real algebraic geometry, 2nd ed.,
Algorithms and Computation in Mathematics, vol. 10, SpringerVerlag,
Berlin, 2006. MR
2248869 (2007b:14125)
 [5]
Tom
Bohman, The trianglefree process, Adv. Math.
221 (2009), no. 5, 1653–1677. MR 2522430
(2010h:05271), 10.1016/j.aim.2009.02.018
 [6]
Tom
Bohman and Peter
Keevash, The early evolution of the 𝐻free process,
Invent. Math. 181 (2010), no. 2, 291–336. MR 2657427
(2011f:05285), 10.1007/s002220100247x
 [7]
B. Bukh and M. Matoušek, ErdősSzekerestype 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), 10.4007/annals.2009.170.941
 [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.1090/S0894034709006456
 [10]
David
Conlon, Jacob
Fox, and Benny
Sudakov, An improved bound for the steppingup lemma, Discrete
Appl. Math. 161 (2013), no. 9, 1191–1196. MR
3030610, 10.1016/j.dam.2010.10.013
 [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, 10.1145/1998196.1998215
 [12]
M. Eliáš and J. Matoušek, Higherorder ErdősSzekeres theorems, in Proc. 28th ACM Symposium on Computational Geometry (2012), 8190.
 [13]
P.
Erdös, Some remarks on the theory of
graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294. MR 0019911
(8,479d), 10.1090/S000299041947087851
 [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, Compositio
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ősSzekerestype theorems for monotone paths and
convex bodies, Proc. Lond. Math. Soc. (3) 105 (2012),
no. 5, 953–982. MR
2997043, 10.1112/plms/pds018
 [19]
P.
Frankl and R.
M. Wilson, Intersection theorems with geometric consequences,
Combinatorica 1 (1981), no. 4, 357–368. MR 647986
(84g:05085), 10.1007/BF02579457
 [20]
Ronald
L. Graham, Bruce
L. Rothschild, and Joel
H. Spencer, Ramsey theory, 2nd ed., WileyInterscience Series
in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New
York, 1990. A WileyInterscience Publication. MR 1044995
(90m:05003)
 [21]
Jeong
Han Kim, The Ramsey number 𝑅(3,𝑡) has order of
magnitude 𝑡²/log𝑡, Random Structures Algorithms
7 (1995), no. 3, 173–207. MR 1369063
(96m:05140), 10.1002/rsa.3240070302
 [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), 10.1016/01966774(92)900214
 [23]
J.
Milnor, On the Betti numbers of real
varieties, Proc. Amer. Math. Soc. 15 (1964), 275–280. MR 0161339
(28 #4547), 10.1090/S00029939196401613399
 [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. S230, no. 1, 264. MR
1576401, 10.1112/plms/s230.1.264
 [26]
Joel
Spencer, Turán’s theorem for 𝑘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)
 [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, 354360. MR 600598 (82a:05064), http://dx.doi.org/10.1016/00973165(80)900308
 [2]
 Noga Alon, János Pach, Rom Pinchasi, Radoš Radoičić, and Micha Sharir, Crossing patterns of semialgebraic sets, J. Combin. Theory Ser. A 111 (2005), no. 2, 310326. MR 2156215 (2006k:14108), http://dx.doi.org/10.1016/j.jcta.2004.12.008
 [3]
 Noga Alon and Joel H. Spencer, The probabilistic method, 3rd ed., WileyInterscience 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 MarieFrançoise Roy, Algorithms in real algebraic geometry, 2nd ed., Algorithms and Computation in Mathematics, vol. 10, SpringerVerlag, Berlin, 2006. MR 2248869 (2007b:14125)
 [5]
 Tom Bohman, The trianglefree process, Adv. Math. 221 (2009), no. 5, 16531677. MR 2522430 (2010h:05271), http://dx.doi.org/10.1016/j.aim.2009.02.018
 [6]
 Tom Bohman and Peter Keevash, The early evolution of the free process, Invent. Math. 181 (2010), no. 2, 291336. MR 2657427 (2011f:05285), http://dx.doi.org/10.1007/s002220100247x
 [7]
 B. Bukh and M. Matoušek, ErdősSzekerestype 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, 941960. MR 2552114 (2011i:05146), http://dx.doi.org/10.4007/annals.2009.170.941
 [9]
 David Conlon, Jacob Fox, and Benny Sudakov, Hypergraph Ramsey numbers, J. Amer. Math. Soc. 23 (2010), no. 1, 247266. MR 2552253 (2010m:05192), http://dx.doi.org/10.1090/S0894034709006456
 [10]
 David Conlon, Jacob Fox, and Benny Sudakov, An improved bound for the steppingup lemma, Discrete Appl. Math. 161 (2013), no. 9, 11911196. MR 3030610, http://dx.doi.org/10.1016/j.dam.2010.10.013
 [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. 117124. MR 2919602, http://dx.doi.org/10.1145/1998196.1998215
 [12]
 M. Eliáš and J. Matoušek, Higherorder ErdősSzekeres theorems, in Proc. 28th ACM Symposium on Computational Geometry (2012), 8190.
 [13]
 P. Erdös, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292294. 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), 93196. 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), 417439. MR 0065615 (16,455d)
 [16]
 P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compos. Math. 2 (1935), 463470. 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), 4983. MR 2983197
 [18]
 Jacob Fox, János Pach, Benny Sudakov, and Andrew Suk, ErdősSzekerestype theorems for monotone paths and convex bodies, Proc. Lond. Math. Soc. (3) 105 (2012), no. 5, 953982. MR 2997043, http://dx.doi.org/10.1112/plms/pds018
 [19]
 P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357368. MR 647986 (84g:05085), http://dx.doi.org/10.1007/BF02579457
 [20]
 Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, 2nd ed., WileyInterscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., New York, 1990. A WileyInterscience Publication. MR 1044995 (90m:05003)
 [21]
 Jeong Han Kim, The Ramsey number has order of magnitude , Random Structures Algorithms 7 (1995), no. 3, 173207. MR 1369063 (96m:05140), http://dx.doi.org/10.1002/rsa.3240070302
 [22]
 Jiří Matoušek and Emo Welzl, Good splitters for counting points in triangles, J. Algorithms 13 (1992), no. 2, 307319. MR 1160056 (93m:68173), http://dx.doi.org/10.1016/01966774(92)900214
 [23]
 J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275280. 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), 389402 (Russian). MR 0034600 (11,613h)
 [25]
 F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. S230, no. 1, 264. MR 1576401, http://dx.doi.org/10.1112/plms/s230.1.264
 [26]
 Joel Spencer, Turán's theorem for graphs, Discrete Math. 2 (1972), 183186. 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. 255265 (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
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/S000299472014061795
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 DMS1069197, and by an MIT NEC Corporation Award
The third author was supported by Swiss National Science Foundation Grants 200021137574 and 200020144531, by Hungarian Science Foundation Grant OTKA NN 102029 under the EuroGIGA programs ComPoSe and GraDR, and by NSF grant CCF0830272
The fourth author’s research was supported in part by NSF grant DMS1101185 and by a USAIsrael BSF grant
The fifth author was supported by an NSF Postdoctoral Fellowship and by Swiss National Science Foundation Grant 200021125287/1
Article copyright:
© Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
