A New Upper Bound for Cancellative Pairs

Abstract

A pair $(\mathcal{A},\mathcal{B})$ of families of subsets of an $n$-element set is called cancellative if whenever $A,A^{\prime }\in \mathcal{A}$ and $B\in \mathcal{B}$ satisfy $A\cup B=A^{\prime }\cup B$, then $A=A^{\prime }$, and whenever $A\in \mathcal{A}$ and $B,B^{\prime }\in \mathcal{B}$ satisfy $A\cup B=A\cup B^{\prime }$, then $B=B^{\prime }$. It is known that there exist cancellative pairs with $|\mathcal{A}||\mathcal{B}|$ about $2.25^n$, whereas the best known upper bound on this quantity is $2.3264^n$. In this paper we improve this upper bound to $2.2682^n$. Our result also improves the best known upper bound for Simonyi's sandglass conjecture for set systems.

7 pages, 1 figure

Cited by in corpus (1)

• On the Non-Adaptive Zero-Error Capacity of the Discrete Memoryless Two-Way Channel