Games of Chains and Cutsets in the Boolean Lattice II |
| |
Authors: | Li David Linnan Shahriari Shahriar |
| |
Affiliation: | (1) Department of Mathematics, Stanford University, Stanford, CA, 94305, U.S.A.;(2) Department of Mathematics, Pomona College, Claremont, CA, 91711, U.S.A. |
| |
Abstract: | Let 2[n] denote the poset of all subsets of [n]={1,2,...,n} ordered by inclusion. Following Gutterman and Shahriari (Order 14, 1998, 321–325) we consider a game Gn(a,b,c). This is a game for two players. First, Player I constructs a independent maximal chains in 2[n]. Player II will extend the collection to a+b independent maximal chains by finding another b independent maximal chains in 2[n]. Finally, Player I will attempt to extend the collection further to a+b+c such chains. The last Player who is able to complete her move wins. In this paper, we complete the analysis of Gn(a,b,c) by considering its most difficult instance: when c=2 and a+b+2=n. We prove, the rather surprising result, that, for n7, Player I wins Gn(a,n–a–2,2) if and only if a3. As a consequence we get results about extending collections of independent maximal chains, and about cutsets (collections of subsets that intersect every maximal chain) of minimum possible width (the size of largest anti-chain). |
| |
Keywords: | Boolean lattice cutset games on the Boolean lattice independent chains maximal chain width |
本文献已被 SpringerLink 等数据库收录! |
|