Title of article :
Packing and covering -chain free subsets in Boolean lattices
Author/Authors :
Shen، نويسنده , , Jia، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Pages :
7
From page :
4628
To page :
4634
Abstract :
Let P be a finite poset. A subset of P is called k -element chain free if it contains no k -element chain. Let H ( B n ) be the hypergraph whose vertices are the points of the Boolean lattice B n , and whose edges are inclusionwise maximal k -chain free subsets of B n . We investigate the covering number τ k ( B n ) of H , i.e. the least number of points intersecting every maximal k -chain free subset of B n , and the packing (matching) number ν k ( B n ) of H , i.e. the greatest number of pairwise disjoint maximal k -chain free subsets in B n . Using counting arguments, exponential bounds for τ k ( B n ) and ν k ( B n ) are given.
Keywords :
Boolean lattice , Packing , Covering , Maximal k -chain free subset
Journal title :
Discrete Mathematics
Serial Year :
2009
Journal title :
Discrete Mathematics
Record number :
1598975
Link To Document :
بازگشت