A New Construction for Cancellative Families of Sets

James B. Shearer


Following [2], we say a family, $H$, of subsets of a $n$-element set is cancellative if $A \cup B = A \cup C$ implies $B =C$ when $A, B, C \in H$. We show how to construct cancellative families of sets with $c 2^{.54797n}$ elements. This improves the previous best bound $c 2^{.52832n}$ and falsifies conjectures of Erdös and Katona [3] and Bollobás [1].

Full Text: PDF