Large B_d-free and union-free subfamilies

Abstract

For a property $\Gamma$ and a family of sets $\cF$, let $f(\cF,Γ)$ be the size of the largest subfamily of $\cF$ having property $\Gamma$. For a positive integer $m$, let $f(m,\Gamma )$ be the minimum of $f(\cF,Γ)$ over all families of size $m$. A family $\cF$ is said to be $B_d$-free if it has no subfamily $\cF'=\{F_I: I \subseteq [d]\}$ of $2^d$ distinct sets such that for every $I,J\subseteq [d]$, both $F_I\cup F_J=F_{I\cup J}$ and $F_I\cap F_J=F_{I\cap J}$ hold. A family $\cF$ is $a$-union free if $F_1\cup ...F_a\ne F_{a+1}$ whenever $F_1,..,F_{a+1}$ are distinct sets in $\FF$. We verify a conjecture of Erd\H os and Shelah that $f(m,B_2\text{-free})=\Theta (m^{2/3})$. We also obtain lower and upper bounds for $f(m,B_d\text{-free})$ and $f(m,a\text{-union free})$.

8 pages

References in corpus (1)

• Maximum union-free subfamilies

Cited by in corpus (1)

• Maximum union-free subfamilies