Boolean algebras and Lubell functions

Abstract

Let $2^{[n]}$ denote the power set of $[n]:=\{1,2,...,n\}$. A collection $\B\subset 2^{[n]}$ forms a $d$-dimensional {\em Boolean algebra} if there exist pairwise disjoint sets $X_0,X_1,...,X_d\subseteq [n]$, all non-empty with perhaps the exception of $X_0$, so that $\B={X_0\cup \bigcup_{i\in I} X_i\colon I\subseteq [d]}$. Let $b(n,d)$ be the maximum cardinality of a family $\F\subset 2^X$ that does not contain a $d$-dimensional Boolean algebra. Gunderson, Rödl, and Sidorenko proved that $b(n,d)\le c_d{n}^{-1/2^d}\cdot 2^n$ where $c_d=10^d{2}^{-2^{1-d}}{d}^{d-2^{-d}}$. In this paper, we use the Lubell function as a new measurement for large families instead of cardinality. The Lubell value of a family of sets $\F$ with $\F\subseteq \tsupn$ is defined by $h_n(\F):=\sum_{F\in \F}1/{n\choose |F|}$. We prove the following Turán type theorem. If $\F\subseteq 2^{[n]}$ contains no $d$-dimensional Boolean algebra, then $h_n(\F)\leq 2(n+1)^{1-2^{1-d}}$ for sufficiently large $n$. This results implies $b(n,d)\le C{n}^{-1/2^d}\cdot 2^n$, where $C$ is an absolute constant independent of $n$ and $d$. As a consequence, we improve several Ramsey-type bounds on Boolean algebras. We also prove a canonical Ramsey theorem for Boolean algebras.

arXiv comment10 pages

Cited by in corpus (1)

• Set families with forbidden subposets