GSoC'2020 Introduction and New Proposal

[Stefan Grosser]

Hi all,

My name is Stefan Grosser, and I am a Master's student in Mathematics at McGill. My primary interests are in extremal and algebraic combinatorics, as well as theoretical computer science. To see a bit more about me, please visit my site or contact me here!

I have a year of experience in Sagemath, using it primarily for a course in convex polytopes and for a research project in algebraic combinatorics. In general, I have many years of experience coding in Python, both at university and at multiple internships. In terms of mathematics, I have many years of experience in algebra, combinatorics, and analysis.

I would like to propose a new potential project, one very closely aligned with some of my research. I would love some feedback on the idea!

Linear Extensions of Posets

Linear extensions of partially ordered sets are fundamental in order theory and in algebraic combinatorics, holding high importance in the study of permutations and Young tableaux. Computing the number of linear extensions, in general, takes O(n!) time, given a poset of n elements. However, many efficient algorithms are known for certain large classes of posets. Sagemath offers a single function to calculate the linear extensions of a poset. For even small posets, this quickly becomes impossible to use for even small posets. The goal of this project would be to implement efficient methods of computing linear extensions of several classes of posets. This includes tree posets [1], d-complete posets [2], skew diagrams [3], mobile posets [4], and more.

The possible mentorship of Travis Scrimshaw would be fantastic! 

[1] Atkinson, Mike D. "On computing the number of linear extensions of a tree." Order 7.1 (1990): 23-25.

[2] Proctor, Robert A. "Dynkin diagram classification of λ-minuscule Bruhat lattices and of d-complete posets." Journal of Algebraic Combinatorics 9.1 (1999): 61-94.

[3] Jacobi-Trudi Identities, https://en.wikipedia.org/wiki/Schur_polynomial#Jacobi%E2%88%92Trudi_identities

[4] Garver, A., Grosser, S., Matherne, J. P., & Morales, A. H. (2020). Counting linear extensions of posets with determinants of hook lengths. arXiv preprint arXiv:2001.08822.

[Travis Scrimshaw]

Hi Stefan,

   This sounds like an interesting project, and it would be good to take advantage of posets that have extra structure. I imagine would require working with the class structure for posets and implementing some new (but simple) categories in Sage. Then other methods could be added to these more specialized classes of posets that other researchers can benefit from. We can talk more of the specifics over email as you draft your proposal.

Best,

Travis