Google Summer of Code 2020: D-Complete and Mobile Posets

In this post, I thought I'd overview the work of my first paper, which has just recently been accepted to SIDMA. 

In order theory, a linear extension of a partially ordered set P is a totally ordered set L which respects the original ordering P. Many famous problems can be converted into counting the number of linear extensions. For example, the number of standard Young tableaux of a given shape is equivalent to the number of linear extensions of a poset with the same shape.

Unfortunately, it is #P-complete in general to count linear extensions (even for posets of height 2!). However, there are famous classes of posets like Young diagrams (or more generally, d-complete posets), which have efficient computation. In our paper, we presented a new class of posets called mobiles that have determinant formulas for counting linear extensions and generalize d-complete posets and ribbon posets.


Since this past summer converted me into a shut-in, I decided to spend some of that extra time to participate in Google Summer of Code. With Travis Scrimshaw, I implemented the work of my paper in SageMath.  

For code documentation and access, see this meta-ticket, which has links to everything. But here's a quick tldr of the main contributions:

1. Created classes and examples for various families of posets (i.e. d-complete, mobiles)
2. Added functions to identify when a poset is d-complete, mobile, etc
3. Added new functions to efficiently count the number of linear extensions of d-complete and mobile posets. 


If you plan to use this code, please let me know! I'd love to see this being used. 

In the future, I plan to add q-analogues of mobiles, which unfortunately did not fit in the time frame of Google Summer of Code. 




Comments

Popular posts from this blog

Derandomization of BPP Using Hitting Set Generators

Number-on-the-Forehead Communication Complexity

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication