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 On Friday, March 20, 2020 at 8:32:04 PM UTC+10, Stefan Grosser wrote: > > 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 <https://blog.catalangrenade.com/p/about.html> or contact > me here <javascript:>! > 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*. > -- You received this message because you are subscribed to the Google Groups "sage-gsoc" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-gsoc/316876d6-e735-4311-a84d-0570c608782a%40googlegroups.com.
