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.
Now you Nijedan kalkulator ne slaže ovaj, ali komadiće su komputentni. Pokušajte jedan ispod, ili upišite vlastiti.
Vježba (3)
Pokušajte svaki na papiru prvo. Otkrijte odgovor provjeriti; provjereni mogu biti otvoreni u rješavač za svaki korak.
-
Consider the poset in . List all of the elements that are comparable to point \(6\).
-
Consider the middle poset in . Give an example of a chain with three elements that contains the point \(21\).
-
Consider the rightmost poset in . Give an example of an antichain with three elements that contains the point \((6,4,5)\).
Besplatan račun dodaje bilješke na svakoj lekciji, zapis onoga što ste završili, rješeni problemi na jednom mjestu, i tutor možete pitati o ovoj stranici. Sama matematika je otvorena za sve, potpisani ili ne.
Prijavi se PrijavaSimboli koji se koriste ovdje
Dodirnite bilo koji simbol za punu definiciju, sliku, i što znači svako slovo u njoj.
Pitanja koja ljudi postavljaju
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.
Dijelovi ove stranice prilagođeni su od Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Ovdje su kondenzirane i objašnjene; greške su naše.
Više u 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