On edge decompositions of posets
type: Item
instance of: scholarly article
title: On edge decompositions of posets
zbMATH Open document ID: 0961.06002
DOI: 10.1023/A:1006419611661
author: Oleg Pikhurko
published in: Order
publication date: 2000-09-04T00:00:00Z
review text: 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.
reviewed by: Vitězslav Novák
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 1501337
zbMATH Keywords: \(n\)-cube
zbMATH Keywords: edge decomposition
zbMATH Keywords: poset
zbMATH Keywords: symmetric chains
zbMATH Keywords: line poset
MaRDI profile type: Publication
full work available at URL: a:1006419611661
OpenAlex ID: W75981726
description: scientific article; zbMATH DE number 1501337