Context Navigation

← Previous Ticket
Next Ticket →

#29687 closed enhancement (fixed)

Efficiently Counting Linear Extensions of Specific Poset Families

Reported by:	gh-sgrosser	Owned by:	gh-sgrosser
Priority:	major	Milestone:	sage-9.3
Component:	combinatorics	Keywords:	gsoc2020 poset linear extension
Cc:	nthiery, saliola, aschilling, tscrim	Merged in:
Authors:	Stefan Grosser	Reviewers:	Travis Scrimshaw
Report Upstream:	N/A	Work issues:
Branch:		Commit:
Dependencies:		Stopgaps:

Status badges

Description (last modified by gh-sgrosser)

This is a meta ticket for the following GSoC 2020 project by Stefan Grosser, mentored by Travis Scrimshaw. Project Proposal

The goal will be to add multiple classes to FinitePoset? such as d-complete, tree, and mobile, where all of these families have individual interest. Specifically, all of these classes permit efficient computation of the number of linear extensions.

Three main tickets were worked on: #28237 #29686 #30220

In 28237, I wrapped up the implementation of Atkinson's algorithm, used to compute the number of linear extensions of Tree posets. This tied in for the LinearExtensionsOfForest class created. In 29686, I worked on implenting the forest posets and d-complete posets, along with their linear extensions. Finally in 30220, I worked on the implementation of mobile posets and the counting of their linear extensions. Additionally, I made several example posets (seen in #30273)