maths.free › Combinatorics & Graph Theory › 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.
Jetzt du Kein Rechner löst diese Frage, aber ihre Teile sind berechenbar. Probieren Sie unten eine aus oder geben Sie Ihre eigene ein.
Übung (1)
Versuchen Sie zuerst jede auf Papier. Decken Sie die Antwort zur Kontrolle auf; überprüfte Aufgaben lassen sich im Löser Schritt für Schritt öffnen.
-
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!
Ein kostenloses Konto fügt Notizen zu jeder Lektion, eine Aufzeichnung von dem, was Sie beendet haben, Ihre gelösten Probleme an einem Ort, und ein Tutor können Sie über diese Seite fragen. Die Mathematik selbst ist offen für alle, angemeldet oder nicht.
Registrieren AnmeldenHier verwendete Symbole
Tippen Sie auf jedes Symbol für die vollständige Definition, ein Bild und was jeder Buchstabe darin bedeutet.
Fragen, die die Leute stellen
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.
Teile dieser Seite sind adaptiert aus Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Hier gekürzt und neu erklärt; Fehler gehen auf uns.
Mehr in 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