THE GRAPH OF LINEAR EXTENSIONS REVISITED.

The graph of linear extensions G(P) of a poset P has as vertices the linear extensions of P, and two vertices are adjacent if they differ only by an adjacent transposition. This graph has so far been investigated mainly with respect to Hamilton paths and intrinsic geodesic convexity. The work on the latter topic especially shows how the graph-theoretic properties of G(P) reflect the order-theoretic structure of P. The aim of this paper is to study the graph G(P) with respect to topics from classical graph theory, e.g., connectivity, cycle space, isometric embeddings, and to find order-theoretic interpretations of these notions. The main theorems in this paper are the equality of the connectivity of G(P) and the jump number of P, the existence of a certain generating system for the cycle space, and a relationship of P and its subposets obtained via an embedding of the graph of linear extensions. [ABSTRACT FROM AUTHOR]