Large B_d-free and union-free subfamilies

Details Large B_d-free and union-free subfamilies Large B_d-free and union-free subfamilies

2010-12-17

arxiv.org/abs/1012.3918v1

Mathematics

Combinatorics

8 pages

Scientific paper

For a property $\Gamma$ and a family of sets $\cF$, let $f(\cF,\Gamma)$ 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,\Gamma)$ 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 \neq 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{\rm -free})=\Theta(m^{2/3})$. We also obtain lower and upper bounds for $f(m, B_d\text{\rm -free})$ and $f(m,a\text{\rm -union free})$.

Affiliated with

Also associated with

No associations

Rating

Large B_d-free and union-free subfamilies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Large B_d-free and union-free subfamilies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large B_d-free and union-free subfamilies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-639444