New Bounds for Union-free Families of Sets

  • Don Coppersmith
  • James B. Shearer

Abstract

Following Frankl and Füredi we say a family, $F$, of subsets of an $n$-set is weakly union-free if $F$ does not contain four distinct sets $A$, $B$, $C$, $D$ with $A \cup B = C \cup D$. If in addition $A \cup B = A \cup C$ implies $B=C$ we say $F$ is strongly union-free. Let $f(n)$ ($g(n)$) be the maximum size of strongly (weakly) union-free families. In this paper we prove the following new bounds on $f$ and $g$: $$2^{[0.31349+o(1)]n} \leq f(n) \leq 2^{[0.4998+o(1)]n}$$ and $$g(n) \leq 2^{[0.5+o(1)]n}.$$

Published
1998-07-24
Article Number
R39