Minimum matrix representation of Sperner systems
Let \(M\) be a matrix, let \(A\) be a set of its columns, and let \(b\) be a column. Then \(A\) implies \(b\) iff there are no two rows in \(M\) equal in \(A\) but different in \(b\). Furthermore, if \(X\) denotes the set of the columns of \(M\) then let \({\mathcal L}(A)\) denote the set of the functions \(2^X\rightarrow 2^X\) for which \({\mathcal L}(A)=\{a\in X: A\) implies \(a\}\). The \(m\times n\) matrix \(M\) represents the Sperner system \({\mathcal K}\subset 2^X\) iff \({\mathcal K}=\{K\in 2^X:{\mathcal L}(K)=X\) and \(K\) is minimal for this property\}. Finally \(s({\mathcal K})\) denotes the smallest integer \(m\) for which there exists an \(m\times n\) matrix \(M\) representing \(\mathcal K\). This paper gives a necessary and sufficient condition for the existence of an \(m\times n\) matrix \(M\) representing a given Sperner system. This gives a usefull tool to determine results concerning \(s({\mathcal K})\).
- Candidate Keys and Antichains
- Graph theory
- scientific article; zbMATH DE number 4074550 (Why is no real title available?)
- scientific article; zbMATH DE number 3666227 (Why is no real title available?)
- scientific article; zbMATH DE number 3464827 (Why is no real title available?)
- Minimum matrix representation of closure operations
- On minimum matrix representation of closure operations
- Perfect error-correcting databases
- The poset of closures as a model of changing databases
- Two conjectures of Demetrovics, Füredi, and Katona, concerning partitions
This page was built for publication: Minimum matrix representation of Sperner systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1382250)
