The width of random subsets of Boolean lattices

DOI10.1006/JCTA.2002.3293MaRDI QIDQ1865401zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 26 March 2003

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcta.2002.3293

zbMATH Keywords

Boolean latticerandom hypergraphSperner family

Mathematics Subject Classification ID

Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorics of partially ordered sets (06A07) Combinatorial probability (60C05)

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\).

Recommendations

• A random version of Sperner's theorem
• The length of random subsets of Boolean lattices
• Occupancy problems and random algebras
• Maximum antichains in random subsets of a finite set
• scientific article; zbMATH DE number 4192744

Cites work

• A short proof of Sperner's lemma
• Box-Spaces and Random Partial Orders
• scientific article; zbMATH DE number 446489 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 3974960 (Why is no real title available?)
• scientific article; zbMATH DE number 1016362 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3223273 (Why is no real title available?)
• Maximum antichains in random subsets of a finite set
• On the diameter and radius of randon subgraphs of the cube
• Percolation, first-passage percolation and covering times for Richardson's model on the \(n\)-cube
• Small sublattices in random subsets of Boolean lattices
• The height of a random partial order: Concentration of measure
• The length of random subsets of Boolean lattices

Cited in

(11)

• Maximum antichains in random subsets of a finite set
• Occupancy problems and random algebras
• The rectangle covering number of random Boolean matrices
• Maximum-size antichains in random set-systems
• scientific article; zbMATH DE number 4192744 (Why is no real title available?)
• Existence thresholds and Ramsey properties of random posets
• A random version of Sperner's theorem
• Small sublattices in random subsets of Boolean lattices
• The length of random subsets of Boolean lattices
• A sharp threshold for a random version of Sperner's theorem
• On Dedekind's problem, a sparse version of Sperner's theorem, and antichains of a given size in the Boolean lattice

This page was built for publication: The width of random subsets of Boolean lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1865401)