کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649674 1342462 2009 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Packing and covering k-chain free subsets in Boolean lattices
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Packing and covering k-chain free subsets in Boolean lattices
چکیده انگلیسی

Let PP be a finite poset. A subset of PP is called kk-element chain free if it contains no kk-element chain. Let H(Bn)H(Bn) be the hypergraph whose vertices are the points of the Boolean lattice BnBn, and whose edges are inclusionwise maximal kk-chain free subsets of BnBn. We investigate the covering number τk(Bn) of HH, i.e. the least number of points intersecting every maximal kk-chain free subset of BnBn, and the packing (matching) number νk(Bn) of HH, i.e. the greatest number of pairwise disjoint maximal kk-chain free subsets in BnBn. Using counting arguments, exponential bounds for τk(Bn) and νk(Bn) are given.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 13, 6 July 2009, Pages 4628–4634
نویسندگان
,