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.
Linear Extension
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.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 ExtensionCite this as:
Weisstein, Eric W. "Linear Extension." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LinearExtension.html