Article ID Journal Published Year Pages File Type
4654394 European Journal of Combinatorics 2008 10 Pages PDF
Abstract

In 1935 Pál Erdős and György Szekeres proved that, roughly speaking, any configuration of  nnpoints in general position in the plane have  lognlognpoints 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>2d>2, asymptotically almost all “simple” families of   nn “dd-separated” convex bodies contains a polytopal subfamily of order   lognd+1.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,