The width of random subsets of Boolean lattices (Q1865401)

From MaRDI portal





scientific article; zbMATH DE number 1888430
Language Label Description Also known as
English
The width of random subsets of Boolean lattices
scientific article; zbMATH DE number 1888430

    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