Changes between Initial Version and Version 9 of Ticket #28237


Ignore:
Timestamp:
07/26/19 16:53:57 (3 years ago)
Author:
jmatherne
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #28237

    • Property Status changed from new to needs_review
    • Property Authors changed from to Galen Dorpalen-Barry, Bryan Gillespie, Jacob P. Matherne, Thomas McConville, Franco Saliola
    • Property Component changed from PLEASE CHANGE to combinatorics
    • Property Summary changed from Atkinson's algorithm for counting linear extensions of (tree) posets to Implement Atkinson's algorithm for counting linear extensions of (tree) posets
    • Property Owner changed from (none) to jmatherne
    • Property Branch changed from to u/jmatherne/atkinson_s_algorithm_for_counting_linear_extensions_of__tree__posets
    • Property Keywords IMA Coding Sprints days99 linear extensions posets trees spectrum added
    • Property Commit changed from to fd63ff1f5e32c68a8cedca4a6fdcd81b02f353ce
    • Property Type changed from PLEASE CHANGE to enhancement
  • Ticket #28237 – Description

    initial v9  
     1We add two methods to posets.py:
     2
     3- "spectrum" - This method has input a poset `P` and an element `a` of `P`.  It outputs the `a`-spectrum of `P`, which is a list of integers whose i-th entry contains the number of linear extensions of `P` with `a` in the i-th position.  In particular, the sum of the entries of the `a`-spectrum is the number of linear extensions of `P`.
     4
     5- "atkinson" - This method has input a poset `P`, whose underlying undirected graph is a forest, and an element `a` of `P`.  It uses Atkinson's algorithm (see reference below) to compute the `a`-spectrum of `P` (see definition of `a`-spectrum above).
     6
     7M. D. Atkinson, ''On computing the number of linear extensions of a tree'', Order '''7''' (1990), 23-25.