Large subfamilies with forbidden configurations

Ida Kantor

Abstract

Let F be a family of finite sets. A subfamily F' of F is a-union-free if it does not contain distinct sets A_1,...,A_{a+1} such that A_1\cup A_2 \cup...\cup A_a = A_{a+1}. f(F,a-union-free) will denote the size of the largest a-union-free subfamily of F, and f(m,a-union-free)= min f(F,a-union-free), where the minimum is taken over all families F of cardinality m.

Instead of "a-union-free" we can take any other property Gamma, and define f(m,Gamma) analogously.

Erdos and Komlos, Kleitman, and Erdos and Shelah have results on 2-union-free families and B_2-free families, where B_2 is Boolean lattice of dimension 2, i.e., distinct sets A_1,A_2,A_3,A_4 such that A_1\cup A_2=A_3 and A_1\cap A_2=A_4. In particular, they show that f(m,B_2-free)\leq (2/3)m^{2/3} and conjecture that the lower bound is cm^{2/3} for some positive constant c.

We prove the conjecture, and provide lower and upper bounds for f(m,