×

Occupancy problems and random algebras. (English) Zbl 0724.06003

Let \([n]=\{1,2,...,n\}\). Consider \({\mathcal P}_ n=2^{[n]}\) as a probability space in which each subset of [n] has the same probability \(2^{-n}\). Now select \(A_ 1,A_ 2,...,A_ k\) independently and randomly from \({\mathcal P}_ n\) (with replacement). The authors determine the asymptotic probability that the Boolean subalgebra (or the distributive sublattice, or the meet sub-semi-lattice) of \({\mathcal P}_ n\) generated by \(A_ 1,A_ 2,...,A_ k\) is \(\alpha\)) freely generated by \(A_ 1,A_ 2,...,A_ k\), or \(\beta\)) the whole of \({\mathcal P}_ n\). For example, in the case of the Boolean subalgebra, if \(\epsilon >0\) is fixed and \(K=\log_ 2n-\log_ 2\log_ en+\log_ 2\log_ e2\) then lim p(\(\alpha\))\(=1\) for \(k\leq K-\epsilon\) and \(\lim_{n\to \infty}p(\alpha)=0\) for \(k\geq K+\epsilon\).
Reviewer: V.N.Salij

MSC:

06B25 Free lattices, projective lattices, word problems
06E99 Boolean algebras (Boolean rings)
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás, B., Random Graphs (1985), Academic Press: Academic Press London · Zbl 0567.05042
[2] Erdős, P.; Rényi, A., On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5, 17-61 (1960)
[3] Feller, W., An Introduction to Probability Theory and its Applications (1966), Wiley: Wiley New York · Zbl 0138.10207
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.