Incidens struktur

Incidensstrukturen er en tredobbelt i matematik

C=(P,L,I).

hvor P er mængden af "punkter", L er mængden af "linjer", og er incidensrelationen . Elementerne kaldes flag . Hvis en

I\subseteq P\ gange L

jeg

(p,l)\i I

, siger vi, at punktet p "ligger på" linjen . Man kan repræsentere L som et sæt af delmængder af P, og forekomsten af I er en inklusion ( hvis og kun hvis ), men man kan tænke mere abstrakt.

l

(p,l)\i I

p\in l

Indfaldsstrukturer generaliserer planer (såsom affine , projektive og Möbius planer ), som det kan ses af de aksiomatiske definitioner af disse planer. Indfaldsstrukturer generaliserer også højere-dimensionelle geometriske strukturer; de endelige strukturer bliver nogle gange omtalt som endelige geometrier .

Sammenligning med andre strukturer

En afbildning af en incidensstruktur kan ligne en graf , men i grafer har en kant kun to endepunkter, mens en linje i en incidensstruktur kan falde sammen med mere end to punkter. Således er incidensstrukturer hypergrafer .

I incidensstrukturen er der intet koncept om et punkt, der ligger mellem to andre punkter. Rækkefølgen af punkterne på linjen er ikke defineret. Sammenlign med ordnet geometri , som har et lie-mellem forhold.

Dobbelt struktur

Hvis vi udveksler rollerne som "punkter" og "linjer" i incidensstrukturen

C = ( P , L , I )

få en dobbelt struktur

C * = ( L , P , I *),

hvor I * er en binær relation, invers til I . Det er klart

C ** = C .

Denne operation er en abstrakt version af projektiv dualitet .

En struktur C , der er isomorf i forhold til sin dobbeltstruktur C *, siges at være selv-dual .

Korrespondance til hypergrafer

Hvert hypergraf eller sæt system kan ses som en incidensstruktur, hvor det universelle sæt spiller rollen som "punkter", det tilsvarende sæt system spiller rollen som "linjer", og incidensrelationen er medlemskabet "∈". Omvendt kan enhver struktur af forekomster ses som en hypergraf.

Eksempel: Fano fly

Især lad

P = {1, 2, 3, 4, 5, 6, 7}, L = { {1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7} , {3,5,6} }.

Den tilsvarende indfaldsstruktur kaldes Fano-planet .

Linjer er nøjagtigt delmængder af punkter, der består af tre punkter, hvis etiketter er polstret til nul med en nim-sum .

Geometrisk repræsentation

Incidensstrukturen kan modelleres med punkter og kurver i euklidisk geometri med standard geometrisk inklusion som incidensrelation. Nogle indfaldsstrukturer kan repræsenteres ved hjælp af punkter og linjer, men for eksempel Fano-overfladen har ikke en sådan repræsentation.

Levi-grafen for incidensstrukturen

Enhver incidensstruktur C svarer til en todelt graf , kaldet Levi-grafen eller strukturincidensgraf. Da enhver todelt graf kan farvelægges med to farver, kan hjørnerne af Levi-grafen farvelægges med hvide og sorte farver, hvor sorte spidser svarer til punkter og hvide spidser svarer til linje C . Kanterne af denne graf svarer til flagene (punkt/linje-hændelsespar) af incidensstrukturen.

Eksempel: Earl of Heawood

Levi-grafen for Fano-flyet er Heawood-grafen . Da Heawood-grafen er forbundet og vertex-transitiv , er der en automorfi (såsom refleksion om den lodrette akse i figuren til højre), der udveksler hvide og sorte hjørner. Dette indebærer, at Fano-flyet er selvdual.