کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654394 1632829 2008 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Erdős–Szekeres “happy end”-type theorems for separoïds
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Erdős–Szekeres “happy end”-type theorems for separoïds
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 29, Issue 4, May 2008, Pages 1076–1085
نویسندگان
,