PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Low Entry average rating: No information on entry rating
Hasse diagram (Definition)

If $ (A,\leq)$ is a finite poset, then it can be represented by a Hasse diagram, which is a graph whose vertices are elements of $ A$ and the edges correspond to the covering relation. More precisely an edge from $ x\in A$ to $ y\in A$ is present if

  • $ x < y$.
  • There is no $ z \in A$ such that $ x < z$ and $ z < y$. (There are no in-between elements.)
If $ x<y$, then in $ y$ is drawn higher than $ x$. Because of that, the direction of the edges is never indicated in a Hasse diagram.

Example: If $ A = \mathcal{P}(\{1,2,3\})$, the power set of $ \{1,2,3\}$, and $ \leq$ is the subset relation $ \subseteq$, then Hasse diagram is

$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & \{1,2,3\} & \ \{1,2\} \ar@{-... ...l] \ar@{-}[u] \ & \emptyset \ar@{-}[ul] \ar@{-}[u] \ar@{-}[ur] & } } \end{xy}$

Even though $ \{3\} < \{1,2,3\}$ (since $ \{3\} \subset \{1,2,3\}$), there is no edge directly between them because there are inbetween elements: $ \{2,3\}$ and $ \{1,3\}$. However, there still remains an indirect path from $ \{3\}$ to $ \{1,2,3\}$.



"Hasse diagram" is owned by bbukh. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: poset, partial order

Log in to rate this entry.
(view current ratings)

Cross-references: path, even, subset, power set, relation, covering, edges, vertices, graph, poset, finite
There are 14 references to this entry.

This is version 14 of Hasse diagram, born on 2002-02-02, modified 2004-04-11.
Object id is 1639, canonical name is HasseDiagram.
Accessed 10359 times total.

Classification:
AMS MSC05C90 (Combinatorics :: Graph theory :: Applications)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy
hmm... by xriso on 2002-02-02 03:11:26
I can't seem to get the diagram to show...
investigating now.
[ reply | up ]
  • yay! by xriso on 2002-02-02 03:55:12

Interact
post | correct | update request | add derivation | add example | add (any)