Extremal problems for sets forming Boolean algebras and complete partite hypergraphs

DOI10.1006/JCTA.1999.2973MaRDI QIDQ1818218zbMATH OpenOpenAlexFDO

Authors Alexander Sidorenko, David S. Gunderson, Vojtěch Rödl

Publication date 31 January 2000

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

Full work available at URL https://semanticscholar.org/paper/f823f2134869bb3ac8f1ae7f566919247221acce

Boolean algebra finite families of sets Hales-Jewitt theorem hypergraphs probabilistic proofs Ramsey functions

Hypergraphs (05C65) Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Structure theory of Boolean algebras (06E05)

Review text

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.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Extremal problems for sets forming Boolean algebras and complete partite hypergraphs

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