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.
- A chain decomposition theorem
- Decompositions of partially ordered sets into chains and antichains of given size
- Peckness of edge posets
- Symmetric chain decompositions of products of posets with long chains
- Gray codes and symmetric chains
- On orthogonal symmetric chain decompositions
- Cubical convex ear decompositions
- On the central levels problem
- scientific article; zbMATH DE number 6533648 (Why is no real title available?)
- scientific article; zbMATH DE number 1506764 (Why is no real title available?)
- Gray codes and symmetric chains
- Orthogonal Symmetric Chain Decompositions of Hypercubes
- On orthogonal symmetric chain decompositions
- On the central levels problem
This page was built for publication: On edge decompositions of posets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1577313)
