Long symmetric chains in the Boolean lattice (Q1919667)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Long symmetric chains in the Boolean lattice |
scientific article |
Statements
Long symmetric chains in the Boolean lattice (English)
0 references
10 October 1996
0 references
A chain \((X_1 \subset \cdots \subset X_l)\) in the Boolean lattice \(B_n\) is called saturated if \(|X_{i + 1} |= |X_i |+ 1\), \(i = 1, \dots, l - 1\). If, in addition, \(l = n - 1\) and \(|X_1 |= 1\), then the chain is said to be long. The authors prove by induction on \(n\): For \(n \geq 2\) and any collection of \(k \leq n - 2\) saturated chains in \(B_n\) there exists at least one long chain disjoint from the chains in the collection. For \(n \geq 3\) and any collection of \(k \leq n - 3\) saturated chains in \(B_n\) there are three pairwise disjoint long chains all being disjoint from the given ones. Moreover, the authors present an example of \(n - 1\) pairwise disjoint long chains such that their union is a cutset, i.e., there is no further long chain in \(B_n \backslash C\).
0 references
symmetric chains
0 references
Boolean lattice
0 references
saturated chains
0 references
long chains
0 references
cutset
0 references