A linear extension of a partially ordered set is a permutation
of the elements
,
, ... of
such that
implies
. For example, the linear extensions of the partially ordered set
are 1234, 1324, 1342, 3124, 3142, and 3412, all
of which have 1 before 2 and 3 before 4.
Nash (2026) reports an exact uniform sampling algorithm for linear extensions of a partially
ordered set represented by adjacency lists
of an acyclic digraph with vertices. The sum of the indegree and outdegree of
each vertex is at most a fixed
, and each directed graph
path has at most a fixed
vertices. The expected cost
is
arithmetic operations and fair random bits, with constants
depending on
and
. The expected arithmetic bit
cost is
in a random access machine model. Nash credits
GPT-6 Astra with the mathematical work. The sampling proof
is in an appendix that the author identifies as AI-generated and excludes from the
reported human review of the main text.