ISSN:
1572-9273
Keywords:
Partially ordered set
;
chain
;
cutset
;
n-cutset property
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract For a partially ordered setP and an elementx ofP, a subsetS ofP is called a cutset forx inP if every element ofS is noncomparable tox and every maximal chain ofP meets {x}∪S. We letc(P) denote the smallest integerk such that every elementx ofP has a cutsetS with ‖S‖⩽k: Ifc(P)⩽n we say thatP has then-cutset property. Our results bear on the following question: givenP, what is the smallestn such thatP can be embedded in a partially ordered set having then-cutset property? As usual, 2 n denotes the Boolean lattice of all subsets of ann-element set, andB n denotes the set of atoms and co-atoms of 2 n . We establish the following results: (i) a characterization, by means of forbidden configurations, of whichP can be embedded in a partially ordered set having the 1-cutset property; (ii) ifP contains a copy of 2 n , thenc(P)⩾2[n/2]−1; (iii) for everyn〉3 there is a partially ordered setP containing 2 n such thatc(P)〈c(2 n ); (iv) for every positive integern there is a positive integerN such that, ifB m is contained in a partially ordered set having then-cutset property, thenm⩽N.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02034332
Permalink