Article ID Journal Published Year Pages File Type
6423806 Electronic Notes in Discrete Mathematics 2011 4 Pages PDF
Abstract

For a property Γ and a family of sets F, let f(F,Γ) be the size of the largest subfamily of F having property Γ. For a positive integer m, let f(m,Γ) be the minimum of f(F,Γ) over all families of size m. A family F is said to be Bd-free if it has no subfamily F′={FI:I⊆[d]} of 2d distinct sets such that for every I,J⊆[d], both FI∪FJ=FI∪J and FI∩FJ=FI∩J hold. A family F is a-union free if F1∪⋯∪Fa≠Fa+1 whenever F1,…,Fa+1 are distinct sets in F. We verify a conjecture of Erdős and Shelah that f(m,B2-free)=Θ(m2/3). We also obtain lower and upper bounds for f(m,Bd-free) and f(m,a-union free).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , , ,