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)
প্রথমে প্রতিটি প্রশ্ন কাগজে লিখে পরীক্ষা করুন । পরীক্ষা করার জন্য উত্তর প্রকাশ করুন; প্রত্যেক ধাপেই পরীক্ষা করা উত্তর সমাধানকারীতে খুলতে পারবেন ।
-
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)\).
একটি বিনামূল্যে অ্যাকাউন্ট প্রতিটি পাঠের নোট যোগ করে, আপনি কি শেষ করেছেন তার একটি রেকর্ড, আপনার সমাধান করা সমস্যা এক জায়গায়, এবং আপনি এই পাতা সম্পর্কে একজন টিউটরকে জিজ্ঞাসা করতে পারেন। গণিত নিজেই সবার জন্য উন্মুক্ত, লগইন করা হোক বা না হোক।
নিবন্ধন করুন লগ- ইনএখানে ব্যবহৃত প্রতীক
যে কোন প্রতীক চাপুন সম্পূর্ণ সংজ্ঞা, একটি ছবি এবং এর প্রতিটি অক্ষরের অর্থের জন্য।
মানুষ জিজ্ঞাসা করে
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