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
    0 references
    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
    0 references
    symmetric chains
    0 references
    Boolean lattice
    0 references
    saturated chains
    0 references
    long chains
    0 references
    cutset
    0 references

    Identifiers