Partial Order and Chain Decomposition of the Set of k-Subsets
摘要
Let P(n, k) denote the set of all k-tuples with strictly increasing elements from the set \([n]=\{1,2,\cdots ,n\}, 1 \le k \le n\) . Through a bijective mapping to binary sequences, P(n, k) is associated with the k-th layer \(L_k\) of the binary cube \(B^n\) . On the other hand, an arbitrary subset \(M \subseteq L_k\) , with \(|M|=r\) , \(r\le \left( {\begin{array}{c}n\\ k\end{array}}\right) \) can be viewed as the incidence matrix of a simple k-uniform hypergraph with n vertices and r hyperedges. The hypergraph degree sequence problem is NP-complete for simple k-uniform hypergraphs, starting from \(k=3\) . This motivates our study of P(n, 3). We investigate properties of the Hasse diagram of the partially ordered set \((P(n,k),\preceq )\) , where \(\preceq \) is a component-wise partial order. An algorithm is presented that constructs a set of non-intersecting chains covering all elements of P(n, 3). The number of these chains equals the width of \((P(n,k),\preceq )\) , and they can be used for the identification of monotone functions defined on P(n, 3). One motivation for studying these functions is that the degree sequences of the corresponding hypergraphs can be used to generate all degree sequences of uniform hypergraphs. Moreover, monotone Boolean functions defined on \(B^n\) play a special role in generating the degree sequences of simple hypergraphs. We consider the case of 3-uniform hypergraphs, the corresponding monotone Boolean functions, and provide complexity estimates for their identification.