On then-cutset property |
| |
Authors: | John Ginsburg |
| |
Institution: | (1) Department of Mathematics, University of Winnipeg, R3B 2E9 Winnipeg, Manitoba, Canada |
| |
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)?2n/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. |
| |
Keywords: | Partially ordered set chain cutset n-cutset property |
本文献已被 SpringerLink 等数据库收录! |
|