On edge decompositions of posets
An edge decomposition of a (finite) poset \(P\) is a collection of its subchains such that every pair of adjacent elements (one covers the other) belongs to exactly one chain. The author shows that the minimum size of edge decomposition of \(P\) equals the maximum of \(e(X,Y)-e(Y,X)\) over all partitions \(P=X\cup Y\) where \(e(X,Y)\) denotes the number of pairs \((x, y)\) in which \(x\in X\), \(y\in Y\) and \(y\) covers \(x\). For an \(n\)-cube \(B_n= (2^n, \subset)\) there is proved that it admits an edge decomposition into symmetric chains. The line poset \(L(P)\) of \(P\) is the set of pairs \((x,y)\) where \(y\) covers \(x\) and \((x,y)\) is less than \((x',y')\) iff \(y\leq x'\). A complete characterization of line posets is given: A poset \(L\) is isomorphic to \(L(P)\) for some \(P\) iff \(L\) is \(N\)-free and \(C_n\)-free for \(n\geq 3\) (here \(C_n\) denotes the poset \(\{x_1, \dots, x_n,y\}\) where \(x_{i+1}\) covers \(x_i\), \(y\) covers \(x_1\) and \(x_i\), \(y\) covers \(x_1\) and \(x_n\) covers \(y)\). Some numerical aspects are also considered.
scientific article; zbMATH DE number 1501337