19.3: Graph for a partial order

Elementary Foundations: An Introduction to Topics in Discrete Mathematics · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    From LibreTexts, under GNU Free Documentation, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    Definition: Hasse diagram

    a diagram for the graph for a partial order on a finite set \(A\text{,}\) omitting reflexive loops and transitive “composite” edges, and placing “smaller” elements lower on the diagram instead of using arrows

    Example \(\PageIndex{1}\): Hasse diagram for division of integers.

    Let \(A = \{2,4,6,8,10,12\}\text{.}\) The Hasse diagram of the partial order \(\mathord{\mid}\) (i.e. “divides”) on \(A\) appears in Figure \(\PageIndex{1}\). Notice that \(2\) is not joined directly to either \(8\) or \(12\text{,}\) since we can use transitivity and the facts that \(2 \mid 4\) and \(2 \mid 6\) to infer \(2 \mid 8\) and \(2 \mid 12\text{,}\) respectively, from the diagram.

    clipboard_e974445b6e9420c633a8cf107930dd672.png
    Figure \(\PageIndex{1}\): The Hasse diagram for the “divides” partial order on a finite set of integers.
    Remark \(\PageIndex{1}\)

    See Example 14.4.2 for another example of a graph for the “divides” relation.

    Example \(\PageIndex{2}\): Hasse diagram for subset order.

    The graph from Example 14.4.1 has been reproduced in Figure \(\PageIndex{2}\) as a Hasse diagram, and represents the partial order \(\mathord{\subseteq}\) on \(\mathscr{P}(\{a,b,c\})\text{.}\)

    clipboard_e9f2d35321d8d94b2259bc27e51790444.png
    Figure \(\PageIndex{2}\): The Hasse diagram for the subset partial order on the power set of a finite set.

    This page titled 19.3: Graph for a partial order was last modified on Tue, 01 Sep 2026 03:36:00 GMT and is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Jeremy Sylvestre via source content that was edited to the style and standards of the LibreTexts platform.