New bounds on Simonyi's conjecture

Abstract: We say that a pair

(m a t h c a l A, m a t h c a l B)

is a recovering pair if

m a t h c a l A

and

m a t h c a l B

are set systems on an

n

element ground set, such that for every

A, A^{'} i n m a t h c a l A

and

B, B^{'} i n m a t h c a l B

we have that (

A s e t m i n u s B = A^{'} s e t m i n u s B^{'}

implies

A = A^{'}

) and symmetrically (

B s e t m i n u s A = B^{'} s e t m i n u s A^{'}

implies

B = B^{'}

). G. Simonyi conjectured that if

(m a t h c a l A, m a t h c a l B)

is a recovering pair, then

| m a t h c a l A | | m a t h c a l B | l e q 2^{n}

. For the quantity

| m a t h c a l A | | m a t h c a l B |

the best known upper bound is

2.326 4^{n}

due to K"orner and Holzman. In this paper we improve this upper bound to

2.28 4^{n}

. Our proof is combinatorial.

Recommendations

Cites Work

Cited In (4)

This page was built for publication: New bounds on Simonyi's conjecture