On the optimal structure of recovering set pairs in lattices: The sandglass conjecture
type: Item
instance of: scholarly article
title: On the optimal structure of recovering set pairs in lattices: The sandglass conjecture
zbMATH Open document ID: 0798.06009
DOI: 10.1016/0012-365X(94)90129-5
author: Gábor Simonyi
author: Rudolf Ahlswede
published in: Discrete Mathematics
publication date: 1994-06-14T00:00:00Z
review text: An ordered pair of subsets \((A,B)\) of a lattice \(L\) is called a recovering pair if for every \(a,a',c,c'\in A\) and \(b,b',d,d'\in B\) the following conditions hold: (i) \(a\vee b= a'\vee b' \Rightarrow a'=a\), (ii) \(c\wedge d= c' \wedge d' \Rightarrow d'=d\). We denote by \(r(L)\) the maximum possible value \(| A|\cdot| B|\) for a recovering pair of \(L\). A pair \((A,B)\) of subsets of a lattice \(L\) is said to form a sandglass if there exists an element \(c\) of \(L\) that satisfies \(c\leq a\) for every \(a\in A\) and \(c\geq b\) for every \(b\in B\). A sandglass is full if adding any new element to \(A\) or \(B\), the new pair will not be a sandglass any more; it is clear that a sandglass always forms a recovering pair. Sandglass Conjecture. Let \(L\) be the product of \(k\) finite length chains. Then there exists a (full) sandglass \((A,B)\) in \(L\) for which \(| A|\cdot | B|= r(L)\). The authors prove the conjecture for \(k=2\).
Mathematics Subject Classification ID: 06B05
zbMATH DE Number: 562608
zbMATH Keywords: recovering pair
zbMATH Keywords: sandglass
reviewed by: Grigore Călugăreanu
MaRDI profile type: Publication
Wikidata QID: Q123193503
cites work: On write-unidirectional memory codes
description: scientific article; zbMATH DE number 562608