Posted research talk given at AMS Meeting

The research talk that I gave at the Joint Mathematics Meetings has now been posted to my talks webpage.  This talk was about the research that one of my groups accomplished this last summer during the Claremont REU.

Title Using TPA to count linear extensions

Authors Jacqueline Banks, Scott Garrabrant, Mark L Huber, and Anne Perizzolo

Abstract A linear extension of a poset P is a permutation of the elements of the set that respects the partial order. Let L(P) denotethe number of linear extensions. It is a #P complete problem to determine L(P) exactly for an arbitrary poset, and so randomized approximation algorithms that draw randomly from the set of linear extensions are used. In this work, the set of linear extensions is embedded in a larger state space with a continuous parameter. The introduction of a continuous parameter allows for the use of a more efficient method for approximating L(P) called TPA. Our primary result is that it is possible to sample from this continuous embedding in time that as fast or faster than the best known methods for sampling uniformly from linear extensions. For a poset containing n elements, this means we can approximate L(P) towithin a factor of 1 +  epsilon with probability at least 1 – delta using an expected number of random bits and comparisons in the poset which is at most O(n^3(ln n)(ln L(P))^2).

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: