کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777214 1632576 2016 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Linear Extension Polytope of a Poset
ترجمه فارسی عنوان
چند ضلعی خطی یک پد
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let P be a finite poset. By definition, the linear extension polytope of P has as vertices the characteristic vectors of all linear extensions of P. In case P is an antichain, it is the linear ordering polytope. The linear extension polytope appears in combinatorial optimization in the context of scheduling with precedence constraints, see e.g. [A. Schulz, Polytopes and Scheduling, Phd Thesis, TU Berlin, 1996]. It seems also relevant to order theory, being similar in spirit to other constructions such as the linear extension graph, see e.g. [M. Massow, Linear extension graphs and linear extension diameter, PhD thesis, TU Berlin, 2009]. In this work, we relate the combinatorial properties of the poset P to the polyhedral structure of its linear extension polytope. Of particular interest is a natural relaxation of the linear extension polytope. We prove that the relaxation is exact in case P is a width-2 poset, and formulate a conjecture stating exactly when the relaxation is exact.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 55, November 2016, Pages 81-84
نویسندگان
, , ,