New bounds on Simonyi's conjecture

Abstract

We say that a pair $(\mathcal{A},\mathcal{B})$ is a recovering pair if $\mathcal{A}$ and $\mathcal{B}$ are set systems on an $n$ element ground set, such that for every $A,A^{\prime }\in \mathcal{A}$ and $B,B^{\prime }\in \mathcal{B}$ we have that ($A\setminus B=A^{\prime }\setminus B^{\prime }$ implies $A=A^{\prime }$) and symmetrically ($B\setminus A=B^{\prime }\setminus A^{\prime }$ implies $B=B^{\prime }$). G. Simonyi conjectured that if $(\mathcal{A},\mathcal{B})$ is a recovering pair, then $|\mathcal{A}||\mathcal{B}|\le 2^n$. For the quantity $|\mathcal{A}||\mathcal{B}|$ the best known upper bound is $2.3264^n$ due to Körner and Holzman. In this paper we improve this upper bound to $2.284^n$. Our proof is combinatorial.

arXiv comment14 pages 1 figure