04/17/2018 - 12:15pm

04/17/2018 - 1:10pm

Speaker:

Sam Dittmer (UCLA)

Abstract:

The study of linear extensions of posets has applications ranging from combinatorics to computer science to voting theory. In 1991, Brightwell and Winkler showed that the number of linear extensions of a poset is #P-complete. We extend this result to posets with certain restrictions. First, we prove that the number of linear extensions of a poset of height two is #P-complete. This resolves the Brightwell-Winkler conjecture. Next, we present an overview of a proof that the number of linear extensions of a poset of dimension two is #P-complete. This problem is equivalent to computing the size of a principal ideal in the weak Bruhat order, a fundamental object in algebraic combinatorics. The proof includes a brute force computer search used to construct certain families of logic gates. It is, to the best of our knowledge, the first computer assisted proof of #P-completeness, and the first proof to use algebraic systems to encode logic gates. Joint work with Igor Pak.

Where:

Millikan 2099, Pomona College

__Claremont Graduate University__ | __Claremont McKenna__ | __Harvey Mudd__ | __Pitzer__ | __Pomona__ | __Scripps__

Proudly Serving Math Community at the Claremont Colleges Since 2007

Copyright © 2018 Claremont Center for the Mathematical Sciences