Kulingdiagram

I den matematiska disciplinen polyedrisk kombinatorik , förvandlar Gale -transformen hörnpunkten på vilken konvex polytop som helst till en uppsättning vektorer eller punkter i ett utrymme med en annan dimension, Gale-diagrammet för polytopen. Det kan användas för att beskriva högdimensionella polytoper med få hörn, genom att omvandla dem till uppsättningar av punkter i ett utrymme med en mycket lägre dimension. Processen kan också vändas, för att konstruera polytoper med önskade egenskaper från deras Gale diagram. Gale-transformen och Gale-diagrammet är uppkallade efter David Gale , som introducerade dessa metoder i ett papper från 1956 om grannpolytoper .

Definitioner

Omvandla

Givet en $d$ -dimensionell polytop, med $n$$) {\displaystyle (d+1)}$ , gränsar 1 till de kartesiska koordinaterna för varje vertex, för att erhålla en -dimensionell kolumnvektor . Matrisen $A$ av dessa $n$ kolumnvektorer har dimensioner $(d+1)\ gånger n$ och rang $\displaystyle d+1 }$ { . Gale-transformen ersätter denna matris med en matris $B$ med dimensionen ${\displaystyle n\times (nd-1)} ,$ vars kolumnvektorer är en bas för kärnan i $A$ . Då har $B$$n$ radvektorer med dimensionen $nd-1$ . Dessa radvektorer bildar galediagrammet för polytopen. Det finns ett val av vilken grund kärnan ska använda, men den ändrar resultatet endast genom en linjär transformation.

En riktig delmängd av hörn av en polytop bildar vertexuppsättningen av en yta av polytopen, om och endast om den komplementära uppsättningen vektorer av Gale-transformen har ett konvext skrov som innehåller ursprunget i dess relativa inre . På motsvarande sätt bildar delmängden av hörn ett ansikte om och endast om det inte finns någon linjär funktion som tilldelar icke-negativa värden till de komplementära vektorerna.

Linjärt diagram

Eftersom Gale-transformen endast definieras upp till en linjär transformation, kan dess icke-nollvektorer normaliseras till att alla är ( $\displaystyle (nd-1)}$ -dimensionella enhetsvektorer . Det linjära Gale-diagrammet är en normaliserad version av Gale-transformen, där alla vektorer är noll- eller enhetsvektorer.

Affint diagram

Givet ett galediagram av en polytop, det vill säga en uppsättning av $n$ enhetsvektorer i ett $(nd-1)$ -dimensionellt utrymme, kan man välja ett $(nd-2)$ -dimensionellt delrum $S$ genom origo som undviker alla vektorer, och ett parallellt delrum $S'$ som inte passerar igenom ursprunget. Sedan kommer en central projektion från origo till $S'$ att producera en uppsättning $(nd-2)$ -dimensionella punkter. Denna projektion förlorar informationen om vilka vektorer som ligger ovanför $S$ och vilka som ligger under den, men denna information kan representeras genom att tilldela ett tecken (positivt, negativt eller noll) eller motsvarande en färg (svart, vit eller grå) till varje punkt. Den resulterande uppsättningen av signerade eller färgade punkter är det affina Gale-diagrammet för den givna polytopen. Denna konstruktion har fördelen, jämfört med Gale-transformen, att använda en dimension mindre för att representera strukturen för den givna polytopen.

Gale transformer och linjära och affina Gale diagram kan också beskrivas genom dualiteten av orienterade matroider . Som med det linjära diagrammet bildar en delmängd av hörn ett ansikte om och endast om det inte finns någon affin funktion (en linjär funktion med en konstant term som eventuellt inte är noll) som tilldelar ett icke-negativt värde till varje positiv vektor i den komplementära mängden och en icke-positivt värde för varje negativ vektor i den komplementära uppsättningen.

Exempel

Gale-diagrammet är särskilt effektivt för att beskriva polyedrar vars antal hörn bara är något större än deras dimensioner.

Simplices

En $d$ -dimensionell polytop med $n=d+1$ hörn, minsta möjliga, är en simplex . I det här fallet är det linjära Gale-diagrammet 0-dimensionellt och består endast av nollvektorer. Det affina diagrammet har $n$ gråpunkter.

Ytterligare en vertex

I en $d$ -dimensionell polytop med $n=d+2$ hörn, är det linjära Gale-diagrammet endimensionellt, där vektorn som representerar varje punkt är ett av de tre talen $-1$ , $0$ eller $+1$ . I det affina diagrammet är punkterna nolldimensionella, så de kan endast representeras av sina tecken eller färger utan något lägesvärde. För att representera en polytop måste diagrammet ha minst två punkter med varje tecken som inte är noll. Två diagram representerar samma kombinatoriska ekvivalensklass av polytoper när de har samma antal punkter av varje tecken, eller när de kan erhållas från varandra genom att negera alla tecken.

För $d=2$ är den enda möjligheten två punkter av varje tecken som inte är noll, vilket representerar en konvex fyrhörning . För $d=3$ finns det två möjliga Gale-diagram: diagrammet med två punkter av varje tecken som inte är noll och en nollpunkt representerar en fyrkantig pyramid , medan diagrammet med två punkter med ett tecken som inte är noll och tre punkter med det andra tecknet representerar den triangulära bipyramiden .

I allmänhet är antalet distinkta Gale-diagram med $n=d+2$ och antalet kombinatoriska ekvivalensklasser för $d$ -dimensionella polytoper med $n$ hörn $\displaystyle \lfloor d^{2}/4\rfloor }$ är .

Ytterligare två hörn

I en $d$ -dimensionell polytop med $n=d+3$ hörn, består det linjära Gale-diagrammet av punkter på enhetscirkeln ( enhetsvektorer) och i dess centrum. Det affina Gale-diagrammet består av märkta punkter eller kluster av punkter på en linje. Till skillnad från fallet med $n=d+2$ hörn, är det inte helt trivialt att avgöra när två Gale-diagram representerar samma polytop.

Tredimensionella polyedrar med sex hörn ger naturliga exempel där den ursprungliga polyedern har en tillräckligt låg dimension för att visualisera, men där Gale-diagrammet fortfarande ger en dimensionsreducerande effekt. Dessa inkluderar både den vanliga oktaedern och det triangulära prismat . Det linjära Gale-diagrammet för en vanlig oktaeder består av tre par lika punkter på enhetscirkeln (som representerar par av motsatta hörn av oktaedern), som delar upp cirkeln i vinkelbågar mindre än π {\displaystyle \ $}$ . Dess affina Gale-diagram består av tre par punkter med lika tecken på linjen, där mittparet har motsatt tecken till de två yttre paren. Det linjära Gale-diagrammet för ett triangulärt prisma består av sex punkter på cirkeln, i tre diametralt motsatta par, där varje par representerar prismats hörn som ligger intill på två kvadratiska ytor av prismat. Motsvarande affina Gale-diagram har tre par punkter på en linje, som den vanliga oktaedern, men med en punkt av varje tecken i varje par.

Ansökningar

Galediagram har använts för att tillhandahålla en komplett kombinatorisk uppräkning av den $d$ -dimensionella polytopen med $n=d+3$ hörn, och för att konstruera polytoper som har ovanliga egenskaper.

Polytoper konstruerade på detta sätt inkluderar:

• Perles-polytopen, en 8-dimensionell polytop med 12 hörn som inte kan realiseras med rationella kartesiska koordinater . Denna polytop konstruerades av Micha Perles från Perles-konfigurationen (nio punkter och nio linjer i planet som inte kan realiseras med rationella koordinater) genom att dubbla tre av punkterna i Perles-konfigurationen, tilldela tecken till de resulterande 12 punkterna, och behandla resulterande signerad konfiguration som Gale diagram av en polytop. Även om irrationella polytoper är kända med dimension så låg som fyra, är ingen känd med färre hörn.
• Kleinschmidt-polytopen, en 4-dimensionell polytop med 8 hörn, 10 tetraedriska fasetter och en oktaedrisk facett, konstruerad av Peter Kleinschmidt. Även om den oktaedriska fasetten har samma kombinatoriska struktur som en vanlig oktaeder, är det inte möjligt att den är regelbunden. Två kopior av denna polytop kan limmas ihop på sina oktaedriska fasetter för att producera en 10-vertex polytop där vissa par av realiseringar inte kan deformeras kontinuerligt till varandra.
• Bipyramiden över en fyrkantig pyramid är en 4-dimensionell polytop med 7 hörn som har den dubbla egenskapen att formen på en av dess vertexfigurer (spetsen på dess centrala pyramid) inte kan föreskrivas. Ursprungligen hittades av David W. Barnette, detta exempel återupptäcktes av Bernd Sturmfels med hjälp av Gale diagram.
• Konstruktionen av små "uneighborly polytopes", det vill säga polytoper utan en universell vertex , och "illuminated polytopes", där varje vertex är infallande till en diagonal som passerar genom det inre av polytopen. Korspolytoperna har dessa egenskaper, men i 16 eller fler dimensioner finns det upplysta polytoper med färre spetsar, och i 6 eller fler dimensioner behöver de upplysta polytoperna med minst spetsar inte vara enkla . Konstruktionen involverar Gale diagram.

Anteckningar

•   Gale, David (1956), "Neighboring vertices on a convex polyhedron", Linear inequalities and related system , Annals of Mathematics Studies, nr. 38, Princeton University Press, Princeton, NJ, s. 255–263, MR 0085552
•   Sturmfels, Bernd (1988), "Some applications of affine Gale diagrams to polytopes with few vertices", SIAM Journal on Discrete Mathematics , 1 (1): 121–133, doi : 10.1137/0401014 , MR 0936614
•    Thomas, Rekha R. (2006), "Kapitel 5: Gale Diagrams", Lectures in Geometric Combinatorics , Student Mathematical Library, vol. 33, Institute for Advanced Study (IAS), Princeton, NJ, s. 37–45, doi : 10.1090/stml/033 , ISBN 0-8218-4140-8 , MR 2237292
•    Wotzlaw, Ronald F.; Ziegler, Günter M. (2011), "A lost counterexample and a problem on illuminated polytopes", American Mathematical Monthly , 118 (6): 534–543, doi : 10.4169/amer.math.monthly.118.06.534 , 284814 , 28481 , S2CID 15007113
•    Ziegler, Günter M. (1995), "Kapitel 6: Duality, Gale Diagrams, and Applications", Lectures on Polytopes , Graduate Texts in Mathematics, vol. 152, New York: Springer-Verlag, s. 149–190, doi : 10.1007/978-1-4613-8431-1_6 , ISBN 0-387-94365-X , MR 1311028