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)
Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.
-
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)\).
A free account adds notes on every lesson, a record of what you have finished, your solved problems in one place, and a tutor you can ask about this page. The maths itself is open to everyone, signed in or not.
ಮೇಲೆ ಗುರುತು ಹಾಕು ಪ್ರವೇಶ (ಲಾಗಿನ್)ಇಲ್ಲಿ ಬಳಸಲಾದ ಸಂಕೇತಗಳು
ಈ ವಚನದಲ್ಲಿ ಬಳಸಲಾಗಿರುವ ಗ್ರೀಕ್‌ ಪದವು, ಚಿತ್ರ ಮತ್ತು ಚಿತ್ರಗಳನ್ನು ನೀವು ಸುಲಭವಾಗಿ ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು ಸಹಾಯ ಮಾಡುತ್ತದೆ.
ಜನರು ಕೇಳುವುದು
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