کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6424250 1632784 2014 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Dimension and height for posets with planar cover graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Dimension and height for posets with planar cover graphs
چکیده انگلیسی
We show that for each integer h≥2, there exists a least positive integer ch so that if P is a poset having a planar cover graph and the height of P is h, then the dimension of P is at most ch. Trivially, c1=2. Also, Felsner, Li and Trotter showed that c2 exists and is 4, but their proof techniques do not seem to apply when h≥3. We focus on establishing the existence of ch, although we suspect that the upper bound provided by our proof is far from best possible. From below, a construction of Kelly is easily modified to show that ch must be at least h+2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 35, January 2014, Pages 474-489
نویسندگان
, ,