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

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

Derandomization of BPP Using Hitting Set Generators

Number-on-the-Forehead Communication Complexity