Minimum matrix representation of Sperner systems (Q1382250)

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})\).