Opened 15 months ago

Closed 8 months ago

#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)

Change History (12)

comment:1 Changed 15 months ago by gh-sgrosser

  • Description modified (diff)
  • Owner changed from (none) to gh-sgrosser

comment:2 Changed 15 months ago by gh-sgrosser

  • Keywords gsoc2020 added; gsoc removed

comment:3 Changed 14 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

comment:4 Changed 14 months ago by tscrim

See also #28237.

comment:5 Changed 11 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:6 Changed 11 months ago by gh-sgrosser

  • Description modified (diff)
  • Status changed from new to needs_review

comment:7 Changed 11 months ago by gh-sgrosser

  • Status changed from needs_review to positive_review

comment:8 Changed 11 months ago by mkoeppe

full author, reviewer names

comment:9 Changed 11 months ago by mkoeppe

  • Status changed from positive_review to needs_work

comment:10 Changed 11 months ago by gh-sgrosser

  • Authors changed from gh-sgrosser to Stefan Grosser
  • Reviewers changed from tscrim to Travis Scrimshaw

comment:11 Changed 11 months ago by mkoeppe

  • Status changed from needs_work to positive_review

comment:12 Changed 8 months ago by chapoton

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.