首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号