Trunkerat projektivt plan

Inom geometri är ett trunkerat projektivt plan (TPP) , även känt som ett dubbelt affint plan , en speciell typ av hypergraf eller geometrisk konfiguration som är konstruerad på följande sätt.

Ta ett ändligt projektivt plan .
Ta bort en av punkterna (topparna) i planet.
Ta bort alla linjer (kanter) som innehåller den punkten.

Dessa objekt har studerats i många olika miljöer, ofta oberoende av varandra, och därför har många terminologier utvecklats. Olika områden tenderar också att ställa olika typer av frågor om dessa föremål och är intresserade av olika aspekter av samma föremål.

Exempel: Pasch-hypergrafen

Tänk på Fano-planet , som är det projektiva planet av ordning 2. Det har 7 hörn {1,2,3,4,5,6,7} och 7 kanter {123, 145, 167, 246, 257, 347, 356 }.

Den kan trunkeras t.ex. genom att ta bort vertexen 7 och kanterna som innehåller den. Den återstående hypergrafen är TPP av ordning 2. Den har 6 hörn {1,2,3,4,5,6} och 4 kanter {123, 154, 624, 653}. Det är en tredelad hypergraf med sidorna {1,6},{2,5},{3,4} (som är exakt grannarna till det borttagna hörnet 7). Det kallas också Pasch-hypergrafen , på grund av dess koppling till Paschs axiom .

Det är en 2- regelbunden hypergraf (varje hörn är i exakt två kanter), och dess maximala matchning är av storlek 1 (varannan av dess kanter skär varandra).

Kombinatorik av dubbla affina plan

Ett ändligt projektivt plan av ordningen $n$ har $n$ + 1 punkter på varje linje ( $n + 1 = r$ i hypergrafbeskrivningen). Det finns $n 2 + n + 1$ totala poäng och lika många linjer. Varje punkt är på $n$ + 1 linjer. Varje två distinkta punkter ligger på en unik linje och varannan distinkta linjer möts vid en unik punkt.

Genom att ta bort en punkt och alla linjer som passerar genom den punkten har konfigurationen som är kvar $n 2 + n$ punkter, $n$ ² linjer, varje punkt är på $n$ linjer och varje linje innehåller $n$ + 1 punkter. Varje par av distinkta linjer möts fortfarande vid en unik punkt, men två distinkta punkter finns på högst en linje. $(n2 + n) n (n2) n +1) är$ således en konfiguration av typen ( .

Punkterna kan delas upp i $n$ + 1 uppsättningar av $n$ punkter vardera, där inga två punkter i samma partitionsuppsättning är sammanfogade av en linje. Dessa uppsättningar är analoger av klasser av parallella linjer i ett affint plan, och vissa författare hänvisar till punkterna i en partitionsdel som parallella punkter i enlighet med strukturens dubbla natur.

Projektiva plan konstruerade från finita fält ( Desarguesian planes ) har automorfismgrupper som verkar transitivt på planets punkter, så för dessa plan är den punkt som avlägsnas för att bilda det dubbla affina planet oväsentlig, resultaten av att välja olika punkter är isomorfa . Det finns emellertid icke-desarguesiska plan och valet av punkt att ta bort i dem kan resultera i icke-isomorfa dubbla affina plan med samma parametrar.

Ett affint plan erhålls genom att ta bort en linje och alla punkter på den linjen från ett projektivt plan. Eftersom ett projektivt plan är en självdubbel konfiguration, erhålls den dubbla konfigurationen av ett affint plan från ett projektivt plan genom att ta bort en punkt och alla linjer genom den punkten. Därav namnet på denna konfiguration.

Hypergrafegenskaper

Det är känt att det projektiva planet av ordningen r -1 existerar närhelst r -1 är en primpotens; därför gäller samma sak för TPP.

Det ändliga projektiva planet av ordningen r -1 innehåller r ² - r +1 hörn och r ² - r +1 kanter; därför innehåller TPP av ordningen r -1 r ² - r hörn och r ² - 2r +1 kanter.

TPP av ordningen r -1 är en r -partit hypergraf : dess hörn kan delas upp i r delar så att varje hyperedge innehåller exakt en vertex av varje del. Till exempel, i TPP för ordning 2 är de 3 delarna {1,6}, {2,5} och {3,4}. I allmänhet innehåller var och en av de r delarna r -1 hörn.

Varje kant i en TPP skär varannan kant. Därför är dess maximala matchande storlek 1:

$\nu (H)=1$ .

Å andra sidan kräver täckning av alla kanter av TPP alla r -1 hörn på en av delarna. Därför är dess minsta vertex-täckstorlek r -1:

$\tau (H)=r-1$ .

Därför är TPP en extrem hypergraf för Rysers gissningar .

Den minsta fraktionella vertex-täckningsstorleken för TPP är också r -1: att tilldela en vikt på 1/ r till varje vertex (vilket är en vertex-cover eftersom varje hyperedge innehåller r vertex) ger en bråkdel av storleken ( r ² - r )/ r = r -1.

Dess maximala bråkmatchningsstorlek är också r -1: att tilldela en vikt på 1/( r-1 ) till varje hyperedge (vilket är en matchning eftersom varje vertex finns i r -1 kanter) ger en bråkdelsmatchning av storlek ( r2-2r + 1)/( r -1)= r - 1 ^. Därför:

$\tau ^{*}(H)=\nu ^{*}(H)=r-1$ .

Observera att ovanstående bråkmatchning är perfekt, eftersom dess storlek är lika med antalet hörn i varje del av r -partite-hypergrafen. Det finns dock ingen perfekt matchning, och dessutom är den maximala matchningsstorleken bara 1. Detta är i motsats till situationen i tvådelade grafer, där en perfekt bråkmatchning innebär att det finns en perfekt matchning.

Designteoretiska aspekter

Dubbla affina plan kan ses som en punktrester av ett projektivt plan, en 1-design och, mer klassiskt, som en taktisk konfiguration .

Eftersom de inte är parvis balanserade konstruktioner (PBD), har de inte studerats i stor utsträckning ur designteoretisk synvinkel. Men taktiska konfigurationer är centrala ämnen inom geometri, särskilt finit geometri .

Historia

Enligt Dembowski (1968 , s. 5) verkar termen "taktisk konfiguration" bero på EH Moore 1896. För historien om dubbla konfigurationer, se Dualitet (projektiv geometri)#History .

Anteckningar

Beth, Thomas; Jungnickel, Dieter ; Lenz, Hanfried (1986), Design Theory , Cambridge: Cambridge University Press , ISBN 3-411-01675-2
Dembowski, Peter (1968), Finite geometries , Ergebnisse der Mathematik und ihrer Grenzgebiete , Band 44, Berlin, New York: Springer-Verlag , ISBN 3-540-61786-8 , MR 0233275