Antikedja - Antichain

I matematik , inom ordningsteorin , är en antikedja en delmängd av en delvis ordnad uppsättning så att två olika element i delmängden är ojämförliga .

Storleken på den största antikedjan i en delvis ordnad uppsättning är känd som dess bredd . Enligt Dilworths sats motsvarar detta också det minsta antalet kedjor (totalt beställda delmängder) som uppsättningen kan delas in i. Dublerat är höjden på den delvis ordnade uppsättningen (längden på dess längsta kedja) lika med Mirskys sats det minsta antalet antikedjor som uppsättningen kan delas in i.

Familjen till alla antikedjor i en begränsad, delvis ordnad uppsättning kan få gå med och möta operationer, vilket gör dem till ett distributivt gitter . För det delvis ordnade systemet för alla delmängder av en ändlig uppsättning, ordnade efter uppsättning inkludering, kallas antikedjorna Sperner -familjer och deras gitter är ett gratis distributivt gitter , med ett Dedekind -antal element. Mer allmänt räknas antalet antikedjor i en begränsad delvis ordnad uppsättning #P-komplett .

Definitioner

Låt vara en delvis beställd uppsättning. Två element och en delvis ordnad uppsättning kallas jämförbara om Om två element inte är jämförbara kallas de ojämförliga; det vill säga och är ojämförliga om inte heller ${\ displaystyle S}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a \ leq b {\ text {eller}} b \ leq a.}$ ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle x \ leq y {\ text {nor}} y \ leq x.}$

En kedja in är en delmängd där varje par av element är jämförbara; det vill säga är helt beställd . En antichain i är en delmängd av i vilken varje par av olika element är ojämförlig; det vill säga, det finns inget ordningsförhållande mellan två olika element i (Dock använder vissa författare termen "antikedja" för att betyda stark antikedja , en delmängd så att det inte finns något element i poset som är mindre än två distinkta element i antikedjan. ) ${\ displaystyle S}$ ${\ displaystyle C \ subseteq S}$ ${\ displaystyle C}$ ${\ displaystyle S}$ ${\ displaystyle A}$ ${\ displaystyle S}$ ${\ displaystyle A.}$

Höjd och bredd

En maximal antikedja är en antikedja som inte är en korrekt delmängd av någon annan antikedja. En maximal antikedja är en antikedja som har kardinalitet minst lika stor som alla andra antikedjor. Den bredd av en partiellt ordnad uppsättning är kardinaliteten av högst antichain. Varje antikedja kan skär en kedja i högst ett element, så om vi kan dela upp beställningens element i kedjor måste ordningens bredd vara högst (om antikedjan har mer än element, enligt duvhålsprincipen , finns det skulle vara 2 av dess element som tillhör samma kedja, motsägelse). Dilworths sats säger att denna gräns alltid kan nås: det finns alltid en antikedja och en uppdelning av elementen i kedjor, så att antalet kedjor är lika med antalet element i antikedjan, som därför också måste vara lika bred. På samma sätt kan man definiera höjden på en partiell ordning som den maximala kardinaliteten hos en kedja. Mirskys sats säger att höjden i alla partiella ordningar med begränsad höjd motsvarar det minsta antalet antikedjor som ordningen kan delas in i. ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle k}$

Sperner -familjer

En antikedja i inkluderingsbeställningen av delmängder av en -elementuppsättning är känd som en Sperner -familj . Antalet olika Sperner -familjer räknas med Dedekind -siffrorna , varav de första siffrorna är ${\ displaystyle n}$

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sekvens A000372 i OEIS ).

Till och med den tomma uppsättningen har två antikedjor i sin kraftuppsättning: en som innehåller en enda uppsättning (den tomma uppsättningen själv) och en som inte innehåller några uppsättningar.

Gå med och träffa verksamheten

Varje antikedja motsvarar en lägre uppsättning ${\ displaystyle A}$

{\ displaystyle L_ {A} = \ {x: \ existerar y \ i A {\ mbox {så att}} x \ leq y \}.}

I en begränsad delordning (eller mer allmänt en delordning som uppfyller det stigande kedjebetingelsen ) har alla lägre uppsättningar denna form. Föreningen av två lägre uppsättningar är en annan lägre uppsättning, och fackföreningsoperationen motsvarar på detta sätt en sammanfogning på antikedjor:

{\ displaystyle A \ vee B = \ {x \ i A \ cup B: \ nexists y \ in A \ cup B {\ mbox {such that}} x <y \}.}

På samma sätt kan vi definiera en meet -operation på antikedjor, motsvarande skärningspunkten mellan lägre uppsättningar:

{\ displaystyle A \ wedge B = \ {x \ i L_ {A} \ cap L_ {B}: \ nexisterar y \ i L_ {A} \ cap L_ {B} {\ mbox {så att}} x <y \}.}

Kopplings- och mötesoperationerna på alla ändliga antikedjor av ändliga delmängder av en uppsättning definierar ett distributivt gitter , det fria distributiva gitteret som genereras av Birkhoffs representationssats för distributiva gitter säger att varje ändligt distributivt gitter kan representeras via sammanfoga och möta operationer på antikedjor av en ändlig delordning, eller likvärdigt som förenings- och korsningsoperationer på delordens lägre uppsättningar .

{\ displaystyle X}

{\ displaystyle X.}

Beräkningskomplexitet

En maximal antikedja (och dess storlek, bredden på en given delvis ordnad uppsättning) kan hittas i polynomtid . Att räkna antalet antikedjor i en viss delvis ordnad uppsättning är #P-komplett .

Referenser

externa länkar

Weisstein, Eric W. "Antichain" . MathWorld .
"Antikedja" . PlanetMath .

Languages

In other projects