A Positive Fraction Erdos - Szekeres Theorem

We prove a fractional version of the Erdős—Szekeres theorem: for any k there is a constant c _k > 0 such that any sufficiently large finite set X⊂ R ² contains k subsets Y ₁ , ... ,Y _k , each of size ≥ c _k |X| , such that every set {y ₁ ,...,y _k } with y _i ε Y _i is in convex position. The main tool is a lemma stating that any finite set X⊂ R ^d contains ``large'' subsets Y ₁ ,...,Y _k such that all sets {y ₁ ,...,y _k } with y _i ε Y _i have the same geometric (order) type. We also prove several related results (e.g., the positive fraction Radon theorem, the positive fraction Tverberg theorem). <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p335.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader>

Authors and Affiliations

1. Mathematical Institute of the Hungarian Academy of Sciences, P.O.B. 127, H-1364 Budapest, Hungary barany@math-inst.hu, , , , , , HU

   I. Bárány

2. Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic valtr@kam.ms.mff.cuni.cz, , , , , , CZ

   P. Valtr

Received March 8, 1996, and in revised form June 24, 1996.

Reprints and permissions