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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Partial Order and Chain Decomposition of the Set of k-Subsets

  • Hasmik Sahakyan,
  • Levon Aslanyan

摘要

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.