HOME

TheInfoList




In
order theory Order theory is a branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geom ...
, a Hasse diagram (; ) is a type of
mathematical diagram, ms. from Lüneburg, A.D. 1200 Mathematical diagrams, such as chart A chart is a graphical representation for data visualization, in which "the data Data are units of information Information can be thought of as the resolution of u ...
used to represent a finite
partially ordered set upright=1.15, Fig.1 The Hasse diagram of the Power set, set of all subsets of a three-element set \, ordered by set inclusion, inclusion. Sets connected by an upward path, like \emptyset and \, are comparable, while e.g. \ and \ are not. In mathem ...
, in the form of a
drawing Drawing is a form of visual art The visual arts are art forms such as painting Painting is the practice of applying paint Paint is any pigmented liquid, liquefiable, or solid mastic composition that, after application to a su ...
of its
transitive reductionIn mathematics, a transitive reduction of a directed graph ''D'' is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices ''v'', ''w'' a (directed) path from ''v'' to ''w'' in ''D'' exists if ...
. Concretely, for a partially ordered set ''(S, ≤)'' one represents each element of ''S'' as a
vertex Vertex (Latin: peak; plural vertices or vertexes) means the "top", or the highest geometric point of something, usually a curved surface or line, or a point where any two geometric sides or edges meet regardless of elevation; as opposed to an Apex ( ...
in the plane and draws a
line segment In geometry Geometry (from the grc, γεωμετρία; ' "earth", ' "measurement") is, with , one of the oldest branches of . It is concerned with properties of space that are related with distance, shape, size, and relative position ...

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. The diagrams are named after
Helmut Hasse Helmut Hasse (; 25 August 1898 – 26 December 1979) was a Germany, German mathematician working in algebraic number theory, known for fundamental contributions to class field theory, the application of p-adic number, ''p''-adic numbers to local c ...

Helmut Hasse
(1898–1979); according to , they are so called because of the effective use Hasse made of them. However, Hasse was not the first to use these diagrams. One example that predates Hasse can be found in . 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 Graph drawing is an area of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical ...
techniques. The phrase "Hasse diagram" may also refer to the transitive reduction as an abstract
directed acyclic graph In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

directed acyclic graph
, independently of any drawing of that graph, but this usage is eschewed here.


Diagram design

Although Hasse diagrams are simple as well as intuitive tools for dealing with finite posets, it turns out to be rather difficult to draw "good" diagrams. The reason is that there will in general be many possible ways to draw a Hasse diagram for a given poset. The simple technique of just starting with the
minimal element In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
s of an order and then drawing greater elements incrementally often produces quite poor results: symmetries and internal structure of the order are easily lost. The following example demonstrates the issue. Consider the
power set In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities an ...
of a 4-element set ordered by inclusion \subseteq. Below are four different Hasse diagrams for this partial order. Each subset has a node labelled with a binary encoding that shows whether a certain element is in the subset (1) or not (0): The first diagram makes clear that the power set is a
graded poset 300px, A partially ordered by Inclusion (set theory), inclusion, with rank defined as number of elements, forms a graded poset. In mathematics, in the branch of combinatorics, a graded poset is a partially ordered set (poset) ''P'' equipped with a ...
. The second diagram has the same graded structure, but by making some edges longer than others, it emphasizes that the
4-dimensional cube
4-dimensional cube
is a combinatorial union of two 3-dimensional cubes, and that a tetrahedron ( abstract 3-polytope) likewise merges two triangles ( abstract 2-polytopes). The third diagram shows some of the internal symmetry of the structure. In the fourth diagram the vertices are arranged like the elements of a 4×4
matrix Matrix or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols, or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the material in between a eukaryoti ...
.


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 crossings if and only if it has
order dimension Image:Order dimension.svg, 240px, A partial order of dimension 4 (shown as a Hasse diagram) and four total orderings that form a realizer for this partial order. In mathematics, the dimension of a partially ordered set (poset) is the smallest number ...

order dimension
at most two. In this case, a non-crossing drawing may be found by deriving Cartesian coordinates for the elements from their positions in the two linear orders realizing the order dimension, and then rotating the drawing counterclockwise by a 45-degree angle. *If the partial order has at most one
minimal element In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
, or it has at most one
maximal element In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
, then it may be tested in
linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by th ...
whether it has a non-crossing Hasse diagram. *It is
NP-complete In computational complexity theory Computational complexity theory focuses on classifying computational problem In theoretical computer science An artistic representation of a Turing machine. Turing machines are used to model general computi ...
to determine whether a partial order with multiple sources and sinks can be drawn as a crossing-free Hasse diagram. However, finding a crossing-free Hasse diagram is fixed-parameter tractable when parametrized by the number of
articulation pointImage:Graph-Biconnected-Components.svg, alt=An example graph with biconnected components marked, Each color corresponds to a biconnected component. Multi-colored vertices are cut vertices, and thus belong to multiple biconnected components. In graph ...
s and triconnected components of the transitive reduction of the partial order. *If the ''y''-coordinates of the elements of a partial order are specified, then a crossing-free Hasse diagram respecting those coordinate assignments can be found in linear time, if such a diagram exists.. In particular, if the input poset is a
graded poset 300px, A partially ordered by Inclusion (set theory), inclusion, with rank defined as number of elements, forms a graded poset. In mathematics, in the branch of combinatorics, a graded poset is a partially ordered set (poset) ''P'' equipped with a ...
, it is possible to determine in linear time whether there is a crossing-free Hasse diagram in which the height of each vertex is proportional to its rank.


UML notation

The standard diagrama for a chain of inclusions is the UML class, connecting sets by the inheritance relation. The illustration shows a
nested set collection
nested set collection
, ''C'': : ''B'' = ;     ''B''1 = ;   ''B''2 = ;   ''B''3 = ;
''C'' = .


Notes


References

*. *. *. *. *. *. An extended preprint is available online

*. *. *. *.


External links

* * {{mathworld, urlname=HasseDiagram, title=Hasse Diagram Order theory Diagrams Graph drawing Graphical concepts in set theory