Hypomorphic Sperner systems and non-reconstructible functions (Q2351723): Difference between revisions

This paper investigates the following reconstruction problem: Is a function \(f : A^n \rightarrow B\) uniquely determined, up to equivalence, by the collection of its identification minors, i.e., the functions obtained from \(f\) by identifying a pair of its arguments? A reconstruction problem is then formulated for Sperner systems. A Sperner system over a set \(A\) is a collection \(\mathcal S\) of subsets of \(A\) with the property that no member of \(\mathcal S\) is a subset of another member of \(\mathcal S\). The authors present infinite families of non-reconstructible Sperner systems. This has an application to a reconstruction problem for functions of several arguments and identification minors. As Sperner systems are representations of certain monotone functions, infinite families of non-reconstructible functions are thus obtained. The clones of Boolean functions are completely classified in regard to reconstructibility.