Abstract: An application oriented class of partially ordered sets is considered. Let P(n,k) denotes the set of all k -tuples with strictly increasing elements from the set N  {1,2,,n} and 1  k  n . Some properties of P(n,k) is studied in terms of partially ordered sets. An algorithm that constructs a set of non intersecting increasing chains that cover all elements of P(n,3) is brought. The number of these chains is the minimal possible: it equals to the width of P(n,3) , i.e. the largest cardinality of an antichain. Analogous to the Hansel’s well known algorithm for identification of monotone Boolean functions, the chains constructed for P(n,3) can be used for identification of monotone functions defined on P(n,3) .

Keywords: partially ordered sets, chain split.

ACM Classification Keywords: G.2.1 Discrete mathematics: Combinatorics

Link:

CHAIN SPLIT OF PARTIALLY ORDERED SET OF K-SUBSETS

Hasmik Sahakyan, Levon Aslanyan

http://foibg.com/ibs_isc/ibs-18/ibs-18-p07.pdf