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

  1. After that, each sport category is available, allowing individuals to play their favourite niche. Many players attempt to land their wins on penny slots, the most inexpensive slot machine video games in online playing. If you might be} certainly one of them, consideration to|take note of} the subsequent slot suggestions – particularly should you suppose you have have} found gold the moment you discovered a penny slot machine with a progressive jackpot. Instead of utilizing real-life currency, House of Fun slot machines use in-game coins and 바카라사이트 merchandise collections only.

    ReplyDelete
  2. Celebrating 15 years of presenting games in 15 languages, Evolution is momentously thriving beyond our 10 studios, 11,000 workers, and 20 countries and cities. Our North American expertise broadcasts 24/7 from our studios in Atlantic City, New Jersey, Southfield, Michigan, Philadelphia, Pennsylvania, and Vancouver, Canada. Other race sports 카지노사이트 are additionally authorized and regulated, these typically embrace biking and motor boat racing although these each come under the jurisdiction of the Ministry of Culture and Tourism. The Royal Palace Casino Jeju is on the smaller aspect at 166 square meters only.

    ReplyDelete
  3. Virgin Casino was among the first manufacturers to enter the US market. It's products run easily on all platforms and offer a broad selection of slots, bingo and free video games. Party Casino is a part of|is half of} the multinational gaming group Entain. It provides a huge range of progressive jackpots and unique slots tournaments, with 24/7 assist. Conveniently, there are additionally sheets at the desk so that you can} hold observe of your rating. Note that 카지노 the content on this site should not be thought of betting recommendation.

    ReplyDelete

Post a Comment

Popular posts from this blog

The Catalan Grenade is Accepting Papers!

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

Number-on-the-Forehead Communication Complexity