Games of Chains and Cutsets in the Boolean Lattice II |
| |
Authors: | Li David Linnan Shahriari Shahriar |
| |
Institution: | (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 G
n
(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 G
n
(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 n 7, Player I wins G
n
(a,n–a–2,2) if and only if a 3. 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 等数据库收录! |
|