Hasse Diagram

In order theory, a Hasse diagram ( /ˈhæsə/; German: /ˈhasə/) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set (S, ≤) one represents each element of S as a vertex in the plane and draws a line segment or curve that goes upward from x to y whenever y covers x (that is, whenever x < y and there is no z such that x < z < y). These curves may cross each other but must not touch any vertices other than their endpoints. Such a diagram, with labeled vertices, uniquely determines its partial order.

Hasse diagrams are named after Helmut Hasse (1898–1979); according to Birkhoff (1948), they are so-called because of the effective use Hasse made of them. However, Hasse was not the first to use these diagrams; they appear, e.g., in Vogt (1895). Although Hasse diagrams were originally devised as a technique for making drawings of partially ordered sets by hand, they have more recently been created automatically using graph drawing techniques.

The phrase "Hasse diagram" may also refer to the transitive reduction as an abstract directed acyclic graph, independently of any drawing of that graph, but this usage is eschewed here.

Read more about Hasse Diagram:  A "good" Hasse Diagram, Upward Planarity

Other articles related to "hasse diagram":

Hasse Diagram - Upward Planarity
... If a partial order can be drawn as a Hasse diagram in which no two edges cross, its covering graph is said to be upward planar ... A number of results on upward planarity and on crossing-free Hasse diagram construction are known If the partial order to be drawn is a lattice, then it can be drawn without ... it may be tested in linear time whether it has a non-crossing Hasse diagram ...

Famous quotes containing the word diagram:

    “God’s fire upon the wane,
    A diagram hung there instead,
    More women born than men.”
    William Butler Yeats (1865–1939)