On representing faces of a cube by subfaces (Q1368664)

The subject of the paper is the poset \([m]\) consisting of the integers \(0,1,\dots,m\) and partially ordered by the relation \(\leq\). This relation is defined by \(i\leq j\) iff either \(i=j\) or \(j=m\). Furthermore, denote by \([m]^n\) the \(n\)th cartesian power of the poset \([m]\). Clearly, \([m]^n\) is a ranked poset. For a ranked poset \((P,\prec)\) let \(P_l\) be the set of all elements of \(P\) of rank \(l\). For a subset \(A=\{x_1,\dots,x_j\}\) of \(P_l\) and an integer \(b<l\) we say that \(A\) has a system of distinct representatives (SDR) in \(P_{l-b}\) if there exist distinct elements \(y_1,\dots,y_j\in P_{l-b}\) with \(y_i\prec x_i\) for \(i=1,\dots,j\). The goal of the paper is to compute a bound \(C(b,l,P)\) on the cardinality of the set \(A\), so that if \(|A|\leq C(b,l,P)\) an SDR for the set \(A\) does exist and if \(|A|\) exceeds this bound the existence of an SDR is not guaranteed in general. Such a result concerning the poset \([1]^n\) (i.e. the \(n\)-cube) is known as Katona's marriage theorem. The author extends the Kruskal-Katona method for computing the minimal shadows in the \(n\)-cube and applies it for the poset \([m]^n\). This result is used in the algorithm for computing an SDR bound.