Title of article :
Erdős–Szekeres “happy end”-type theorems for separoïds
Author/Authors :
Strausz، نويسنده , , Ricardo، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2008
Pages :
10
From page :
1076
To page :
1085
Abstract :
In 1935 Pál Erdős and György Szekeres proved that, roughly speaking, any configuration of n points in general position in the plane have log n points in convex position — which are the vertices of a convex polygon. Later, in 1983, Bernhard Korte and László Lovász generalised this result in a purely combinatorial context; the context of greedoids. In this note we give one step further to generalise this last result for arbitrary dimensions, but in the context of separoids; thus, via the geometric representation theorem for separoids, this can be applied to families of convex bodies. Also, it is observed that the existence of some homomorphisms of separoids implies the existence of not-too-small polytopal subfamilies — where each body is separated from its relative complement. Finally, by means of a probabilistic argument, it is settled, basically, that for all  d > 2 , asymptotically almost all “simple” families of  n “ d -separated” convex bodies contains a polytopal subfamily of order  log n d + 1 .
Journal title :
European Journal of Combinatorics
Serial Year :
2008
Journal title :
European Journal of Combinatorics
Record number :
1548271
Link To Document :
بازگشت