Linear extensions of semiorders: a maximization problem

✍ Scribed by Peter C. Fishburn; W.T. Trotter

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 926 KB
• Volume: 103
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90036-f

✦ Synopsis

We consider the problem of determining which partially ordered sets on n points with k pairs in their ordering relations have the greatest number of linear extensions. The posets that maximize the number of linear extensions for each hxed (n, k), 0 G k G (;), are semiorders. However, except for special cases, it appears difficult to say precisely which semiorders solve the problem. We give a complete solution for k G n, a nearly complete solution for k = n + 1, and comment on a few other cases. Let (n, >0) denote the set n = (1, 2, . . . , n} partially ordered by an irreflexive and transitive relation >,, c n2, and let e(n, >J = I{ (n, >*): >* is an irreflexive, transitive and complete (a # b j a >* b or b >* a) relation in n2 that includes >,,} 1, be the number of linear extensions of (n, >O). We consider the problem of determining the posets that maximize e(n, Bo) when >0 has exactly k ordered pairs in n2. That is, given 0 c k c (;) and letting p(n, k) = {(n, >o): PO1 = k), 0, k) = pg=j eh >d,