کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776985 | 1413647 | 2017 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
De Bruijn-ErdÅs-type theorems for graphs and posets
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A classical theorem of De Bruijn and ErdÅs asserts that any noncollinear set of n points in the plane determines at least n distinct lines. We prove that an analogue of this theorem holds for posets, where lines are defined using the natural betweenness relation in posets. More precisely, we obtain a bound on the number of lines depending on the height of the poset. The extremal configurations are also determined. Finally, we introduce a new notion of lines in graphs and show that our result for posets can be extended to this setting.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 5, May 2017, Pages 995-999
Journal: Discrete Mathematics - Volume 340, Issue 5, May 2017, Pages 995-999
نویسندگان
Pierre Aboulker, Guillaume Lagarde, David Malec, Abhishek Methuku, Casey Tompkins,