On Cancellative Set Families
János Körner, Blerina Sinaimeri · Combinatorics Probability Computing · 2007
A family of subsets of an n -set is 2-cancellative if, for every four-tuple { A , B , C , D } of its members, A ∪ B ∪ C = A ∪ B ∪ D implies C = D . This generalizes the concept of cancellative set families, defined by the property that A ∪ B ≠ A ∪ C for A , B , C all different. The asymptotics of the maximum size of cancellative families of subsets of an n -set is known (Tolhuizen [7]). We provide a new upper bound on the size of 2-cancellative families, improving the previous bound of 2 0.458 n to 2 0.42 n .