**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Hasse diagram

Summary

In order theory, a Hasse diagram (ˈhæsə; ˈ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 one represents each element of as a vertex in the plane and draws a line segment or curve that goes upward from one vertex to another vertex whenever covers (that is, whenever , and there is no distinct from and with ). 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 Garrett Birkhoff, 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 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.
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, in general, there are many different possible ways to draw a Hasse diagram for a given poset. The simple technique of just starting with the minimal elements 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 of a 4-element set ordered by inclusion . 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.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (1)

Related publications (8)

Related concepts (16)

Related people (1)

Related lectures (11)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

Covering relation

In mathematics, especially order theory, the covering relation of a partially ordered set is the binary relation which holds between comparable elements that are immediate neighbours. The covering relation is commonly used to graphically express the partial order by means of the Hasse diagram. Let be a set with a partial order . As usual, let be the relation on such that if and only if and . Let and be elements of . Then covers , written , if and there is no element such that .

Order theory

Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary. Orders are everywhere in mathematics and related fields like computer science. The first order often discussed in primary school is the standard order on the natural numbers e.

Product order

In mathematics, given a partial order and on a set and , respectively, the product order (also called the coordinatewise order or componentwise order) is a partial ordering on the Cartesian product Given two pairs and in declare that if and Another possible ordering on is the lexicographical order, which is a total ordering. However the product order of two total orders is not in general total; for example, the pairs and are incomparable in the product order of the ordering with itself.

Lattices for Abstract Interpretation

Covers lattices, abstract interpretation, fixpoint analysis, Hoare logic, and partial orders with extreme elements.

Relations, Sequences and Summations

Covers topics on relations, sequences, and summations, including lattices, recurrence relations, and sigma notation.

Partial Ordering: Relations, Sequences, Summation

Introduces partial orderings, lattices, and lexicographic orderings on Cartesian products.

, ,

The use of supplementary cementitious materials as a partial replacement for Portland cement is the most effective way to reduce the carbon footprint of the concrete industry. Raw clays containing kaolinite (kaolin) are promising substitute materials. In t ...

,

Water diversions from rivers and torrents for anthropic uses of the resource alter the natural flow regime. As a measure, environmental flows have been prescribed and often are enforced by law to follow policies (e.g., minimal flow, proportional redistribu ...

Anna Fontcuberta i Morral, Elias Zsolt Stutz, Mahdi Zamani, Simon Robert Escobar Steinvall

Thermodynamic phase diagrams are the cornerstones to develop synthesis of new materials. Zinc phosphide has evolved into a prospective semicontuctor for next generation solar cells, thanks to its abundance and functional properties. Here we derive an optim ...

2019