The width of random subsets of Boolean lattices (Q1865401)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The width of random subsets of Boolean lattices
scientific article

    Statements

    The width of random subsets of Boolean lattices (English)
    0 references
    0 references
    26 March 2003
    0 references
    Let \([n]=\{ 1,\ldots,n\}\) and let \({\mathcal P}(n,p)\) be a random hypergraph whose edges are randomly chosen from the set of subsets of \([n]\), independently, with probability \(p\) each. The authors investigate the cardinality \(\alpha({\mathcal P}(n,p))\) of a largest Sperner family contained in \({\mathcal P}(n,p)\). The main result says that for any constant \(b>0\) and \(p=n^{-b\sqrt{n}}\), the ratio \(\frac{\alpha({\mathcal P}(n,p))}{|{\mathcal P}(n,p)|}\) tends to a constant with probability tending to \(1\) as \(n\rightarrow\infty\).
    0 references
    0 references
    Boolean lattice
    0 references
    Sperner family
    0 references
    random hypergraph
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references