Giving the Algebra/Number Theory/Combinatorics Seminar talk in Claremont today

I’m speaking about some of the work that I have done on randomly generating, and counting the number of, linear extensions of a poset.

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.

See here for more details.

Advertisements

,

  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: