The width of random subsets of Boolean lattices
type: Item
instance of: scholarly article
title: The width of random subsets of Boolean lattices
zbMATH Open document ID: 1015.05090
author: Yanyan Li
published in: Journal of Combinatorial Theory. Series A
publication date: 2003-03-26T00:00:00Z
review text: 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\).
reviewed by: Zbigniew Lonc
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 05D40
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 1888430
zbMATH Keywords: Boolean lattice
zbMATH Keywords: Sperner family
zbMATH Keywords: random hypergraph
MaRDI profile type: Publication
full work available at URL: jcta.2002.3293
OpenAlex ID: W2003200680
cites work: Q3741626
cites work: Q3682518
cites work: Q3726125
cites work: Box-Spaces and Random Partial Orders
cites work: The height of a random partial order: Concentration of measure
cites work: On the diameter and radius of randon subgraphs of the cube
cites work: Q3142411
cites work: Q4338928
cites work: Percolation, first-passage percolation and covering times for Richardson's model on the \(n\)-cube
cites work: Q4519896
cites work: The length of random subsets of Boolean lattices
cites work: Small sublattices in random subsets of Boolean lattices
cites work: A short proof of Sperner's lemma
cites work: Maximum antichains in random subsets of a finite set
cites work: Q5511767
DOI: 10.1006/JCTA.2002.3293
description: scientific article; zbMATH DE number 1888430