On Entropy and Extensions of Posets

Abstract

A vast body of literature in combinatorics and computer science aims at understanding the structural properties of a poset P implied by placing certain marginal constraints on the uniform distribution over linear extensions of P . These questions are typically concerned with whether or not P must be a total order (or have small width). Here, we instead consider whether or not these marginal constraints imply a non-trivial bound on the entropy of the uniform distribution (over the set of linear extensions of P ). We prove such a result and establish that local bounds do indeed yield global bounds. ∗This research was supported in part by an NSF Computing and Innovation Fellowship.

Topics

1 Figures and Tables

Download Full PDF Version (Non-Commercial Use)