On some new types of greedy chains and greedy linear extensions of partially ordered sets (Q1894377): Difference between revisions

The author's presence in both practical as well as theoretical aspects of research into the details of the jump number problem has been long established. In this paper the author provides an insightful theoretical discussion concerning the role that strongly greedy and semi-strongly greedy chains (defined here also) play in the construction of greedy linear extensions which deform to those from which the jump number may be more efficiently determined by restricting the search space for any (suitable) algorithm. Thus Theorem 1: If a poset \(P\) contains a strongly greedy chain \(C\), then every greedy linear extension \(L\) of \(P\) can be transformed to a greedy linear extension \(L^*\) of \(P\) which begins with \(C\) and such that \(S(P, L^*)\leq S(P,L)\) (the jump number). This leads to: Corollary 1. If a poset \(P\) contains a strongly greedy chain \(C\), then \(P\) has an optimal linear extension which begins with \(C\) and such that \(S(P)= S(P- C)+1\). Theorem 2: If a poset \(P\) has no strongly greedy chain, then it has a semi-strongly greedy chain, establishes a branching whence. Theorem 3 becomes Theorem 1 for the semi-strongly greedy chain case. For those interested in the structure theory of (finite) posets the discussion in this paper is possibly most relevant because of perspectives on additional refined classifications going beyond being series-parallel or \(N\)-free, for example, to classes also sufficiently well-defined to permit the establishment of otherwise NP-complete algorithms as being polynomial-time. The fact that this is so suggests that useful invariants may be associated with such classes. As observed by the author one such is a non-\(N\)-freeness degree directly useful in complexity estimations which will also put limits on other parameters associated with posets.