Games of Chains and Cutsets in the Boolean Lattice

B. Bajnok and S. Shahriari proved that in 2^[n], the Boolean lattice of order n, the width (the maximum size of an antichain) of a non-trivial cutset (a collection of subsets that meets every maximal chain and does not contain or [n]) is at least n-1. We prove that, for n5, in the Boolean lattice of order n, given -1 disjoint long chains, we can enlarge the collection to a cutset of width n-1. However, there exists a collection of long chains that cannot be so extended.     

Partitioning Boolean lattices into antichains

Let f(n) be the smallest integer t such that a poset obtained from a Boolean lattice with n atoms by deleting both the largest and the smallest elements can be partitioned into t antichains of the same size except for possibly one antichain of a smaller size. In this paper, it is shown that f(n)b n²/log n. This is an improvement of the best previously known upper bound for f(n).     

Games of Chains and Cutsets in the Boolean Lattice II

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 n7, Player I wins G _n (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).     

Partitioning Boolean lattices into chains of subsets

We prove that the Boolean lattice of all subsets of an n-set can be partitioned into chains of size four if and only if n9.Research supported in part by N.S.F. grant DMS-8401281.Research supported in part by N.S.F. grant DMS-8406451.     

布尔矩阵的指标格(英文)

本文介绍了布尔矩阵的指标格,并讨论了它的性质,得到了从布尔矩阵指标格到一个给定完备格的一个序嵌入映射存在的条件,回答了在什么条件下布尔矩阵的指标格是完全分配格的问题。     

布尔矩阵的指标格

本文首先构造了由一个布尔矩阵的特定行指标和列指标对所确定的指标格,然后刻画了指标格的同态像、直积和子格所对应的布尔矩阵的性质.     

原子Boolean格代数的导子

设L是Banach空间X上的原子Boolean子空间格,δ是algL的任一导子,则存在X中的一个稠定线性算子T,使得δ（A）＝AT—TA（A∈algL）在T的定义域D（T）上成立．另外,如果L还是一个有限格,并且对L的任一原子L,L＋L＇闭,则δ是连续的和内的．     

布尔格偏序结构图的性质

对布尔格的偏序结构图—哈斯图,从图论角度进行了研究.给出4个性质、两个推论.     

Q 2-free Families in the Boolean Lattice

For a family F{{\cal F}} of subsets of [n] = {1, 2, ..., n} ordered by inclusion, and a partially ordered set P, we say that F{{\cal F}} is P-free if it does not contain a subposet isomorphic to P. Let ex(n, P) be the largest size of a P-free family of subsets of [n]. Let Q ₂ be the poset with distinct elements a, b, c, d, a < b,c < d; i.e., the 2-dimensional Boolean lattice. We show that 2N − o(N) ≤ ex(n, Q ₂) ≤ 2.283261N + o(N), where N = \binomn?n/2 ?N = \binom{n}{\lfloor n/2 \rfloor}. We also prove that the largest Q ₂-free family of subsets of [n] having at most three different sizes has at most 2.20711N members.     

The Number of Linear Extensions of the Boolean Lattice

Let L(Q ^t ) denote the number of linear extensions of the t-dimensional Boolean lattice Q ^t . We use the entropy method of Kahn to show that

The Dimension of Neighboring Levels of the Boolean Lattice

The order dimension of suborders of the Boolean lattice is considered. It is shown that the suborder of consisting of levels s and s+1 has dimension O(\log n/log log n). This improves a bound in [1].     

布尔矩阵的指标格的性质

介绍了布尔矩阵的行零元、列零元和相容子矩阵的定义并讨论了它们的性质,给出了布尔矩阵的指标格分别为分配格、半分配格和半模格的等价条件.     

Chains of Modular Elements and Lattice Connectivity

We show that the order complex of any finite lattice with a chain of modular elements is at least (r−2)-connected. The first author was supported during part of this work by a postdoctoral fellowship from the Mathematical Sciences Research Institute. The second author was supported by NSF grant DMS-0300483.     

On Uniform f-vectors of Cutsets in the Truncated Boolean Lattice

and let be the collection of all subsets of [n] ordered by inclusion. is a cutset if it meets every maximal chain in , and the width of is the minimum number of chains in a chain decomposition of . Fix . What is the smallest value of such that there exists a cutset that consists only of subsets of sizes between m and l, and such that it contains exactly k subsets of size i for each ? The answer, which we denote by , gives a lower estimate for the width of a cutset between levels m and l in . After using the Kruskal–Katona Theorem to give a general characterization of cutsets in terms of the number and sizes of their elements, we find lower and upper bounds (as well as some exact values) for . Received September 4, 1997     

Width and f-vectors of Cutsets in the Truncated Boolean Lattice

In this paper we will survey a collection of recent results about chains and cutsets in the Boolean lattice and some other posets. In particular, we consider the possibilities for the width (i.e., the size of the largest anti-chain) and the f-vectors (i.e., the number of subsets of various sizes) of cutsets. Given k chains in the Boolean lattice, we will also consider the possible number of pair-wise disjoint maximal chains that do not intersect the given k chains.     

Three Layer Q 2-Free Families in the Boolean Lattice

We prove that the largest Q ₂-free family of subsets of [n] which contains sets of at most three different sizes has at most $\big(3 + 2\sqrt {3} \big)N/3 + o(N) \approx 2.1547N\,\, + o(N)$ members, where $N = { n \choose {{\lfloor} n/2 {\rfloor} }}$ . This improves an earlier bound of 2.207N?+?o(N) by Axenovich, Manske, and Martin.     

An Extremal Problem with Excluded Subposet in the Boolean Lattice

Let 2[n] be the poset of all subsets of {1,...,n} ordered by inclusion. A poset P is said to be contained in a subposet F of 2[n] as a subposet if there exists a subposet P' of F that is isomorphic to P. In this paper we will give an estimate on the size of a maximally sized subposet of 2[n] under the assumption that the subposet does not contain Y(u,v) = ({a1,...,au, b1,...,bv}, {a1< ··· < au, au< b1, au< b2,...,au< bv}) as a subposet.