Boolean algebras and Lubell functions

Abstract: Let

2^{[n]}

denote the power set of

[n] := 1, 2, ..., n

. A collection

B s u b s e t 2^{[n]}

forms a

d

-dimensional {em Boolean algebra} if there exist pairwise disjoint sets

X_{0}, X_{1}, ..., X_{d} s u b s e t e q [n]

, all non-empty with perhaps the exception of

X_{0}

, so that

. Let

b (n, d)

be the maximum cardinality of a family

F s u b s e t 2^{X}

that does not contain a

d

-dimensional Boolean algebra. Gunderson, R"odl, and Sidorenko proved that

b (n, d) l e q c_{d} n^{- 1 / 2^{d}} c d o t 2^{n}

where

c_{d} = 1 0^{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 s u b s e t e q s u p n

is defined by

h_{n} (F) := s u m_{F i n F} 1 / n c h o o s e | F |

. We prove the following Tur'an type theorem. If

F s u b s e t e q 2^{[n]}

contains no

d

-dimensional Boolean algebra, then

h_{n} (F) l e q 2 (n + 1)^{1 - 2^{1 - d}}

for sufficiently large

n

. This results implies

b (n, d) l e q C n^{- 1 / 2^{d}} c d o t 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.

Recommendations

Cites Work

Cited In (11)

This page was built for publication: Boolean algebras and Lubell functions