Grev Levy

Levy-grafen (også incidensgrafen ) er en todelt graf svarende til incidensstrukturen [1] [2] . Ud fra et sæt punkter og linjer i en indfaldsgeometri eller projektiv konfiguration dannes en graf med et toppunkt for hvert punkt, et toppunkt for hver linje og en kant for hvert punkt og linjeindfald (dvs. "punktet ligger på linje"-forhold). Disse grever blev opkaldt efter Friedrich Levi, der beskrev dem i 1942 [1] [3] .

Levi-grafen for et system af punkter og linjer har normalt en omkreds på mindst seks: enhver cyklus med længde 4 skal svare til to linjer, der går gennem de samme to punkter. Derfor kan enhver todelt graf med en omkreds på mindst seks betragtes som en Levi-graf af den abstrakte incidensstruktur [1] . Levi-grafer over konfigurationer er biregelmæssigeog enhver biregulær graf med en omkreds på mindst seks kan betragtes som en Levi-graf med abstrakt konfiguration [4] .

Afgiftsgrafer kan også defineres for andre typer af incidensstrukturer, såsom forekomster mellem punkter og planer i det euklidiske rum . For enhver Levi-graf er der en tilsvarende hypergraf og omvendt.

Eksempler

• Desargues-grafen er Levi- grafen for Desargues-konfigurationen , bestående af 10 punkter og 10 linjer. Der er 3 punkter på hver linje og 3 linjer går gennem hvert punkt. Desargues grafen kan også ses som en generaliseret Petersen graf G (10,3) eller som en todelt Kneser graf med parameter 5,2. Det er en 3-regulær graf med 20 hjørner.

• Heawood-grafen er Levi-grafen for Fano-flyet . Også kendt som (3,6) -cellen er det en 3-regulær graf med 14 hjørner.

• Möbius-Cantor-grafen er Lévy-grafen for Möbius-Cantor-konfigurationen , et system med 8 punkter og 8 linjer, der ikke kan realiseres med rette linjer på det euklidiske plan. Det er en 3-regulær graf og har 16 hjørner.

• Pappus- grafen er Levi-grafen for Pappus-konfigurationen , bestående af 9 punkter og 9 linjer. Som i Desargues-konfigurationen er der 3 punkter på hver linje og 3 linjer passerer gennem hvert punkt. Grafen er 3-regulær og har 18 hjørner.

• Den grå graf er en Levi graf af en konfiguration, der kan opnås i R 3 som et 3×3×3 gitter med 27 punkter og 27 ortogonale linjer gennem disse punkter.

• Den 8-cellede Thatta er Levi-grafen for Cremona-Richmond-konfigurationen . Grafen, også kendt som en (3,8)-celle, er 3-regulær og har 30 hjørner.

• Grafen for den firedimensionelle hyperkube Q 4 er Levi-grafen for Möbius-konfigurationen dannet af punkterne og planerne af to indbyrdes indskrevne tetraedre. Her betragtes et tetraeder som indskrevet i et andet, hvis alle dets toppunkter ligger på planer, der passerer gennem ansigterne på et andet tetraeder (ikke nødvendigvis på selve ansigterne).

• Ljubljana - grafen med 112 hjørner er Lévy-grafen for Ljubljana-konfigurationen [5] .

Noter

1. ↑ 1 2 3 Branko Grünbaum. Coxeter-arven. - Providence, RI: American Mathematical Society, 2006. - S. 179-225. Se især s. 181 Arkiveret 1. april 2018 på Wayback Machine .
2. ↑ Burkard Polster. En geometrisk billedbog. - New York: Springer-Verlag, 1998. - S. 5. - (Universitex). — ISBN 0-387-98437-2 . - doi : 10.1007/978-1-4419-8526-2 .
3. ↑ FW Levi. Finite geometriske systemer. — Calcutta: University of Calcutta, 1942.
4. ↑ Harald Gruppen. Håndbog i kombinatoriske designs / Charles J. Colbourn, Jeffrey H. Dinitz. - Sekund. - Chapman & Hall / CRC, Boca Raton, FL, 2007. - S. 353-355. - (Diskret matematik og dens anvendelser (Boca Raton)).
5. ↑ M. Conder, A. Malnič, D. Marušič, T. Pisanski, Z. Potočnik. Ljubljana-grafen . — Universitetet i Ljubljana Institut for Matematik, 2002.

Links

• Weisstein, Eric W. Levi Graph  (engelsk) på Wolfram MathWorld- webstedet .