Extremal problems for sets forming Boolean algebras and complete partite hypergraphs (Q1818218): Difference between revisions

This interesting paper explores two Ramsey functions involving Boolean subalgebras of finite families of sets. Let \(b(n,d)\) be the maximum size of a family of subsets of \([n]\) not containing a \(d\)-dimensional Boolean algebra, and let \(r(n,d)\) be the largest number of colors one can color the power set of \([n]\) and be guaranteed a monochromatic \(d\)-dimensional Boolean algebra. The paper develops some density results for hypergraphs which are used as lemmas in some probabilistic proofs that \(b(n,d)\) has lower and upper bounds both of the form \(\text{const}\cdot n^{-\text{const}}2^n\). Then \(r(n,d)\) has lower and upper bounds both of the form \(\text{const}\cdot n^{\text{const}}\), and in fact, \(\left({3\over 4}- o(1)\right)\sqrt n\leq r(2, n)\leq (1+ o(1))\sqrt n\). The paper concludes with a variant of the Hales-Jewitt theorem.