pith. sign in

arxiv: 1012.3918 · v1 · pith:SJZTFKN3new · submitted 2010-12-17 · 🧮 math.CO

Large B_d-free and union-free subfamilies

classification 🧮 math.CO
keywords freegammafamilysetstextdistinctpropertysize
0
0 comments X
read the original abstract

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})$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.