Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Erdős–Szekeres Theorems for Families of Convex Sets

  • Chapter
  • First Online:
New Trends in Intuitive Geometry

Part of the book series: Bolyai Society Mathematical Studies ((BSMS,volume 27))

Abstract

The well-known Erdős–Szekeres theorem states that every sufficiently large set of points in the plane containing no three points on a line, has a large subset in convex position. This classical result has been generalized in several directions. In this article we review recent progress related to one such direction, initiated by Bisztriczky and Fejes Tóth, in which the points are replaced by convex sets.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 99.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 129.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    A closely related concept is transitive colorings of ordered hypergraphs which was introduced by Eliáš and Matoušek [10], and was used for a different generalization of the “cup-cap” argument.

  2. 2.

    Other names for generalized configurations found in the literature are uniform rank 3 acyclic oriented matroids [6] or CC-systems [21]. See also the survey [15] for further information.

  3. 3.

    A slight warning may be in order: The basis for Suk’s argument is the positive fraction Erdős–Szekeres theorem, originally due to Bárány and Valtr [2]. Suk’s proof uses a quantitatively improved version due to Pór and Valtr [32], but their proof is essentially a counting argument and works just as well for generalized configurations!

  4. 4.

    Theorem 3.12 was announced by Pór and Valtr in [32] for the case of pairwise disjoint bodies, but their proof is complicated and appears only in an unpublished manuscript.

  5. 5.

    In [9] they use a different (but equivalent) encoding of the signature which is more useful for the proof. Since we do not discuss the details of the proof here, the current encoding will suffice.

References

  1. I. Bárány, G. Károlyi, Problems and results around the Erdős–Szekeres convex polygon theorem, in Discrete and computational geometry (Tokyo, 2000), Lecture Notes in Comput. Sci. (Springer, Berlin, 2001), pp. 91–105

    Chapter  Google Scholar 

  2. I. Bárány, P. Valtr, A positive fraction Erdős-Szekeres theorem. Discret. Comput. Geom. 19, 335–342 (1998)

    Article  Google Scholar 

  3. T. Bisztriczky, G. Fejes, Tóth, A generalization of the Erdős-Szekeres convex \(n\)-gon theorem. J. Reine Angew. Math. 395, 167–170 (1989)

    Google Scholar 

  4. T. Bisztriczky, G. Fejes, Tóth, Nine convex sets determine a pentagon with convex sets as vertices. Geom. Dedicata 31, 89–104 (1989)

    Article  MathSciNet  Google Scholar 

  5. T. Bisztriczky, G. Fejes Tóth, Convexly independent sets. Combinatorica 10, 195–202 (1990)

    Article  MathSciNet  Google Scholar 

  6. A. Björner, M.L. Vergnas, B. Sturmfels, N. White, G.M. Ziegler, Oriented Matroids, 2nd edn., Encyclopedia of Mathematics and its Applications (Cambridge University Press, Cambridge, 1999)

    Google Scholar 

  7. F.R.K. Chung, R.L. Graham, Forced convex \(n\)-gons in the plane. Discret. Comput. Geom. 19, 367–371 (1998)

    Google Scholar 

  8. M.G. Dobbins, A.F. Holmsen, A. Hubard, The Erdős-Szekeres problem for non-crossing convex sets. Mathematika 60, 463–484 (2014)

    Article  MathSciNet  Google Scholar 

  9. M.G. Dobbins, A.F. Holmsen, A. Hubard, Regular systems of paths and families of convex sets in convex position. Trans. Am. Math. Soc. 368, 3271–3303 (2016)

    Article  MathSciNet  Google Scholar 

  10. M. Eliáš, J. Matoušek, Higher-order Erdős-Szekeres theorems. Adv. Math. 244, 1–15 (2013)

    Article  MathSciNet  Google Scholar 

  11. P. Erdős, G. Szekeres, A combinatorial problem in geometry. Compositio Math. 2, 463–470 (1935)

    MathSciNet  MATH  Google Scholar 

  12. P. Erdős, G. Szekeres, On some extremum problems in elementary geometry. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3–4, 53–62 (1960/1961)

    Google Scholar 

  13. S. Felsner, P. Valtr, Coding and counting arrangements of pseudolines. Discret. Comput. Geom. 46, 405–416 (2011)

    Article  MathSciNet  Google Scholar 

  14. J. Fox, J. Pach, B. Sudakov, A. Suk, Erdős-Szekeres-type theorems for monotone paths and convex bodies. Proc. Lond. Math. Soc. 105, 953–982 (2012)

    Article  MathSciNet  Google Scholar 

  15. J.E. Goodman, Pseudoline arrangements, in Handbook of Discrete and Computational Geometry, 2nd edn. (CRC Press Ser. Discrete Math. Appl., FL, 2004), pp. 97–128

    Chapter  Google Scholar 

  16. J.E. Goodman, R. Pollack, On the combinatorial classification of nondegenerate configurations in the plane. J. Comb. Theory Ser. A 29, 220–235 (1980)

    Article  MathSciNet  Google Scholar 

  17. J.E. Goodman, R. Pollack, A combinatorial perspective on some problems in geometry, Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. I (Baton Rouge, La., 1981),vol. 32 (1981), pp. 383–394

    Google Scholar 

  18. J.E. Goodman, R. Pollack, Upper bounds for configurations and polytopes in \({ R}^d\). Discret. Comput. Geom. 1, 219–227 (1986)

    Google Scholar 

  19. A. Hubard, L. Montejano, E. Mora, A. Suk, Order types of convex bodies. Order 28, 121–130 (2011)

    Article  MathSciNet  Google Scholar 

  20. D.J. Kleitman, L. Pachter, Finding convex sets among points in the plane. Discret. Comput. Geom. 19, 405–410 (1998)

    Article  MathSciNet  Google Scholar 

  21. D.E. Knuth, Axioms and Hulls, Lecture Notes in Computer Science (Springer, Berlin, 1992)

    Book  Google Scholar 

  22. M. Lewin, A new proof of the Erdős-Szekeres theorem. Math. Gaz. 60, 136–138 (1976)

    Google Scholar 

  23. P.A. MacMahon, Combinatorial Analysis, Two volumes (bound as one) (Chelsea Publishing Co., New York, 1960)

    Google Scholar 

  24. H.N. Mojarrad, On the Erdős–Szekeres Conjecture (2015). arXiv:1510.06255

  25. H.N. Mojarrad, G. Vlachos, An improved upper bound for the Erdős-Szekeres Conjecture. Discret. Comput. Geom. 56, 165–180 (2016)

    Article  MathSciNet  Google Scholar 

  26. W. Morris, V. Soltan, The Erdős-Szekeres problem on points in convex position–a survey. Bull. Am. Math. Soc. 37, 437–458 (2000)

    Google Scholar 

  27. G. Moshkovitz, A. Shapira, Ramsey Theory, integer partitions and a new proof of the Erdős-Szekeres Theorem. Adv. Math. 262, 1107–1129 (2014)

    Article  MathSciNet  Google Scholar 

  28. S. Norin, Y. Yuditsky, Erdős-Szekeres without induction. Discret. Comput. Geom. 55, 963–971 (2016)

    Article  MathSciNet  Google Scholar 

  29. J. Pach, J. Solymosi, Canonical theorems for convex sets. Discret. Comput. Geom. 19, 427–435 (1998)

    Article  MathSciNet  Google Scholar 

  30. J. Pach, G. Tóth, A generalization of the Erdős-Szekeres theorem to disjoint convex sets. Discret. Comput. Geom. 19, 437–445 (1998)

    Article  Google Scholar 

  31. J. Pach, G. Tóth, Erdős-Szekeres-type theorems for segments and noncrossing convex sets. Geom. Dedicata 81, 1–12 (2000)

    Article  MathSciNet  Google Scholar 

  32. A. Pór, P. Valtr, The partitioned version of the Erdős-Szekeres theorem. Discret. Comput. Geom. 28, 625–637 (2002)

    Article  MathSciNet  Google Scholar 

  33. A. Pór, P. Valtr, On the positive fraction Erdős-Szekeres theorem for convex sets. Eur. J. Comb. 27, 1199–1205 (2006)

    Article  MathSciNet  Google Scholar 

  34. A. Suk, On the Erdős–Szekeres convex polygon problem. J. Am. Math. Soc. 30, 1047–1053 (2017). arXiv:1604.08657

    Article  Google Scholar 

  35. G. Szekeres, L. Peters, Computer solution to the 17-point Erdős-Szekeres problem. ANZIAM J. 48, 151–164 (2006)

    Article  MathSciNet  Google Scholar 

  36. G. Tóth, Finding convex sets in convex position. Combinatorica 20, 589–596 (2000)

    Article  MathSciNet  Google Scholar 

  37. G. Tóth, P. Valtr, Note on the Erdős-Szekeres theorem. Discret. Comput. Geom. 19, 457–459 (1998)

    Article  Google Scholar 

  38. G. Tóth, P. Valtr, The Erdős-Szekeres theorem: upper bounds and related results, Combinatorial and Computational Geometry, vol. 52 (Cambridge Univ. Press, Cambridge, 2005), pp. 557–568

    Google Scholar 

  39. G. Vlachos, On a conjecture of Erdős and Szekeres (2015). arXiv:1505.07549

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, KAIST Daejeon, Daejeon, South Korea

    Andreas F. Holmsen

Authors
  1. Andreas F. Holmsen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andreas F. Holmsen .

Editor information

Editors and Affiliations

  1. MTA Alfréd Rényi Institute of Mathematics, Budapest, Hungary

    Gergely Ambrus

  2. MTA Alfréd Rényi Institute of Mathematics, Budapest, Hungary

    Imre Bárány

  3. MTA Alfréd Rényi Institute of Mathematics, Budapest, Hungary

    Károly J. Böröczky

  4. MTA Alfréd Rényi Institute of Mathematics, Budapest, Hungary

    Gábor Fejes Tóth

  5. MTA Alfréd Rényi Institute of Mathematics, Budapest, Hungary

    János Pach

Rights and permissions

Reprints and permissions

Copyright information

© 2018 János Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Holmsen, A.F. (2018). Erdős–Szekeres Theorems for Families of Convex Sets. In: Ambrus, G., Bárány, I., Böröczky, K., Fejes Tóth, G., Pach, J. (eds) New Trends in Intuitive Geometry. Bolyai Society Mathematical Studies, vol 27. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-57413-3_9

Download citation

Publish with us

Policies and ethics

Search

Navigation