Shuffling with rules: drawing uniformly from linear extensions of a partial order

09/11/2012 - 12:15pm
09/11/2012 - 1:10pm
Speaker: 
Mark Huber (Claremont McKenna College)
Abstract: 

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.

Where: 
Millikan 208 (Pomona College)
Misc. Information: 

There will be a short organizational meeting for the ANTC seminar preceding Mark's talk at 12:00 noon in the same room.