Antikette - Antichain

In der Mathematik , im Bereich der Ordnungstheorie , ein Antikette ist eine Teilmenge von einem teilweise geordneten Satz , so daß je zwei verschiedene Elemente in der Untergruppe sind unvergleichbar .

Die Größe der größten Antikette in einer teilweise geordneten Menge wird als Breite bezeichnet . Nach dem Satz von Dilworth entspricht dies auch der minimalen Anzahl von Ketten (vollständig geordneten Teilmengen), in die die Menge unterteilt werden kann. Die Höhe der teilweise geordneten Menge (die Länge ihrer längsten Kette) entspricht nach dem Satz von Mirsky der minimalen Anzahl von Antiketten, in die die Menge unterteilt werden kann.

Der Familie aller Antiketten in einer endlichen, teilweise geordneten Menge können Join- und Meet- Operationen gegeben werden, wodurch sie zu einem Verteilungsgitter werden . Für das teilgeordnete System aller Teilmengen einer endlichen Menge, geordnet nach Mengeneinschluss, heißen die Antiketten Sperner-Familien und ihr Gitter ist ein freies Verteilungsgitter mit einer Dedekind- Elementzahl. Allgemeiner ausgedrückt ist das Zählen der Anzahl von Antiketten einer endlichen teilweise geordneten Menge #P-vollständig .

Definitionen

Sei eine teilweise geordnete Menge. Zwei Elemente und einer teilweise geordneten Menge heißen vergleichbar, wenn Wenn zwei Elemente nicht vergleichbar sind, heißen sie unvergleichbar; das heißt, und sind unvergleichbar, wenn keines von beiden${\displaystyle S}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a\leq b{\text{ oder }}b\leq a.}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x\leq y{\text{nor}}y\leq x.}$

Eine Kette in ist eine Teilmenge, in der jedes Paar von Elementen vergleichbar ist; das heißt, ist total bestellt . Eine Antikette in eine Teilmenge der in dem jedes Paar von unterschiedlichen Elementen ist unvergleichlich; das heißt, es gibt keine Ordnungsbeziehung zwischen zwei verschiedenen Elementen in (Einige Autoren verwenden jedoch den Begriff "Antikette", um eine starke Antikette zu bedeuten , eine Untermenge, bei der es kein Element des Poset gibt, das kleiner als zwei verschiedene Elemente der Antikette ist. ) ${\displaystyle S}$ ${\displaystyle C\subseteq S}$${\displaystyle C}$${\displaystyle S}$ ${\displaystyle A}$${\displaystyle S}$${\displaystyle A.}$

Höhe und Breite

Eine maximale Antikette ist eine Antikette, die keine richtige Untermenge einer anderen Antikette ist. Eine maximale Antikette ist eine Antikette, deren Kardinalität mindestens so groß ist wie jede andere Antikette. Die Breite einer teilweise geordneten Menge ist die Kardinalität einer maximalen Antikette. Jede Antikette kann schneiden jede Kette in höchstens einem Element, so, wenn wir die Elemente eines Auftrags in partitionieren können Ketten dann die Breite in der Größenordnung höchstens sein muss (wenn die Antikette hat mehr als Elemente, die von dem Schubfachprinzip gibt wären 2 seiner Elemente, die zu derselben Kette gehören, Widerspruch). Der Satz von Dilworth besagt, dass diese Schranke immer erreicht werden kann: Es gibt immer eine Antikette und eine Aufteilung der Elemente in Ketten, so dass die Anzahl der Ketten gleich der Anzahl der Elemente in der Antikette ist, die also auch gleich der Breite sein muss. Ebenso kann man die Höhe einer Teilordnung als maximale Kardinalität einer Kette definieren. Der Satz von Mirsky besagt, dass in jeder partiellen Ordnung endlicher Höhe die Höhe der kleinsten Anzahl von Antiketten entspricht, in die die Ordnung unterteilt werden kann. ${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

Sperner Familien

Eine Antikette in der Inklusionsordnung von Teilmengen einer -elementigen Menge ist als Sperner-Familie bekannt . Die Anzahl der verschiedenen Sperner-Familien wird durch die Dedekind-Zahlen gezählt , von denen die ersten Zahlen sind ${\displaystyle n}$

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (Sequenz A000372 im OEIS ).

Sogar die leere Menge hat zwei Antiketten in ihrer Potenzmenge: eine enthält eine einzelne Menge (die leere Menge selbst) und eine enthält keine Mengen.

Schließen Sie sich den Betrieben an und treffen Sie sie

Jede Antikette entspricht einer niedrigeren Menge${\displaystyle A}$

In einer endlichen Teilordnung (oder allgemeiner einer Teilordnung, die die aufsteigende Kettenbedingung erfüllt ) haben alle unteren Mengen diese Form. Die Vereinigung zweier niedrigerer Mengen ist eine weitere untere Menge, und die Vereinigungsoperation entspricht auf diese Weise einer Join- Operation auf Antiketten: In ähnlicher Weise können wir eine Meet- Operation auf Antiketten definieren, die der Schnittmenge der unteren Mengen entspricht: Die Join-and-meet-Operationen auf allen endlichen Antiketten endlicher Teilmengen einer Menge definieren ein Verteilungsgitter , das durch Birkhoffs Darstellungssatz für Verteilungsgitter erzeugte freie Verteilungsgitter besagt, dass jedes endliche Verteilungsgitter durch Join- und Meet-Operationen auf Antiketten von a represented dargestellt werden kann endlicher Teilordnung oder äquivalent als Vereinigungs- und Schnittoperationen auf den unteren Mengen der Teilordnung. ${\displaystyle X}$${\displaystyle X.}$

Rechenkomplexität

Eine maximale Antikette (und ihre Größe, die Breite einer gegebenen teilweise geordneten Menge) kann in polynomieller Zeit gefunden werden . Das Zählen der Anzahl von Antiketten in einem gegebenen teilweise geordneten Satz ist #P-vollständig .

Verweise

Externe Links

• Weisstein, Eric W. "Antichain" . MathWorld .
• "Antikette" . PlanetMath .