Long symmetric chains in the Boolean lattice (Q1919667)

From MaRDI portal





scientific article; zbMATH DE number 909612
Language Label Description Also known as
English
Long symmetric chains in the Boolean lattice
scientific article; zbMATH DE number 909612

    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