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


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