Note on the Optimal Structure of Recovering Set Pairs in Lattices: The Sandglass Conjecture

We present a conjecture concerning the optimal structure of a subset pair satisfying two dual requirements in a lattice that can be derived as the product of k finite length chains. The conjecture is proved for k = 2 . Introduction On an Oberwolfach conference in 1989 the second author presented the following conjecture. Conjecture: Let A = fA i g M1 i=1 , B = fB i g M2 i=1 be two families of subsets of an n--set such that the following two conditions hold: (i) A j [ B r = A k [ B s ) j = k (ii) A j " B r = A k " B s ) r = s . Then M 1 M 2 2 n . \Xi If true this upper bound is sharp as it is shown by the following simple construction. Fix an arbitrary C ` [n] and let A = fA : C ` A ` [n]g and B = fB : B ` Cg . Then clearly for every A 2 A , B 2 B we have B ` A , i.e., A [ B = A and A " B = B that assures the two conditions to be satisfied. On the other hand jAjjBj = 2 n\GammajCj 2 jCj = 2 n . (The problem originally arose from the investigation of codes for so--..