𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Long Symmetric Chains in the Boolean Lattice

✍ Scribed by Béla Bajnok; Shahriar Shahriari

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
316 KB
Volume
75
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

Let 2 [n] be the poset of all subsets of a set with n elements ordered by inclusion. A long chain in this poset is a chain of n&1 subsets starting with a subset with one element and ending with a subset with n&1 elements. In this paper we prove: Given any collection of at most n&2 skipless chains in 2 [n] , there exists at least one (but sometimes not more than one) long chain disjoint from the chains in the collection. Furthermore, for k 3, given a collection of n&k skipless chains in 2 [n] , there are at least k pairwise disjoint long chains which are also disjoint from the given chains.

📜 SIMILAR VOLUMES

Partitioning the Boolean Lattice into Ch
Partitioning the Boolean Lattice into Chains of Large Minimum Size
✍ Tim Hsu; Mark J. Logan; Shahriar Shahriari; Christopher Towse 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 187 KB

Let 2 [n] denote the Boolean lattice of order n, that is, the poset of subsets of {1, ..., n} ordered by inclusion. Recall that 2 [n] may be partitioned into what we call the canonical symmetric chain decomposition (due to de Bruijn, Tengbergen, and Kruyswijk), or CSCD. Motivated by a question of Fü

The t-intersection Problem in the Trunca
The t-intersection Problem in the Truncated Boolean Lattice
✍ Rudolf Ahlswede; Christian Bey; Konrad Engel; Levon H. Khachatrian 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 146 KB

Let I (n, t) be the class of all t-intersecting families of subsets of [n] and set ≤k . After the maximal families in I (n, t) [13] and in I k (n, t) [1,9] are known we study now maximal families in I ≤k (n, t). We present a conjecture about the maximal cardinalities and prove it in several cases.

On the f-vectors of Cutsets in the Boole
On the f-vectors of Cutsets in the Boolean Lattice
✍ Matthew Haines; Shahriar Shahriari 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 102 KB

A cutset in the poset 2 [n] , of subsets of [1, ..., n] ordered by inclusion, is a subset of 2 [n] that intersects every maximal chain. Let 0 : 1 be a real number. Is it possible to find a cutset in 2 [n] that, for each 0 i n, contains at most : ( n i ) subsets of size i ? Let :(n) be the greatest l