On the width of an orientation of a tree (Q1112850)

Let T be an unrooted tree with n vertices and \(\lambda\) leaves. Each of the n-1 edges of T can be oriented in one of two directions, and so there are \(2^{n-1}\) ways in which T can be oriented. Each of these orientations of T can be regarded as the Hasse diagram of a partially ordered set whose width is simply the size of the largest anti-chain in the partially ordered set. The authors determine the maximal and minimal widths these partially ordered sets can have. First, they construe T as a bipartite graph and observe that a bipartition of T produces two canonical orientations of T, each of which maximizes the width. Second, they show that the minimal width is either \(\lfloor \lambda /2\rfloor\) or \(\lfloor \lambda /2\rfloor +1\). Last, they give algorithms to determine the maximal width and to construct the minimal width orientation.