Affordable Access

Publisher Website

Cancellative pairs of families of sets

Authors
Journal
European Journal of Combinatorics
0195-6698
Publisher
Elsevier
Publication Date
Volume
16
Issue
3
Identifiers
DOI: 10.1016/0195-6698(95)90031-4

Abstract

Abstract A pair ( A, B ) of families of subsets of an n-element set X is cancellative if, for all A, A ′ ϵ A and B, B ′ ϵ B, the following conditions hold: A⧹ B = A ′⧹ B ⇒ A = A ′ and B⧹ A = B ′⧹ A ⇒ B = B ′. We prove that every such pair satisfies AB \ ̌ gd , where τ = 2.3264. This is related to a conjecture of Erdõ and Katona on cancellative families and to a conjecture of Simonyi on recovering pairs. For the latter, our result gives the best known upper bound.

There are no comments yet on this publication. Be the first to share your thoughts.