En matemáticas combinatorias , un gráfico de Levi o gráfico de incidencia es un gráfico 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 gráfico con un vértice por punto, un vértice por línea y un borde para cada incidencia entre un punto y una línea. Llevan el nombre de Friedrich Wilhelm Levi , quien escribió sobre ellos en 1942. [1] [3]
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 que pasan por 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 Levi de configuraciones son biregulares , y cada gráfico biregular 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, existe un hipergráfico equivalente y viceversa.
