Bestillingsdimensjon - Order dimension

En delvis rekkefølge av dimensjon 4 (vist som et Hasse-diagram ) og fire totalbestillinger som danner en realisator for denne delordren.

I matematikk , den dimensjon av en delvis ordnet sett (poset) er det minste antall av totale ordre til skjæringspunktet som gir opphav til delvis rekkefølgen. Dette konseptet er også noen ganger kalt for dimensjon eller Dushnik-Miller dimensjon av delvis rekkefølgen. Dushnik & Miller (1941) studerte først ordredimensjon ; for en mer detaljert behandling av dette emnet enn gitt her, se Trotter (1992) .

Formell definisjon

Dimensjonen til en poset P er det minste heltallet t som det finnes en familie for

${\ displaystyle {\ mathcal {R}} = (<_ {1}, \ prikker, <_ {t})}$

av lineære utvidelser av P slik at for hver x og y i P , x forut y i P hvis og bare hvis den kommer før y i alle de lineære utvidelser. Det er,

${\ displaystyle P = \ bigcap {\ mathcal {R}} = \ bigcap _ {i = 1} ^ {t} <_ {i}.}$

En alternativ definisjon av ordredimensjon er det minimale antall totale ordrer slik at P legger inn i deres produkt med komponentvis bestilling, dvs. hvis og bare hvis for alle i ( Hiraguti 1955 , Milner & Pouzet 1990 ). ${\ displaystyle x \ leq y}$${\ displaystyle x_ {i} \ leq y_ {i}}$

Realisere

En familie av lineære ordrer på X kalles en realizer av en poset P = ( X , < _P ) if ${\ displaystyle {\ mathcal {R}} = (<_ {1}, \ prikker, <_ {t})}$

${\ displaystyle <_ {P} = \ bigcap {\ mathcal {R}}}$,

det vil si at for alle x og y i X , x < _P y nøyaktig når x < ₁ y , x < ₂ y , ... og x < _t y . Dermed er en ekvivalent definisjon av dimensjonen til en poset P "den minste kardinaliteten til en realisator av P. "

Det kan vises at en hvilken som helst ikke-familie R av lineære utvidelser er en realiserer av et endelig delvis ordnet sett P hvis og bare hvis, for hvert kritisk par ( x , y ) av P , y < _i x for noen rekkefølge < _i i R .

Eksempel

La n er et positivt heltall, og la P være delvis rekkefølgen på elementene en _i og b _i (i 1 ≤ i ≤ n ) i hvilken en _i ≤ b _j når i ≠ j , men ingen andre parene er sammenlignbare. Spesielt er en _i og b _jeg er enestående i P ; P kan sees på som en orientert form av et kronediagram . Illustrasjonen viser en rekkefølge av denne typen for n = 4.

Så, for hver i , må enhver realizer inneholde en lineær rekkefølge som begynner med alle a _j bortsett fra a _i (i en eller annen rekkefølge), deretter inkluderer b _i , deretter a _i og slutter med alle gjenværende b _j . Dette er slik fordi hvis det var en realizer som ikke inkludere en slik rekkefølge, og deretter krysset av det realizer ordre ville ha en _i foregående b _i , noe som ville motsi incomparability av en _i og b _i i P . Og omvendt, noe familie av lineære ordrer som omfatter en rekkefølge av denne type for hver jeg har P som skjæringspunktet. Dermed har P dimensjon nøyaktig n . Faktisk er P kjent som standardeksemplet på en posisjon med dimensjon n , og betegnes vanligvis med S _n .

Bestill dimensjon to

Delordrene med ordredimensjon to kan karakteriseres som delordrene hvis sammenlignbarhetsgraf er komplementet til sammenlignbarhetsgrafen til en annen delordre ( Baker, Fishburn & Roberts 1971 ). Det vil si at P er en delvis rekkefølge med ordredimensjon to hvis og bare hvis det eksisterer en delvis orden Q på det samme settet med elementer, slik at hvert par x , y av forskjellige elementer er sammenlignbare i nøyaktig en av disse to delordrene. Hvis P realiseres av to lineære utvidelser, kan delvis rekkefølge Q komplementær til P realiseres ved å reversere en av de to lineære utvidelsene. Derfor er sammenlignbarhetsgrafene til delordningene til dimensjon to nøyaktig permutasjonsgrafer , grafer som begge er sammenlignbarhetsgrafer og komplementære til sammenlignbarhetsgrafer.

Delordrenes ordre dimensjon to inkluderer serieparallelle delordrer ( Valdes, Tarjan & Lawler 1982 ). De er nøyaktig de delvise ordrene hvis Hasse-diagrammer har dominanstegninger , som kan oppnås ved å bruke posisjonene i de to permutasjonene til en realisator som kartesiske koordinater.

Beregningskompleksitet

Det er mulig å bestemme på polynomtid om et gitt endelig, delvis ordnet sett har bestillingsdimensjon på høyst to, for eksempel ved å teste om sammenlignbarhetsgrafen til den delvise ordenen er en permutasjonsgraf. For alle k  ≥ 3 er det imidlertid NP-komplett å teste om ordredimensjonen maksimalt er k ( Yannakakis 1982 ).

Forekomstposer av grafer

Den Forekomsten poset av en hvilken som helst ikke-rettet graf G har de hjørner og kanter av G som dets elementer; i denne poset, x ≤ y hvis enten x = y eller x er et toppunkt, y er en kant, og x er et endepunkt på y . Visse typer grafer kan kjennetegnes ved ordre dimensjonene av insidensen Posets: en graf er et sti graf hvis og bare hvis den orden dimensjonen av forekomsten poset er høyst to, og i henhold til Schnyder teorem er det en plan graf hvis og bare hvis rekkefølge dimensjonen av dens forekomst poset er på det meste tre ( Schnyder 1989 ).

For en komplett graf på n hjørner er rekkefølge dimensjonen til forekomsten poset ( Hoşten & Morris 1999 ). Det følger at alle enkle n- hvirvelgrafer har innfallsposer med ordredimensjon . ${\ displaystyle \ Theta (\ log \ log n)}$${\ displaystyle O (\ log \ log n)}$

k -dimensjon og 2-dimensjon

En generalisering av dimensjon er begrepet k -dimensjon (skrevet ) som er det minste antall kjeder med lengden på det meste k i hvis produkt den delvise rekkefølgen kan legges inn. Spesielt kan 2-dimensjonen til en ordre sees på som størrelsen på det minste settet slik at ordren innebærer i inkluderingsrekkefølgen på dette settet. ${\ displaystyle {\ textrm {dim}} _ {k}}$

Se også

• Intervalldimensjon

Referanser

• Baker, KA; Fishburn, P .; Roberts, FS (1971), "Partial orders of dimension 2", Networks , 2 (1): 11–28, doi : 10.1002 / net.3230020103.
• Dushnik, Ben; Miller, EW (1941), "Delvis ordnede sett", American Journal of Mathematics , 63 (3): 600–610, doi : 10.2307 / 2371374 , hdl : 10338.dmlcz / 100377 , JSTOR  2371374.
• Hiraguti, Tosio (1955), "On the dimension of orders" (PDF) , The Science Reports of the Kanazawa University , 4 (1): 1–20, MR  0077500.
• Hoşten, Serkan; Morris, Walter D., Jr. (1999), "The order dimension of the complete graph", Discrete Mathematics , 201 (1–3): 133–139, doi : 10.1016 / S0012-365X (98) 00315-X , MR  1687882.
• Milner, EC; Pouzet, M. (1990), "A note on the dimension of a poset", Order , 7 (1): 101–102, doi : 10.1007 / BF00383178 , MR  1086132 , S2CID  123485792.
• Schnyder, W. (1989), "Planar charts and poset dimension", Order , 5 (4): 323–343, doi : 10.1007 / BF00353652 , S2CID  122785359.
• Trotter, William T. (1992), Combinatorics og delvis bestilte sett: Dimensjonsteori , Johns Hopkins Series in the Mathematical Sciences, The Johns Hopkins University Press, ISBN 978-0-8018-4425-6.
• Valdes, Jacobo; Tarjan, Robert E .; Lawler, Eugene L. (1982), "The recognition of series parallel digraphs", SIAM Journal on Computing , 11 (2): 298–313, doi : 10.1137 / 0211023.
• Yannakakis, Mihalis (1982), "The complex order of the partial order dimension problem", SIAM Journal on Algebraic and Discrete Methods , 3 (3): 351–358, doi : 10.1137 / 0603036.