En matemáticas combinatorias , un grafo de Levi o grafo de incidencia es un grafo bipartito asociado a 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 grafo 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. Reciben su nombre de Friedrich Wilhelm Levi , quien escribió sobre ellos en 1942. [1] [3]
El gráfico de Levi de un sistema de puntos y líneas suele tener una circunferencia de al menos seis: cualquier ciclo de 4 correspondería a dos líneas que pasan por los mismos dos puntos. Por el contrario, cualquier gráfico bipartito con una circunferencia de al menos seis puede considerarse como el gráfico de Levi de una estructura de incidencia abstracta. [1] Los gráficos de Levi de configuraciones son biregulares , y todo gráfico biregular con una circunferencia de al menos seis puede considerarse como el gráfico de Levi de una configuración abstracta. [4]
Los grafos de Levi también pueden definirse para otros tipos de estructuras de incidencia, como las incidencias entre puntos y planos en el espacio euclidiano . Para cada grafo de Levi, existe un hipergrafo equivalente y viceversa.
