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
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
Boolean lattice
0 references
Sperner family
0 references
random hypergraph
0 references
0 references