𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Width of Random Subsets of Boolean Lattices

✍ Scribed by Y. Kohayakawa; B. Kreuter

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
132 KB
Volume
100
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

Suppose we toss an independent coin with probability of success p for each subset of ½n ¼ f1; . . . ; ng; and form the random hypergraph Pðn; pÞ by taking as hyperedges the subsets with successful coin tosses. We investigate the cardinality of the largest Sperner family contained in Pðn; pÞ: We obtain a sharp result for the range of p ¼ pðnÞ in which this Sperner family has cardinality comparable to the cardinality of Pðn; pÞ: # 2002 Elsevier Science (USA)

πŸ“œ SIMILAR VOLUMES

The length of random subsets of Boolean
The length of random subsets of Boolean lattices
✍ Y. Kohayakawa; B. Kreuter; D. Osthus πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 236 KB πŸ‘ 3 views

We form the random poset P P n, p by including each subset of n s 1, . . . , n with probability p and ordering the subsets by inclusion. We investigate the length of the Ε½ . longest chain contained in P P n, p . For p G ern we obtain the limit distribution of this random variable. For smaller p we g

Small sublattices in random subsets of B
Small sublattices in random subsets of Boolean lattices
✍ B. Kreuter πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 290 KB πŸ‘ 3 views

In this article, we determine the probability of existence of small lattices in random subsets of a Boolean lattice. Furthermore, we address some Ramsey-and Turan-type questions. Analogous questions have been studied extensively for random graphs, but it turns out that the situation for Boolean lat

Rank-width of random graphs
Rank-width of random graphs
✍ Choongbum Lee; Joonkyung Lee; Sang-il Oum πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 109 KB

Rank-width of a graph G, denoted by rw(G), is a width parameter of graphs introduced by Oum and Seymour [J Combin Theory Ser B 96 (2006), 514-528]. We investigate the asymptotic behavior of rank-width of a random graph G(n, p). We show that, asymptotically almost surely, (i 2 ), then rw(G(n, p)) =

On the Maximal Width of Empty Lattice Si
On the Maximal Width of Empty Lattice Simplices
✍ Christian Haase; GΓΌnter M. Ziegler πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 116 KB

We construct d-dimensional empty lattice simplices of arbitrarily high volume from (d -1)dimensional ones, while preserving the lattice width. In particular, we give an example of infinitely many empty 4-simplices of width 2.