En matemáticas , un sistema abstracto que consta de dos tipos de objetos y una sola relación entre estos tipos de objetos se denomina estructura de incidencia . Considere los puntos y las líneas del plano euclidiano como los dos tipos de objetos e ignore todas las propiedades de esta geometría excepto la relación de qué puntos están en qué líneas para todos los puntos y líneas. Lo que queda es la estructura de incidencia del plano euclidiano.
Las estructuras de incidencia se consideran con mayor frecuencia en el contexto geométrico donde se abstraen y, por lo tanto, generalizan los planos (como los planos afín , proyectivo y de Möbius ), pero el concepto es muy amplio y no se limita a los escenarios geométricos. Incluso en un entorno geométrico, las estructuras de incidencia no se limitan solo a puntos y líneas; Se pueden utilizar objetos de dimensiones superiores (planos, sólidos, n- espacios, cónicas, etc.). El estudio de estructuras finitas a veces se denomina geometría finita . [1]
Definición y terminología formal
Una estructura de incidencia es una triple ( P , L , I ) donde P es un conjunto cuyos elementos se llaman puntos , L es un conjunto distinto cuyos elementos se llaman líneas e I ⊆ P × L es la relación de incidencia . Los elementos de I se llaman banderas. Si ( p , l ) está en I, entonces se puede decir que el punto p "está en" la línea l o que la línea l "pasa por" el punto p . Una terminología más "simétrica", para reflejar la naturaleza simétrica de esta relación, es que " p es incidente con l " o que " l es incidente con p " y usa la notación p I l como sinónimo de ( p , l ) ∈ I . [2]
En algunas situaciones comunes, L puede ser un conjunto de subconjuntos de P, en cuyo caso la incidencia I será de contención ( p I l si y solo si p es un miembro de l ). Las estructuras de incidencia de este tipo se denominan teóricas de conjuntos . [3] Este no es siempre el caso, por ejemplo, si P es un conjunto de vectores y L un conjunto de matrices cuadradas , podemos definir I = {( v , M ): el vector v es un vector propio de la matriz M }. Este ejemplo también muestra que mientras se usa el lenguaje geométrico de puntos y líneas, los tipos de objetos no necesitan ser estos objetos geométricos.
Ejemplos de
1. Avión Fano
2. Estructura no uniforme
Una estructura de incidencia es uniforme si cada línea incide con el mismo número de puntos. Cada uno de estos ejemplos, excepto el segundo, es uniforme con tres puntos por línea.
Gráficos
Cualquier gráfico (que no tiene por qué ser simple ; se permiten bucles y bordes múltiples ) es una estructura de incidencia uniforme con dos puntos por línea. Para estos ejemplos, los vértices del gráfico forman el conjunto de puntos, los bordes del gráfico forman el conjunto de líneas y la incidencia significa que un vértice es el punto final de un borde.
Espacios lineales
Las estructuras de incidencia rara vez se estudian en su completa generalidad; es típico estudiar estructuras de incidencia que satisfacen algunos axiomas adicionales. Por ejemplo, un espacio lineal parcial es una estructura de incidencia que satisface:
- Cualesquiera dos puntos distintos inciden como máximo con una línea común, y
- Cada línea es incidente con al menos dos puntos.
Si el primer axioma anterior se reemplaza por el más fuerte:
- Dos puntos distintos son incidentes con exactamente una línea común,
la estructura de incidencia se llama espacio lineal . [4] [5]
Redes
Un ejemplo más especializado es k -net . Ésta es una estructura de incidencia en la que las líneas caen en k clases paralelas , de modo que dos líneas en la misma clase paralela no tienen puntos comunes, pero dos líneas en clases diferentes tienen exactamente un punto común, y cada punto pertenece exactamente a una línea desde cada clase paralela. Un ejemplo de k -net es el conjunto de puntos de un plano afín junto con k clases paralelas de líneas afines.
Estructura dual
Si intercambiamos el papel de "puntos" y "líneas" en
- C = ( P , L , I )
obtenemos la estructura dual ,
- C ∗ = ( L , P , I ∗ ) ,
donde I * es la relación inversa de la I . De la definición se desprende inmediatamente que:
- C ** = C .
Ésta es una versión abstracta de la dualidad proyectiva . [2]
Una estructura C que es isomorfa a su dual C ∗ se llama auto-dual . El plano de Fano de arriba es una estructura de incidencia auto-dual.
Otra terminología
El concepto de estructura de incidencia es muy simple y ha surgido en varias disciplinas, cada una de las cuales presenta su propio vocabulario y especifica los tipos de preguntas que normalmente se hacen sobre estas estructuras. Las estructuras de incidencia utilizan una terminología geométrica, pero en términos de teoría de grafos se denominan hipergráficos y en términos de teoría de diseño se denominan diseños de bloques . También se conocen como sistema de conjuntos o familia de conjuntos en un contexto general.
Hipergrafos
Cada hipergrama o sistema de conjuntos puede considerarse como una estructura de incidencia en la que el conjunto universal desempeña el papel de "puntos", la correspondiente familia de conjuntos desempeña el papel de "líneas" y la relación de incidencia es la pertenencia al conjunto "∈". A la inversa, cada estructura de incidencia puede verse como un hipergráfico identificando las líneas con los conjuntos de puntos que inciden en ellas.
Diseños de bloques
Un diseño de bloque (general) es un conjunto X junto con una familia F de subconjuntos de X (se permiten subconjuntos repetidos). Normalmente se requiere un diseño de bloque para satisfacer las condiciones de regularidad numérica. Como estructura de incidencia, X es el conjunto de puntos y F es el conjunto de líneas, generalmente llamados bloques en este contexto (los bloques repetidos deben tener nombres distintos, por lo que F es en realidad un conjunto y no un conjunto múltiple). Si todos los subconjuntos de F tienen el mismo tamaño, el diseño de bloque se denomina uniforme . Si cada elemento de X aparece en el mismo número de subconjuntos, se dice que el diseño del bloque es regular . El diseño dual de un diseño uniforme es un diseño regular y viceversa.
Ejemplo: avión Fano
Considere el diseño de bloque / hipergrama dado por:
- ,
- .
Esta estructura de incidencia se denomina plano de Fano . Como diseño de bloque, es uniforme y regular.
En el etiquetado dado, las líneas son precisamente los subconjuntos de los puntos que consisten en tres puntos cuyas etiquetas suman cero usando la suma nim . Alternativamente, cada número, cuando se escribe en binario , puede identificarse con un vector distinto de cero de longitud tres sobre el campo binario . Tres vectores que generan un subespacio forman una línea; en este caso, eso equivale a que su suma vectorial sea el vector cero.
Representaciones
Las estructuras de incidencia se pueden representar de muchas formas. Si los conjuntos P y L son finitos, estas representaciones pueden codificar de forma compacta toda la información relevante relativa a la estructura.
Matriz de incidencia
La matriz de incidencia de una estructura de incidencia (finita) es una matriz (0,1) que tiene sus filas indexadas por los puntos { p i } y las columnas indexadas por las líneas { l j } donde la ij -ésima entrada es un 1 si p i I l j y 0 en caso contrario. [6] Una matriz de incidencia no se determina de forma única ya que depende del orden arbitrario de los puntos y las líneas. [7]
La estructura de incidencia no uniforme que se muestra arriba (ejemplo número 2) viene dada por:
- P = { A , B , C , D , E , P }
- L = { l = { C , P , E }, m = { P }, n = { P , D }, o = { P , A }, p = { A , B }, q = { P , B } } .
Una matriz de incidencia para esta estructura es:
que corresponde a la tabla de incidencia:
I l metro norte o pag q A 0 0 0 1 1 0 B 0 0 0 0 1 1 C 1 0 0 0 0 0 D 0 0 1 0 0 0 mi 1 0 0 0 0 0 PAG 1 1 1 1 0 1
Si una estructura de incidencia C tiene una matriz de incidencia M , entonces la estructura dual C ∗ tiene la matriz de transposición M T como su matriz de incidencia (y está definida por esa matriz).
Una estructura de incidencia es auto-dual si existe un orden de los puntos y líneas de modo que la matriz de incidencia construida con ese orden sea una matriz simétrica .
Con las etiquetas dadas en el ejemplo número 1 anterior y con los puntos ordenados A , B , C , D , G , F , E y las líneas ordenadas l , p , n , s , r , m , q , el plano Fano tiene la incidencia matriz:
Dado que se trata de una matriz simétrica, el plano de Fano es una estructura de incidencia auto-dual.
Representaciones pictóricas
Una figura de incidencia (es decir, una descripción de una estructura de incidencia), se construye representando los puntos por puntos en un plano y teniendo algún medio visual de unir los puntos para que correspondan a líneas. [7] Los puntos pueden colocarse de cualquier manera, no hay restricciones sobre las distancias entre puntos o cualquier relación entre puntos. En una estructura de incidencia no existe el concepto de que un punto esté entre otros dos puntos; el orden de los puntos en una línea no está definido. Compare esto con la geometría ordenada , que tiene una noción de intermediación. Se pueden hacer las mismas declaraciones sobre las representaciones de las líneas. En particular, las líneas no necesitan estar representadas por "segmentos de línea recta" (ver ejemplos 1, 3 y 4 arriba). Como ocurre con la representación pictórica de gráficos , el cruce de dos "líneas" en cualquier lugar que no sea un punto no tiene ningún significado en términos de la estructura de incidencia; es solo un accidente de la representación. Estas cifras de incidencia a veces pueden parecerse a gráficos, pero no son gráficos a menos que la estructura de incidencia sea un gráfico.
Realizabilidad
Las estructuras de incidencia se pueden modelar mediante puntos y curvas en el plano euclidiano con el significado geométrico habitual de incidencia. Algunas estructuras de incidencia admiten la representación por puntos y líneas (rectas). Las estructuras que pueden ser se denominan realizables . Si no se menciona ningún espacio ambiental, se asume el plano euclidiano. El plano de Fano (ejemplo 1 arriba) no es realizable ya que necesita al menos una curva. La configuración de Möbius-Kantor (ejemplo 4 arriba) no se puede realizar en el plano euclidiano, pero sí en el plano complejo . [8] Por otro lado, los ejemplos 2 y 5 anteriores son realizables y las cifras de incidencia dadas allí lo demuestran. Steinitz (1894) [9] ha demostrado que n 3 configuraciones (estructuras de incidencia con n puntos yn líneas, tres puntos por línea y tres líneas a través de cada punto) son realizables o requieren el uso de una sola línea curva en sus representaciones. . [10] El plano de Fano es el único ( 7 3 ) y la configuración de Möbius-Kantor es el único ( 8 3 ).
Gráfico de incidencia (gráfico de Levi)
Cada estructura de incidencia C corresponde a un gráfico bipartito llamado gráfico de Levi o gráfico de incidencia de la estructura. Como cualquier gráfico bipartito es de dos coloreable, el gráfico Levi se puede dar un blanco y negro colorante vértice , donde vértices negros corresponden a los puntos y vértices blancas corresponden a las líneas de C . Los bordes de este gráfico corresponden a las banderas (puntos de incidencia / pares de líneas) de la estructura de incidencia. El gráfico de Levi original era el gráfico de incidencia del cuadrángulo generalizado de orden dos (ejemplo 3 anterior), [11] pero el término ha sido ampliado por HSM Coxeter [12] para referirse a un gráfico de incidencia de cualquier estructura de incidencia. [13]
Ejemplos de gráficos de Levi
El gráfico de Levi del plano de Fano es el gráfico de Heawood . Dado que el gráfico de Heawood está conectado y es transitivo a vértices , existe un automorfismo (como el definido por una reflexión sobre el eje vertical en la figura del gráfico de Heawood) que intercambia vértices en blanco y negro. Esto, a su vez, implica que el plano de Fano es auto-dual.
La representación específica, a la izquierda, del gráfico de Levi de la configuración de Möbius-Kantor (ejemplo 4 arriba) ilustra que una rotación de π / 4 alrededor del centro (ya sea en sentido horario o antihorario) del diagrama intercambia los vértices azul y rojo y asigna bordes a bordes. Es decir, existe un automorfismo de intercambio de colores de este gráfico. En consecuencia, la estructura de incidencia conocida como configuración de Möbius-Kantor es auto-dual.
Generalización
Es posible generalizar la noción de estructura de incidencia para incluir más de dos tipos de objetos. Una estructura con k tipos de objetos se denomina estructura de incidencia de rango k o geometría de rango k . [13] Formalmente, estos se definen como k + 1 tuplas S = ( P 1 , P 2 , ..., P k , I ) con P i ∩ P j = ∅ y
El gráfico de Levi para estas estructuras se define como un gráfico multipartito con los vértices correspondientes a cada tipo con el mismo color.
Ver también
- Incidencia (geometría)
- Geometría de incidencia
- Configuración proyectiva
Notas
- ^ Colbourn y Dinitz 2007 , p. 702
- ↑ a b Dembowski 1968 , págs. 1-2
- ^ Biliotti, Jha y Johnson 2001 , p. 508
- ^ El término espacio lineal también se usa para referirse a espacios vectoriales, pero esto rara vez causará confusión.
- ^ Moorhouse 2007 , p. 5
- ^ La otra convención de indexar las filas por líneas y las columnas por puntos también se usa ampliamente.
- ↑ a b Beth, Jungnickel y Lenz 1986 , p. 17
- ^ Pisanski y Servatius 2013 , p. 222
- ^ E. Steinitz (1894), Über die Construction der Configurationen n 3 , Disertación, Breslau
- ^ Gropp, Harald (1997), "Configuraciones y sus realizaciones", Matemáticas discretas , 174 : 137-151, doi : 10.1016 / s0012-365x (96) 00327-5
- ^ Levi, FW (1942), Sistemas geométricos finitos , Calcuta: Universidad de Calcuta, MR 0006834
- ^ Coxeter, HSM (1950), "Configuraciones auto-duales y gráficos regulares", Boletín de la American Mathematical Society , 56 : 413–455, doi : 10.1090 / s0002-9904-1950-09407-5
- ↑ a b Pisanski y Servatius , 2013 , p. 158
Referencias
- Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986), teoría del diseño , Cambridge University Press, ISBN 3-411-01675-2
- Biliotti, Mauro; Jha, Vikram; Johnson, Norman L. (2001), Fundamentos de los planos de traducción , Marcel Dekker , ISBN 0-8247-0609-9
- Colbourn, Charles J .; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios (2a ed.), Boca Raton: Chapman & Hall / CRC, ISBN 1-58488-506-8
- Dembowski, Peter (1968), Geometrías finitas , Ergebnisse der Mathematik und ihrer Grenzgebiete , Band 44, Berlín, Nueva York: Springer-Verlag , ISBN 3-540-61786-8, MR 0233275
- G. Eric Moorhouse (2014) Geometría de incidencia a través de John Baez en la Universidad de California, Riverside
- Pisanski, Tomaž; Servatius, Brigitte (2013), Configuraciones desde un punto de vista gráfico , Springer, doi : 10.1007 / 978-0-8176-8364-1 , ISBN 978-0-8176-8363-4
Otras lecturas
- Prensa CRC (2000). Manual de matemáticas discretas y combinatorias , (Capítulo 12.2), ISBN 0-8493-0149-1
- Harold L. Dorwart (1966) La geometría de la incidencia , Prentice Hall