The workshop got off to a flying start with a talk by Devdatt on sorting under partial information. Given a partial order, the information-theoretic sorting bound says that the number of comparisons needed is at least logarithmic in the number of linear extension. Can this bound be achieved for an arbitrary partially ordered set? A simple counter-example shows that the constant factor must be greater than 1, unlike in sorting from scratch. How much greater? One approach to bounding this has been to search for a balanced pair in the poset: an incomparable pair which when ordered halves or almost halves the number of linear extensions. The search for a balanced pair has thrown up interesting conjectures and likely counter-examples, but there's miles to go. We were taken through the details of such an analysis for width-2 posets, and also shown something rather counter-intuitive, namely that it actually pays to be lopsided rather than search for an almost balanced pair. The search for balanced pairs was also given a geometrical perspective, and once we were down to mixed volumes, an inequality due to Alexandrov and Finchel popped up and did the deed. A good overview of this approach with several proofs fully described or at least sketched is provided by a recent survey of Brightwell [8], see also [16].
Later in the workshop, we returned to the theme of sorting under partial information, when graph entropy played a key role in discovering the optimal (not necessarily balanced) pair to compare at each stage. An overview follows in this report, eventually -- read on!