Greve Levy

Levy-grafen (även incidensgrafen ) är en tvådelad graf som motsvarar incidensstrukturen [1] [2] . Från en uppsättning punkter och linjer i en infallsgeometri eller projektiv konfiguration bildas en graf med en vertex för varje punkt, en vertex för varje linje och en kant för varje punkt och linjeinfall (d.v.s. "punkten ligger på linje" förhållande). Dessa grevar fick sitt namn efter Friedrich Levi, som beskrev dem 1942 [1] [3] .

Levi-grafen för ett system av punkter och linjer har vanligtvis en omkrets på minst sex: varje cykel med längd 4 måste motsvara två linjer som går genom samma två punkter. Därför kan vilken tvådelad graf som helst med minst sex omkrets betraktas som en Levi-graf av den abstrakta incidensstrukturen [1] . Levi-grafer över konfigurationer är tvåregelbundnaoch varje biregelbunden graf med omkrets minst sex kan betraktas som en Levi-graf med abstrakt konfiguration [4] .

Avgiftsgrafer kan också definieras för andra typer av infallsstrukturer, såsom incidenser mellan punkter och plan i det euklidiska rummet . För alla Levi-grafer finns det en motsvarande hypergraf och vice versa.

Exempel

• Desargues-grafen är Levi -grafen för Desargues-konfigurationen , bestående av 10 punkter och 10 linjer. Det finns 3 punkter på varje linje och 3 linjer passerar genom varje punkt. Desargues-grafen kan också ses som en generaliserad Petersen-graf G (10,3) eller som en tvådelad Kneser-graf med parametrarna 5,2. Det är en 3-regelbunden graf med 20 hörn.

• Heawood-grafen är Levi-grafen för Fano-planet . Även känd som (3,6) -cellen , det är en 3-regelbunden graf med 14 hörn.

• Möbius-Cantor-grafen är Lévy-grafen för Möbius-Cantor-konfigurationen , ett system med 8 punkter och 8 linjer som inte kan realiseras med raka linjer på det euklidiska planet. Det är en 3-regelbunden graf och har 16 hörn.

• Pappus- grafen är Levi-grafen för Pappus-konfigurationen , som består av 9 punkter och 9 linjer. Som i Desargues-konfigurationen finns det 3 punkter på varje linje och 3 linjer passerar genom varje punkt. Grafen är 3-regelbunden och har 18 hörn.

• Den grå grafen är en Levi-graf av en konfiguration som kan erhållas i R 3 som ett 3×3×3 gitter med 27 punkter och 27 ortogonala linjer genom dessa punkter.

• Thatta med 8 celler är Levi-grafen för Cremona-Richmond-konfigurationen . Grafen, även känd som en (3,8)-cell, är 3-regelbunden och har 30 hörn.

• Grafen för den fyrdimensionella hyperkuben Q 4 är Levi-grafen för Möbius-konfigurationen som bildas av punkterna och planen av två inbördes inskrivna tetraedrar. Här anses en tetraeder vara inskriven i en annan om alla dess hörn ligger på plan som passerar genom ytorna på en annan tetraeder (inte nödvändigtvis på själva ytorna).

• Ljubljana -grafen med 112 vertex är Lévy-grafen för Ljubljana-konfigurationen [5] .

Anteckningar

1. ↑ 1 2 3 Branko Grünbaum. Arvet från Coxeter. - Providence, RI: American Mathematical Society, 2006. - P. 179-225. Se särskilt s. 181 Arkiverad 1 april 2018 på Wayback Machine .
2. ↑ Burkard Polster. En geometrisk bilderbok. - New York: Springer-Verlag, 1998. - S. 5. - (Universitex). — ISBN 0-387-98437-2 . - doi : 10.1007/978-1-4419-8526-2 .
3. ↑ FW Levi. Finita geometriska system. — Calcutta: University of Calcutta, 1942.
4. ↑ Harald Group. Handbook of combinatorial designs / Charles J. Colbourn, Jeffrey H. Dinitz. — För det andra. - Chapman & Hall / CRC, Boca Raton, FL, 2007. - P. 353-355. - (Diskret matematik och dess tillämpningar (Boca Raton)).
5. ↑ M. Conder, A. Malnič, D. Marušič, T. Pisanski, Z. Potočnik. Ljubljana-grafen . — Universitetet i Ljubljana Institutionen för matematik, 2002.

Länkar

• Weisstein, Eric W. Levi Graph  (engelska) på Wolfram MathWorld- webbplatsen .