### 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.

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.

This comment has been removed by a blog administrator.

ReplyDeleteThis comment has been removed by a blog administrator.

ReplyDeleteThis comment has been removed by a blog administrator.

ReplyDelete