Contele Levy

Graficul Levy (de asemenea , graficul de incidență ) este un grafic bipartit corespunzător structurii de incidență [1] [2] . Dintr-un set de puncte și linii într- o geometrie de incidență sau configurație proiectivă , se formează un grafic cu un vârf pentru fiecare punct, un vârf pentru fiecare linie și o muchie pentru fiecare punct și incidență a liniilor (adică, "punctul se află pe relație de linie). Acești conți au fost numiți după Friedrich Levi, care le-a descris în 1942 [1] [3] .

Graficul Levi al unui sistem de puncte și linii are de obicei o circumferință de cel puțin șase: orice ciclu de lungime 4 trebuie să corespundă cu două drepte care trec prin aceleași două puncte. Prin urmare, orice graf bipartit cu circumferință de cel puțin șase poate fi considerat ca un graf Levi al structurii abstracte de incidență [1] . Graficele Levi ale configurațiilor sunt biregulareiar orice graf biregular cu circumferința de cel puțin șase poate fi privit ca un graf Levi de configurație abstractă [4] .

Graficele Levy pot fi definite și pentru alte tipuri de structuri de incidență, cum ar fi incidențele dintre puncte și plane din spațiul euclidian . Pentru orice graf Levi, există un hipergraf echivalent și invers.

Exemple

• Graficul Desargues este graficul Levi al configurației Desargues , format din 10 puncte și 10 linii. Există 3 puncte pe fiecare linie și 3 linii trec prin fiecare punct. Graficul Desargues poate fi văzut și ca un graf Petersen generalizat G (10,3) sau ca un graf Kneser bipartit cu parametrii 5,2. Este un grafic cu 3 regulate cu 20 de vârfuri.

• Graficul Heawood este graficul Levi al planului Fano . Cunoscut și sub denumirea de celula (3,6) , este un grafic cu 3 regulate cu 14 vârfuri.

• Graficul Möbius–Cantor este graficul Lévy al configurației Möbius–Cantor , un sistem de 8 puncte și 8 drepte care nu poate fi realizat cu drepte pe planul euclidian. Este un grafic cu 3 regulate și are 16 vârfuri.

• Graficul Pappus este graficul Levi al configurației Pappus , format din 9 puncte și 9 linii. Ca și în configurația Desargues, există 3 puncte pe fiecare linie și 3 linii trec prin fiecare punct. Graficul este 3-regular și are 18 vârfuri.

• Graficul Gray este un grafic Levi cu o configurație care poate fi obținută în R 3 ca o rețea 3×3×3 de 27 de puncte și 27 de linii ortogonale prin aceste puncte.

• Thatta cu 8 celule este graficul Levi al configurației Cremona-Richmond . Graficul, cunoscut și ca o celulă (3,8), este 3-regular și are 30 de vârfuri.

• Graficul hipercubului cu patru dimensiuni Q 4 este graficul Levi al configurației Möbius format din punctele și planurile a două tetraedre înscrise reciproc. Aici, un tetraedru este considerat înscris într-un altul dacă toate vârfurile sale se află pe planuri care trec prin fețele altui tetraedru (nu neapărat pe fețele în sine).

• Graficul Ljubljana cu 112 vârfuri este graficul Lévy al configurației Ljubljana [5] .

Note

1. ↑ 1 2 3 Branko Grünbaum. Moștenirea Coxeter. - Providence, RI: Societatea Americană de Matematică, 2006. - P. 179-225. Vezi în special p. 181 Arhivat la 1 aprilie 2018 la Wayback Machine .
2. ↑ Burkard Polster. O carte cu imagini geometrice. - New York: Springer-Verlag, 1998. - P. 5. - (Universitex). — ISBN 0-387-98437-2 . - doi : 10.1007/978-1-4419-8526-2 .
3. ↑ FW Levi. Sisteme geometrice finite. — Calcutta: Universitatea din Calcutta, 1942.
4. ↑ Grupul Harald. Manual de desene combinatorii / Charles J. Colbourn, Jeffrey H. Dinitz. - Al doilea. - Chapman & Hall / CRC, Boca Raton, FL, 2007. - P. 353-355. - (Matematica discretă și aplicațiile sale (Boca Raton)).
5. ↑ M. Conder, A. Malnič, D. Marušič, T. Pisanski, Z. Potočnik. Graficul Ljubljana . — Universitatea din Ljubljana, Departamentul de Matematică, 2002.

Link -uri

• Weisstein, Eric W. Levi Graph  (engleză) pe site-ul Wolfram MathWorld .