En matemática combinatoria , un gráfico de Levi o gráfico de incidencia es un gráfico bipartito asociado con una estructura de incidencia . [1] [2] A partir de una colección de puntos y líneas en una geometría de incidencia o una configuración proyectiva , formamos un gráfico con un vértice por punto, un vértice por línea y una arista por cada incidencia entre un punto y una línea. Llevan el nombre de Friedrich Wilhelm Levi , quien escribió sobre ellos en 1942. [1] [3]
Gráfico de Levi | |
---|---|
Circunferencia | ≥ 6 |
Tabla de gráficos y parámetros |
La gráfica de Levi de un sistema de puntos y líneas generalmente tiene una circunferencia de al menos seis: Cualesquiera 4 ciclos corresponderían a dos líneas a través de los mismos dos puntos. Por el contrario, cualquier gráfico bipartito con una circunferencia de al menos seis puede verse como el gráfico de Levi de una estructura de incidencia abstracta. [1] Los gráficos de configuraciones de Levi son birregulares , y cada gráfico birregular con una circunferencia de al menos seis puede verse como el gráfico de Levi de una configuración abstracta. [4]
Los gráficos de Levi también se pueden definir para otros tipos de estructura de incidencia, como las incidencias entre puntos y planos en el espacio euclidiano . Para cada gráfico de Levi, hay un hipergráfico equivalente y viceversa.
Ejemplos de
- El gráfico de Desargues es el gráfico de Levi de la configuración de Desargues , compuesto por 10 puntos y 10 líneas. Hay 3 puntos en cada línea y 3 líneas que pasan por cada punto. El gráfico de Desargues también se puede ver como el gráfico de Petersen generalizado G (10,3) o el gráfico de Kneser bipartito con los parámetros 5,2. Es 3-regular con 20 vértices.
- El gráfico de Heawood es el gráfico de Levi del plano de Fano . También se conoce como la jaula (3,6) , y es 3-regular con 14 vértices.
- El gráfico de Möbius-Kantor es el gráfico de Levi de la configuración de Möbius-Kantor , un sistema de 8 puntos y 8 líneas que no se pueden realizar mediante líneas rectas en el plano euclidiano. Es 3-regular con 16 vértices.
- El gráfico de Pappus es el gráfico de Levi de la configuración de Pappus , compuesto por 9 puntos y 9 líneas. Al igual que la configuración de Desargues, hay 3 puntos en cada línea y 3 líneas que pasan por cada punto. Es 3-regular con 18 vértices.
- El gráfico de Gray es el gráfico de Levi de una configuración que se puede realizar en como un cuadrícula de 27 puntos y las 27 líneas ortogonales que los atraviesan.
- El Tutte de ocho jaulas es el gráfico de Levi de la configuración Cremona-Richmond . También se conoce como la jaula (3,8) y es 3-regular con 30 vértices.
- El gráfico de hipercubo de cuatro dimensiones es el gráfico de Levi de la configuración de Möbius formado por los puntos y planos de dos tetraedros mutuamente incidentes.
- El gráfico de Ljubljana en 112 vértices es el gráfico de Levi de la configuración de Ljubljana. [5]
Referencias
- ^ a b c Grünbaum, Branko (2006), "Configuraciones de puntos y líneas", The Coxeter Legacy , Providence, RI: American Mathematical Society, págs. 179-225, MR 2209028. Ver en particular la p. 181 .
- ^ Polster, Burkard (1998), A Geometrical Picture Book , Universitext, Nueva York: Springer-Verlag, p. 5, doi : 10.1007 / 978-1-4419-8526-2 , ISBN 0-387-98437-2, MR 1640615.
- ^ Levi, FW (1942), Sistemas geométricos finitos , Calcuta: Universidad de Calcuta , MR 0006834.
- ^ Gropp, Harald (2007), "VI.7 Configurations", en Colbourn, Charles J .; Dinitz, Jeffrey H. (eds.), Manual de diseños combinatorios , Matemáticas discretas y sus aplicaciones (Boca Raton) (Segunda ed.), Chapman & Hall / CRC, Boca Raton, Florida, págs. 353–355.
- ^ Conder, Marston ; Malnič, Aleksander; Marušič, Dragan ; Pisanski, Tomaž ; Potočnik, Primož (2002), The Ljubljana Graph (PDF) , IMFM Preprint 40-845, Departamento de Matemáticas de la Universidad de Ljubljana.
enlaces externos
- Weisstein, Eric W. "Levi Graph" . MathWorld .