Georgia Institute of Technology College of Sciences

Graded posets are partially ordered sets equipped with a unique rank function that respects the partial order and such that neighboring elements in the Hasse diagram have ranks that differ by one. We frequently find them throughout combinatorics, including the canonical partial order on Young diagrams and plane partitions, where their respective rank functions are the area and volume under the configuration. We ask when it is possible to efficiently sample elements with a fixed rank in a graded poset. We show that for certain classes of posets, a biased Markov chain that connects elements in the Hasse diagram allows us to approximately generate samples from any fixed rank in expected polynomial time. While varying a bias parameter to increase the likelihood of a sample of a desired size is common in statistical physics, one typically needs properties such as log-concavity in the number of elements of each size to generate desired samples with sufficiently high probability. Here we do not even require unimodality in order to guarantee that the algorithm succeeds in generating samples of the desired rank efficiently. This joint work with Prateek Bhakta, Ben Cousins, and Dana Randall will appear at SODA 2017.