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.
Ahora tú Ninguna calculadora resuelve este, pero las piezas son computables. Pruebe uno abajo, o escriba el suyo.
Práctica (3)
Pruebe primero cada uno sobre el papel. Revela la respuesta para comprobar; los verificados se pueden abrir en el solucionador para cada paso.
-
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)\).
Una cuenta gratuita añade notas sobre cada lección, un registro de lo que has terminado, tus problemas resueltos en un lugar, y un tutor que puedes preguntar sobre esta página. Las matemáticas en sí están abiertas a todos, se han registrado o no.
Registrarse Inicio de sesiónSímbolos utilizados aquí
Toque cualquier símbolo para la definición completa, una imagen, y lo que cada letra en ella significa.
Preguntas que la gente hace
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.
Partes de esta página están adaptadas de Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensados y re-explicados aquí; los errores son nuestros.
Más en 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