Shuffling with rules: drawing uniformly from linear extensions of a partial order
Suppose I try to shuffle a deck of n cards by randomly transposing adjacent cards. It turns out you need to do this O(n^3 ln(n)) times to really mix up the deck. Now suppose I add some extra rules that look like: "The King of Hearts must be above the Queen of Spades" or "The Queen of Spades must be above the 9 of Diamonds" and so on. I will shuffle the same way, but if an adjacent transposition would cause me to violate one of my rules, I do not execute the transposition. The surprising fact is that it still takes O(n^3 ln(n)) steps to mix up the deck! Now these shuffles with rules is more formally known as linear extensions of a partial order. In this talk I will show where the O(n^3 ln(n)) is coming from, and show how to exactly draw uniformly from the set of linear extensions. I will also discuss recent work on this problem and why embedding this problem in a continuous context can lead to better algorithms for counting linear extensions.
There will be a short organizational meeting for the ANTC seminar preceding Mark's talk at 12:00 noon in the same room.