Counting restricted posets

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