maths.free › Combinatorics & Graph Theory › 6. Partially Ordered Sets › Additional Concepts for Posets
Additional Concepts for Posets
We say (X,P) and (Y,Q) are isomorphic, and write (X,P) \cong(Y,Q) if there exists a bijection (11 and onto map) f:X\to Y so that x_1\le x_2 in P if and only if f(x_1)\le f(x_2) in Q.
Additional Concepts for Posets
We say \((X,P)\) and \((Y,Q)\) are isomorphic, and write \((X,P) \cong(Y,Q)\) if there exists a bijection (11 and onto map) \(f:X\to Y\) so that \(x_1\le x_2\) in \(P\) if and only if \(f(x_1)\le f(x_2)\) in \(Q\). In this definition, the map \(f\) is called an isomorphism from \(\bfP\) to \(\bfQ\). In , the first two posets are isomorphic.
An isomorphism from \(\bfP\) to \(\bfP\) is called an automorphism of \(\bfP\). An isomorphism from \(\bfP\) to a subposet of \(\bfQ\) is called an embedding of \(\bfP\) in \(\bfQ\). In most settings, we will not distinguish between isomorphic posets, and we will say that a poset \(\PXP\) is contained in \(\QYQ\) (also \(\bfQ\) contains \(\bfP\)) when there is an embedding of \(\bfP\) in \(\bfQ\). Also, we will say that \(\bfP\) excludes \(\bfQ\) when no subposet of \(\bfP\) is isomorphic to \(\bfQ\), and we will frequently say \(\bfP=\bfQ\) when \(\bfP\) and \(\bfQ\) are isomorphic.
With the notion of isomorphism, we are lead naturally to the notion of an unlabeled posets, and in , we show a diagram for such a poset.
Note that the poset shown in has the property that there is only one maximal point. Such a point is sometimes called a one, denoted not surprisingly as\(1\). Also, there is only one minimal point, and it is called a zero, denoted\(0\).
The dual of a partial order \(P\) on a set \(X\) is denoted by \(P^d\) and is defined by \(P^d=\{(y,x):(x,y)\in P\}\). The dual of a poset \(\PXP\) is denoted by \(\bfP^d\) and is defined by \(\bfP^d=(X,P^d)\). A poset \(\bfP\) is self-dual if \(\bfP=\bfP^d\).
Condensed — the full section is in Keller & Trotter, Applied Combinatorics.
Practice (1)
Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.
-
Look at the four claims Bob makes in . For each claim, briefly discuss reasons why you think that Bob is correct or incorrect. Alice is correct that two of Bob's claims are correct, but try to avoid process of elimination as your justification for one of the claims being correct/incorrect!
Symbols used here
Inequalities that allow equality; < and > exclude it.
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
Number of k-element subsets of n things: n!/(k!(n−k)!).
Add a_k for k = 1 up to n.
Multiply a_k for k = 1 up to n.
The set with no elements; the number of elements of A.
Questions people ask
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.
נסה את שלך.
Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.
יותר בפנים. 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