The width of random subsets of Boolean lattices (Q1865401)

From MaRDI portal





scientific article; zbMATH DE number 1888430
Language Label Description Also known as
default for all languages
No label defined
    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