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)

 
 

 

Regular systems of paths and families of convex sets in convex position


Authors: Michael Gene Dobbins, Andreas F. Holmsen and Alfredo Hubard
Journal: Trans. Amer. Math. Soc. 368 (2016), 3271-3303
MSC (2010): Primary 05D10, 52C10; Secondary 52C30
DOI: https://doi.org/10.1090/tran/6437
Published electronically: July 14, 2015
MathSciNet review: 3451877
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we show that every sufficiently large family of convex bodies in the plane has a large subfamily in convex position provided that the number of common tangents of each pair of bodies is bounded and every subfamily of size five is in convex position. (If each pair of bodies has at most two common tangents it is enough to assume that every triple is in convex position, and likewise, if each pair of bodies has at most four common tangents it is enough to assume that every quadruple is in convex position.) This confirms a conjecture of Pach and Tóth and generalizes a theorem of Bisztriczky and Fejes Tóth. Our results on families of convex bodies are consequences of more general Ramsey-type results about the crossing patterns of systems of graphs of continuous functions $ f : [0,1]\to \mathbb{R}$. On our way towards proving the Pach-Tóth conjecture we obtain a combinatorial characterization of such systems of graphs in which all subsystems of equal size induce equivalent crossing patterns. These highly organized structures are what we call regular systems of paths, and they are natural generalizations of the notions of cups and caps from the famous theorem of Erdős and Szekeres. The characterization of regular systems is combinatorial and introduces some auxiliary structures which may be of independent interest.


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

  • [1] Imre Bárány and Gyula Károlyi, Problems and results around the Erdős-Szekeres convex polygon theorem, Discrete and computational geometry (Tokyo, 2000) Lecture Notes in Comput. Sci., vol. 2098, Springer, Berlin, 2001, pp. 91-105. MR 2043640, https://doi.org/10.1007/3-540-47738-1_7
  • [2] T. Bisztriczky and G. Fejes Tóth, A generalization of the Erdős-Szekeres convex $ n$-gon theorem, J. Reine Angew. Math. 395 (1989), 167-170. MR 983064 (90b:52005), https://doi.org/10.1515/crll.1989.395.167
  • [3] T. Bisztriczky and G. Fejes Tóth, Convexly independent sets, Combinatorica 10 (1990), no. 2, 195-202. MR 1082649 (92c:52005), https://doi.org/10.1007/BF02123010
  • [4] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler, Oriented matroids, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge University Press, Cambridge, 1999. MR 1744046 (2000j:52016)
  • [5] Michael Gene Dobbins, Andreas Holmsen, and Alfredo Hubard, The Erdős-Szekeres problem for non-crossing convex sets, Mathematika 60 (2014), no. 2, 463-484. MR 3229499, https://doi.org/10.1112/S0025579314000072
  • [6] Herbert Edelsbrunner and Leonidas J. Guibas, Topologically sweeping an arrangement, 18th Annual ACM Symposium on Theory of Computing (Berkeley, CA, 1986), J. Comput. System Sci. 38 (1989), no. 1, 165-194. MR 990055 (91d:68124), https://doi.org/10.1016/0022-0000(89)90038-X
  • [7] P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463-470. MR 1556929
  • [8] P. Erdős and G. Szekeres, On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3-4 (1960/1961), 53-62. MR 0133735 (24 #A3560)
  • [9] 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, https://doi.org/10.1112/plms/pds018
  • [10] Jacob E. Goodman, Proof of a conjecture of Burr, Grünbaum, and Sloane, Discrete Math. 32 (1980), no. 1, 27-35. MR 588905 (82b:51005), https://doi.org/10.1016/0012-365X(80)90096-5
  • [11] Jacob E. Goodman, Pseudoline arrangements, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 83-109. MR 1730161
  • [12] H. Groemer, Geometric applications of Fourier series and spherical harmonics, Encyclopedia of Mathematics and its Applications, vol. 61, Cambridge University Press, Cambridge, 1996. MR 1412143 (97j:52001)
  • [13] Alfredo Hubard, Luis Montejano, Emiliano Mora, and Andrew Suk, Order types of convex bodies, Order 28 (2011), no. 1, 121-130. MR 2774044 (2012c:52005), https://doi.org/10.1007/s11083-010-9156-2
  • [14] W. Morris and V. Soltan, The Erdős-Szekeres problem on points in convex position--a survey, Bull. Amer. Math. Soc. (N.S.) 37 (2000), no. 4, 437-458 (electronic). MR 1779413 (2001e:52030), https://doi.org/10.1090/S0273-0979-00-00877-6
  • [15] J. Pach and G. Tóth, A generalization of the Erdős-Szekeres theorem to disjoint convex sets, Dedicated to the memory of Paul Erdős, Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 437-445. MR 1608885 (99b:52038), https://doi.org/10.1007/PL00009361
  • [16] János Pach and Géza Tóth, Erdős-Szekeres-type theorems for segments and noncrossing convex sets, Geom. Dedicata 81 (2000), no. 1-3, 1-12. MR 1772191 (2001g:52027), https://doi.org/10.1023/A:1005210202899
  • [17] George Szekeres and Lindsay Peters, Computer solution to the 17-point Erdős-Szekeres problem, ANZIAM J. 48 (2006), no. 2, 151-164. MR 2291511 (2008a:52022), https://doi.org/10.1017/S144618110000300X
  • [18] Géza Tóth and Pavel Valtr, The Erdős-Szekeres theorem: upper bounds and related results, Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 557-568. MR 2178339 (2006k:52044)
  • [19] Géza Tóth, Finding convex sets in convex position, Combinatorica 20 (2000), no. 4, 589-596. MR 1804829 (2002c:52021), https://doi.org/10.1007/s004930070010

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05D10, 52C10, 52C30

Retrieve articles in all journals with MSC (2010): 05D10, 52C10, 52C30


Additional Information

Michael Gene Dobbins
Affiliation: Department of Mathematical Sciences, Binghamton University SUNY, Binghamton, New York 13902 – and – GAIA, Postech, Pohang, South Korea
Email: dobbins@postech.ac.kr

Andreas F. Holmsen
Affiliation: Department of Mathematical Sciences, KAIST, Daejeon, South Korea
Email: andreash@kaist.edu

Alfredo Hubard
Affiliation: Laboratoire de l’Institut Gaspard Monge, Université Paris-Est Marne-la-Vallée, Paris, France – and – GEOMETRICA, Inria Sophia-Antipolos, France
Email: alfredo.hubard@inria.fr

DOI: https://doi.org/10.1090/tran/6437
Received by editor(s): June 28, 2013
Received by editor(s) in revised form: February 28, 2014
Published electronically: July 14, 2015
Additional Notes: The first author was supported by NRF grant 2011-0030044 funded by the government of South Korea (SRC-GAIA) and BK21
The second author was supported by Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Education, Science and Technology (NRF-2010-0021048)
The third author was supported by Fondation Sciences Mathématiques de Paris and would like to thank KAIST for their hospitality and support during his visit
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society