TOPICS
Search

Linear Extension


A linear extension of a partially ordered set P is a permutation of the elements p_1, p_2, ... of P such that p_i<p_j implies i<j. For example, the linear extensions of the partially ordered set ((1,2),(3,4)) 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 n vertices. The sum of the indegree and outdegree of each vertex is at most a fixed d, and each directed graph path has at most a fixed h vertices. The expected cost is O(nlogn) arithmetic operations and fair random bits, with constants depending on d and h. The expected arithmetic bit cost is O(nlog^2n) 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.


Explore with Wolfram|Alpha

References

Brightwell, G. and Winkler, P. "Counting Linear Extensions." Order 8, 225-242, 1991.Brualdi, R. A. Introductory Combinatorics, 4th ed. New York: Elsevier, 1997.Bubley, R. and Dyer, M. "Faster Random Generation of Linear Extensions." In Proc. Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, Calif., pp. 350-354, 1998.Nash, N. "An Optimal Deterministic Adversary for Sorting." Version 2. Hexagon, 2026. https://hexagonmath.org/2611.00196v2.Preusse, G. and Ruskey, F. "Generating Linear Extensions Fast." SIAM J. Comput. 23, 373-386, 1994.Varol, Y. and Rotem, D. "An Algorithm to Generate All Topological Sorting Arrangements." Comput. J. 24, 83-84, 1981.

Referenced on Wolfram|Alpha

Linear Extension

Cite this as:

Weisstein, Eric W. "Linear Extension." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LinearExtension.html

Subject classifications