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. pattiquennevilleNovember 6, 2022 at 7:59 PM

    This comment has been removed by a blog administrator.

    ReplyDelete
  2. uktredhackmannNovember 8, 2022 at 7:03 PM

    This comment has been removed by a blog administrator.

    ReplyDelete
  3. jaimilaeastesNovember 8, 2022 at 8:57 PM

    This comment has been removed by a blog administrator.

    ReplyDelete

Post a Comment

Popular posts from this blog

The Catalan Grenade is Accepting Papers!

-
As an inaugural post to this blog, I will announce that I am perpetually accepting papers! Here at the Catalan Grenade, I'll be going through papers on cool results, old and new, in Combinatorics and Algebra. Currently, I am a recent graduate from UMass Amherst (Fall 2018), and am waiting to hear back from grad schools. This seems like a fun way to pass the time.
Read more

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

-
A classical result from Yannakakis states that $$\text{xc}(P) = \text{rank}_+(S),$$ where \(P\) is a polytope with slack matrix \(S\). Yannakakis further showed that with nondeterministic communication complexity, one can give a lower bound for the nonnegative rank. This lower bound is sufficient to prove that some polytopes, like the correlation polytope, have exponential extension complexity. However, it fails for many other examples.  In a 2013 paper, "Extended formulations, nonnegative factorizations, and randomized communication protocols," by Faenza, Fiorini, Grappe, and Tiwary, they show that a model of randomized communication complexity can not only lower bound nonnegative rank, but exactly characterize it.  In my communication complexity reading group, I gave a talk presenting this paper and its results. The proofs are extremely elegant and simple, making for a very enjoyable read.  For those interested, here is a link to my lecture notes! 
Read more

Number-on-the-Forehead Communication Complexity

-
 Since the Winter 2020 semester at McGill, I've helped run a Communication Complexity reading group attended by undergraduate and graduate students. Recently, I became particularly excited by the Number-on-the-Forehead model, and gave a talk on it in the reading group.  The idea is quite simple. For 2 player communication, imagine that Alice's input is on top of Bob's forehead, making it easy for Alice to see but impossible for Bob to see. Likewise, Bob's input is on Alice's forehead.  This generalizes to k-player problems where k people stand in a circle, each with a card on their forehead indicating some information that is viewable to everyone but the forehead owner.  If this still doesn't make sense, think of this scene from The Office.  Here are the  lecture notes  I wrote for the talk. I cover basic definitions, Behrend's bound and it's application to the Exactly-N problem, and Ramsey Theoretic lower bounds on cylinders.  As I liked this topic so
Read more