REGULAR SYSTEMS OF PATHS AND FAMILIES OF CONVEX SETS IN CONVEX POSITION

Cited 3 time in webofscience Cited 0 time in scopus
  • Hit : 262
  • Download : 0
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 Toth and generalizes a theorem of Bisztriczky and Fejes Toth. 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] -> R. On our way towards proving the Pach-Toth 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 Erdos and Szekeres. The characterization of regular systems is combinatorial and introduces some auxiliary structures which may be of independent interest.
Publisher
AMER MATHEMATICAL SOC
Issue Date
2016-05
Language
English
Article Type
Article
Keywords

ERDOS-SZEKERES PROBLEM; THEOREM; BODIES

Citation

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, v.368, no.5, pp.3271 - 3303

ISSN
0002-9947
DOI
10.1090/tran/6437
URI
http://hdl.handle.net/10203/209527
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 3 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0