maths.free › Combinatorics & Graph Theory › Partially Ordered Sets › Basic Notation and Terminology

Basic Notation and Terminology

A partially ordered set or poset \bfP is a pair (X,P) where X is a set and P is a reflexive, antisymmetric, and transitive binary relation on X.

Basic Notation and Terminology

A partially ordered set or poset \(\bfP\) is a pair \((X,P)\) where \(X\) is a set and \(P\) is a reflexive, antisymmetric, and transitive binary relation on \(X\). (Refer to for a refresher of what these properties are if you need to.) We call \(X\) the ground set while \(P\) is a partial order on \(X\). Elements of the ground set \(X\) are also called points, and the poset \(\bfP\) is finite if its ground set \(X\) is a finite set.

Example

Let \(X=\{a,b,c,d,e,f\}\). Consider the following binary relations on \(X\). \[\begin{aligned}R_1=\{\amp (a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(a,b),(a,c),(e,f)\} \\ R_2=\{\amp (a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(d,b),(d,e),(b,a),(e,a), \\ \amp(d,a),(c,f)\} \\ R_3=\{\amp(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(a,c),(a,e),(a,f),(b,c), \\ \amp(b,d),(b,e),(b,f),(d,e),(d,f),(e,f)\} \\ R_4=\{\amp(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(d,b),(b,a),(e,a),(c,f)\} \\ R_5=\{\amp(a,a),(c,c),(d,d),(e,e),(a,e),(c,a),(c,e),(d,e)\} \\ R_6=\{\amp(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(d,f),(b,e),(c,a),(e,b)\}\end{aligned}\] Which of the binary relations are partial orders on \(X\)? For those that are not partial orders on \(X\), which property or properties are violated?

Solution

A bit of checking confirms that \(R_1\), \(R_2\) and \(R_3\) are partial orders on \(X\), so \(\bfP_1=(X,R_1)\), \(\bfP_2=(X,R_2)\) and \(\bfP_3=(X,R_3)\) are posets. Several of the other examples we will discuss in this chapter will use the poset \(\bfP_3=(X,R_3)\).

On the other hand, \(R_4\), \(R_5\) and \(R_6\) are not partial orders on \(X\). Note that \(R_4\) is not transitive, as it contains \((d,b)\) and \((b,a)\) but not \((d,a)\). The relation \(R_5\) is not reflexive, since it doesn't contain \((b,b)\). (Also, it also doesn't contain \((f,f)\), but one shortcoming is enough.) Note that \(R_5\) is a partial order on \(\{a,c,d,e\}\). The relation \(R_6\) is not antisymmetric, as it contains both \((b,e)\) and \((e,b)\).

For posets of moderate size, diagrams are frequently used to define a posetrather than the explicit binary relation notation illustrated in . In , we illustrate a poset \(\PXP\) with ground set \(X=[17]=\{1,2,\dots,17\}\). It would take several lines of text to write out the binary relation \(P\), and somehow the diagram serves to give us a more tactile sense of the properties of the poset.

When \(\PXP\) is a poset and \(Y\subseteq X\), the binary relation \(Q=P\cap(Y\times Y)\) is a partial order on \(Y\), and we call the poset \((Y,Q)\) a subposet of \(\bfP\). In , we show a subposet of the poset first presented in .

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.

ປັດຈຸບັນ​ທ່ານ ບໍ່ມີ​ເຄື່ອງ​ຄິດໄລ່​ທີ່​ຈະ​ແກ້ໄຂ​ບັນຫາ​ນີ້​ໄດ້, ແຕ່​ສ່ວນ​ຂອງ​ມັນ​ສາມາດ​ຄິດໄລ່​ໄດ້. ພະຍາຍາມ​ອັນ​ໃດ​ອັນ​ໜຶ່ງ​ຂ້າງ​ລຸ່ມນີ້ ຫຼື ພິມ​ຕົວ​ເອງ​ເອງ.

ທົດລອງ (3)

ທົດລອງ​ທຸກ​ຢ່າງ​ກ່ອນ​ໜ້າ​ນີ້​ໃນ​ເຈ້ຍ. ເປີດ​ເຜີຍ​ຄໍາຕອບ​ເພື່ອ​ກວດ​ສອບ; ຄໍາຕອບ​ທີ່​ໄດ້​ຮັບ​ການ​ກວດ​ສອບ​ສາມາດ​ເປີດ​ໃນ​ຕົວ​ແກ້​ໄຂ​ສຳລັບ​ທຸກ​ບາດກ້າວ.

  1. Consider the poset in . List all of the elements that are comparable to point \(6\).

  2. Consider the middle poset in . Give an example of a chain with three elements that contains the point \(21\).

  3. Consider the rightmost poset in . Give an example of an antichain with three elements that contains the point \((6,4,5)\).

ຮັກສາ​ການ​ເຮັດວຽກ​ຂອງ​ທ່ານ​ໄວ້

ບັນຊີຟຣີ ເພີ່ມ​ຂໍ້​ມູນ​ໃສ່​ບົດຮຽນ​ທຸກ​ບົດ, ບັນທຶກ​ຂອງ​ສິ່ງທີ່​ທ່ານ​ໄດ້​ເຮັດ​ແລ້ວ, ບັນຫາ​ທີ່​ທ່ານ​ໄດ້​ແກ້​ໄຂ​ໄວ້​ໃນ​ບ່ອນ​ດຽວ ແລະ ຄູ​ສອນ​ທີ່​ທ່ານ​ສາມາດ​ຖາມ​ກ່ຽວກັບ​ໜ້າ​ນີ້. ຄະນິດສາດ​ເອງ​ແມ່ນ​ເປີດ​ໃຫ້​ທຸກ​ຄົນ, ບໍ່​ວ່າ​ຈະ​ໄດ້​ເຂົ້າ​ສູ່​ລະບົບ ຫຼື ບໍ່.

ລົງທະບຽນ ចូល

ຕົວ​ສະ​ແດງ​ທີ່​ໃຊ້​ຢູ່​ທີ່​ນີ້

ກົດ​ຕົວ​ອັກສອນ​ໃດ​ໜຶ່ງ​ເພື່ອ​ເບິ່ງ​ຄວາມ​ໝາຍ​ເຕັມ, ຮູບ ແລະ ຕົວອັກສອນ​ແຕ່ລະ​ຕົວ​ໃນ​ມັນ​ໝາຍ​ຄວາມ​ວ່າ​ແນວໃດ.

ຄໍາຖາມທີ່ຄົນຖາມ

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

ບາງສ່ວນຂອງ ໜ້າ ນີ້ ຖືກປັບແຕ່ງຈາກ Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). ຖືກ​ປະສົມ​ປະສານ​ແລະ​ອະທິບາຍ​ຄືນ​ໃໝ່​ທີ່​ນີ້; ຄວາມ​ຜິດ​ພາດ​ແມ່ນ​ຂອງ​ເຮົາ.

ເພີ່ມເຕີມໃນ Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs