Estructura de incidencia

Ejemplos de estructuras de incidencia: Ejemplo 1: puntos y líneas del plano euclidiano (arriba) Ejemplo 2: puntos y círculos (centro) Ejemplo 3: estructura de incidencia finita definida por una matriz de incidencia (abajo)

En matemáticas , una estructura de incidencia es un sistema abstracto que consta de dos tipos de objetos y una única relación entre ellos. Consideremos los puntos y las rectas del plano euclidiano como los dos tipos de objetos e ignoremos todas las propiedades de esta geometría, excepto la relación que indica qué puntos inciden sobre qué rectas para todos los puntos y rectas. Lo que queda es la estructura de incidencia del plano euclidiano.

Las estructuras de incidencia se suelen considerar en el contexto geométrico, donde se abstraen de los planos (como los planos afines , proyectivos y de Möbius ) y, por lo tanto, los generalizan; sin embargo, el concepto es muy amplio y no se limita a entornos 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 las estructuras finitas se denomina a veces geometría finita . ^[¹^]

Definición formal y terminología

Una estructura de incidencia es una tripleta ( $P, L, I$ ) donde $P$ es un conjunto cuyos elementos se denominan puntos , $L$ es un conjunto distinto cuyos elementos se denominan líneas e $I \subseteq P \times L$ es la relación de incidencia . Los elementos de $I$ se denominan banderas. Si ( $p$ $,$ $l$ ) pertenece a $I$ , se puede decir que el punto $p$ "se encuentra sobre" 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 utiliza la notación $p$ $I$ $l como$ ^sinónimo de $($ $p$ $,$ $l$ $) \in$ $I.$ [ ²^]

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 de teoría 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):{\vec {v}}{\text{ es un vector propio de la matriz }}M\}.$ Este ejemplo también muestra que, si bien se utiliza el lenguaje geométrico de puntos y líneas, los tipos de objetos no tienen por qué ser estos objetos geométricos.

Ejemplos

Algunos ejemplos de estructuras de incidencia

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 grafo (que no tiene por qué ser simple ; se permiten bucles y aristas múltiples ) es una estructura de incidencia uniforme con dos puntos por línea. En estos ejemplos, los vértices del grafo forman el conjunto de puntos, las aristas forman el conjunto de líneas, y la incidencia significa que un vértice es un extremo de una arista.

Espacios lineales

Las estructuras de incidencia rara vez se estudian en toda su generalidad; lo habitual es estudiar estructuras de incidencia que satisfacen algunos axiomas adicionales. Por ejemplo, un espacio lineal parcial es una estructura de incidencia que satisface:

Dos puntos cualesquiera distintos son incidentes con como máximo 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 cualesquiera son incidentes con exactamente una línea común,

La estructura de incidencia se denomina espacio lineal . ^{[ 4 ]}^{[ 5 ]}

Redes

Un ejemplo más especializado es una $k$ -red . Se trata de una estructura de incidencia en la que las líneas se dividen en $k$ clases paralelas , de modo que dos líneas de la misma clase paralela no tienen puntos en común, pero dos líneas de clases diferentes tienen exactamente un punto en común, y cada punto pertenece a una única línea de cada clase paralela. Un ejemplo de $k$ -red 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 $I.$ De la definición se deduce inmediatamente que: $C^{**}=C$

Esta es una versión abstracta de la dualidad proyectiva . ^{[ 2 ]}

Una estructura $C$ que es isomorfa a su dual $C *$ se denomina autodual . El plano de Fano de arriba es una estructura de incidencia autodual.

Otra terminología

El concepto de estructura de incidencia es muy simple y ha surgido en diversas disciplinas, cada una con su propio vocabulario y especificando los tipos de preguntas que suelen plantearse sobre estas estructuras. Las estructuras de incidencia utilizan terminología geométrica, pero en teoría de grafos se denominan hipergrafos y en teoría del diseño combinatorio, diseños de bloques . En un contexto general, también se las conoce como sistema de conjuntos o familia de conjuntos .

Hipergrafos

Cada hipergrafo o sistema de conjuntos puede considerarse una estructura de incidencia en la que el conjunto universal representa los "puntos", la familia correspondiente de subconjuntos representa las "líneas" y la relación de incidencia es la pertenencia al conjunto " $\in$ ". A la inversa, toda estructura de incidencia puede verse como un hipergrafo al identificar las líneas con los conjuntos de puntos que inciden en ellas.

Diseños de bloques

Un diseño de bloques (general) es un conjunto $X$ junto con una familia $F$ de subconjuntos de $X$ (se permiten subconjuntos repetidos). Normalmente, un diseño de bloques debe satisfacer 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 multiconjunto). Si todos los subconjuntos en $F$ tienen el mismo tamaño, el diseño de bloques se llama uniforme . Si cada elemento de $X$ aparece en el mismo número de subconjuntos, el diseño de bloques se dice que es regular . El dual de un diseño uniforme es un diseño regular y viceversa.

Ejemplo: Avión de Fano

Considere el diseño de bloques/hipergrafo dado por: ${\begin{aligned}P&=\{1,2,3,4,5,6,7\},\\[2pt]L&=\left\{{\begin{array}{ll}\{1,2,3\},&\{1,4,5\},\\\{1,6,7\},&\{2,4,6\},\\\{2,5,7\},&\{3,4,7\},\\\{3,5,6\}\end{array}}\right\}.\end{aligned}}$

Esta estructura de incidencia se denomina plano de Fano . Como diseño de bloques, es uniforme y regular.

En el etiquetado dado, las líneas son precisamente los subconjuntos de los puntos que constan de tres puntos cuyas etiquetas suman cero usando la suma de nim . Alternativamente, cada número, cuando se escribe en binario , puede identificarse con un vector no nulo de longitud tres sobre el campo binario . Tres vectores que generan un subespacio forman una línea; en este caso, eso es equivalente a que su suma vectorial sea el vector cero.

Representaciones

Las estructuras de incidencia pueden representarse de muchas maneras. Si los conjuntos $P$ y $L$ son finitos, estas representaciones pueden codificar de forma compacta toda la información relevante sobre la estructura.

Matriz de incidencia

La matriz de incidencia de una estructura de incidencia (finita) es una matriz (0,1) cuyas filas están indexadas por los puntos ${p i}$ y sus columnas por las líneas ${l j}$ , donde la entrada $ij$ es 1 si $p i | l j$ y 0 en caso contrario. ^{[ a ]} Una matriz de incidencia no está determinada de forma única, ya que depende del orden arbitrario de los puntos y las líneas. ^{[ 6 ]}

La estructura de incidencia no uniforme que se muestra arriba (ejemplo número 2) viene dada por: ${\begin{aligned}P&=\{A,B,C,D,E,P\}\\[2pt]L&=\left\{{\begin{array}{ll}l=\{C,P,E\},&m=\{P\},\\n=\{P,D\},&o=\{P,A\},\\p=\{A,B\},&q=\{P,B\}\end{array}}\right\}\end{aligned}}$

La matriz de incidencia para esta estructura es: ${\begin{pmatrix}0&0&0&1&1&0\\0&0&0&0&1&1\\1&0&0&0&0&0\\0&0&1&0&0&0\\1&0&0&0&0&0\\1&1&1&1&0&1\end{pmatrix}}$ que corresponde a la tabla de incidencia:

Si una estructura de incidencia $C$ tiene una matriz de incidencia $M$ , entonces la estructura dual $C *$ tiene la matriz transpuesta $M$ ^T como su matriz de incidencia (y está definida por esa matriz).

Una estructura de incidencia es autodual si existe un ordenamiento de los puntos y las líneas tal que la matriz de incidencia construida con ese ordenamiento 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 de Fano tiene la matriz de incidencia: ${\begin{pmatrix}1&1&1&0&0&0&0\\1&0&0&1&1&0&0\\1&0&0&0&0&1&1\\0&1&0&1&0&1&0\\0&1&0&0&1&0&1\\0&0&1&1&0&0&1\\0&0&1&0&1&1&0\end{pmatrix}}.$ Dado que se trata de una matriz simétrica, el plano de Fano es una estructura de incidencia autodual.

Representaciones pictóricas

Una figura de incidencia (es decir, una representación de una estructura de incidencia) se construye representando los puntos mediante puntos en un plano y utilizando algún medio visual para unir los puntos y formar líneas. ^{[ 6 ]} Los puntos pueden colocarse de cualquier manera; no existen restricciones en cuanto a las distancias entre puntos ni a las relaciones entre ellos. En una estructura de incidencia, no existe el concepto de que un punto se encuentre entre otros dos; el orden de los puntos en una línea es indefinido. Compárese esto con la geometría ordenada , que sí contempla la noción de intermediación. Lo mismo puede decirse de las representaciones de las líneas. En particular, las líneas no tienen por qué representarse mediante "segmentos de línea recta" (véanse los ejemplos 1, 3 y 4 anteriores). Al igual que en la representación gráfica de los gráficos , el cruce de dos "líneas" en cualquier punto que no sea un punto carece de significado en términos de la estructura de incidencia; es simplemente una casualidad de la representación. Estas figuras de incidencia pueden, en ocasiones, asemejarse a gráficos, pero no lo son a menos que la estructura de incidencia sea un gráfico.

Realizabilidad

Las estructuras de incidencia pueden modelarse mediante puntos y curvas en el plano euclidiano con el significado geométrico habitual de incidencia. Algunas estructuras de incidencia admiten representación mediante puntos y líneas (rectas). Las estructuras que pueden ser se denominan realizables . Si no se menciona ningún espacio ambiente, se asume el plano euclidiano. El plano de Fano (ejemplo 1 anterior) no es realizable ya que necesita al menos una curva. La configuración de Möbius-Kantor (ejemplo 4 anterior) no es realizable en el plano euclidiano, pero sí lo es en el plano complejo . ^{[ 7 ]} Por otro lado, los ejemplos 2 y 5 anteriores son realizables y las figuras de incidencia que se dan allí lo demuestran. Steinitz (1894) ^{[ 8 ]} ha demostrado que $las n 3$ -configuraciones (estructuras de incidencia con $n$ puntos y $n$ líneas, tres puntos por línea y tres líneas que pasan por cada punto) son realizables o requieren el uso de solo una línea curva en sus representaciones. ^{[ 9 ]} El plano de Fano es el único ( $73$ ) y la configuración de Möbius-Kantor es la única ( $83$ ).

Gráfico de incidencia (gráfico de Levi)

Cada estructura de incidencia $C$ corresponde a un grafo bipartito llamado grafo de Levi o grafo de incidencia de la estructura. Como cualquier grafo bipartito es bicoloreable, al grafo de Levi se le puede asignar una coloración de vértices en blanco y negro , donde los vértices negros corresponden a puntos y los vértices blancos a líneas de $C.$ Las aristas de este grafo corresponden a las banderas (pares de punto/línea incidentes) de la estructura de incidencia. El grafo de Levi original era el grafo de incidencia del cuadrilátero generalizado de orden dos (ejemplo 3 anterior), ^{[ 10 ]} pero el término fue extendido por HSM Coxeter ^{[ 11 ]} para referirse a un grafo de incidencia de cualquier estructura de incidencia. ^{[ 12 ]}

Ejemplos de gráficos de Levi

El grafo de Levi del plano de Fano es el grafo de Heawood . Dado que el grafo de Heawood es conexo y transitivo respecto a los vértices , existe un automorfismo (como el definido por una reflexión respecto al eje vertical en la figura del grafo de Heawood) que intercambia vértices blancos y negros. Esto, a su vez, implica que el plano de Fano es autodual.

La representación específica, a la izquierda, del grafo de Levi de la configuración de Möbius-Kantor (ejemplo 4 anterior) ilustra que una rotación de $π /4$ alrededor del centro (en sentido horario o antihorario) del diagrama intercambia los vértices azules y rojos y mapea aristas con aristas. Es decir, existe un automorfismo de intercambio de colores en este grafo. En consecuencia, la estructura de incidencia conocida como configuración de Möbius-Kantor es autodual.

Generalización

Es posible generalizar la noción de una 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$ . ^[¹²^] Formalmente, estas se definen como $k$ $+ 1$ tuplas $S$ $= ($ $P$ $1$ $,$ $P$ $2$ $, ...,$ $P$ $k$ $,$ $I$ $)$ con $P$ $i$ $\cap$ $P$ $j$ $= \emptyset$ y $I\subseteq \bigcup _{i<j}P_{i}\times P_{j}.$

El grafo de Levi para estas estructuras se define como un grafo multipartito en el que los vértices correspondientes a cada tipo están coloreados del mismo color.

Véase también

Notas

↑ También se utiliza ampliamente la otra convención de indexar las filas por líneas y las columnas por puntos.

Referencias

^ Colbourn y Dinitz 2007 , pág. 702
1 2 Dembowski 1968 , págs. 1–2
↑ Biliotti, Jha y Johnson 2001 , pág. 508
↑ El término espacio lineal también se utiliza para referirse a espacios vectoriales, pero esto rara vez causará confusión.
↑ Moorhouse 2014 , pág. 5
1 2 Beth, Jungnickel y Lenz 1986 , pág. 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 ( 1–3 ): 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 autoduales y grafos regulares", Bulletin of the American Mathematical Society , 56 (5): 413–455 , doi : 10.1090/s0002-9904-1950-09407-5
^ Pisanski y Servatius 2013 , pág. 158

Bibliografía

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 traslación , Marcel Dekker , ISBN 0-8247-0609-9
Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios (2.ª ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1
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
Moorhouse, G. Eric (2014). "Geometría de incidencia" (PDF) – vía John Baez en la Universidad de California, Riverside .
Pisanski, Tomaž; Servatius, Brigitte (2013), Configurations from a Graphical Viewpoint , Springer, doi : 10.1007/978-0-8176-8364-1 , ISBN 978-0-8176-8363-4

Lecturas adicionales

CRC Press (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

[6] También se utiliza ampliamente la otra convención de indexar las filas por líneas y las columnas por puntos.

[1] Colbourn y Dinitz 2007 , pág. 702

[Demb1-2] 1 2 Dembowski 1968 , págs. 1–2

[3] Biliotti, Jha y Johnson 2001 , pág. 508

[4] El término espacio lineal también se utiliza para referirse a espacios vectoriales, pero esto rara vez causará confusión.

[5] Moorhouse 2014 , pág. 5

[Beth17-7] 1 2 Beth, Jungnickel y Lenz 1986 , pág. 17

[8] Pisanski y Servatius 2013 , p. 222

[9] E. Steinitz (1894), Über die Construction der Configurationen $n 3$ , Disertación, Breslau

[10] Gropp, Harald (1997), "Configuraciones y sus realizaciones", Matemáticas Discretas , 174 ( 1–3 ): 137–151 , doi : 10.1016/s0012-365x(96)00327-5

[11] Levi, FW (1942), Sistemas geométricos finitos , Calcuta: Universidad de Calcuta, MR 0006834

[12] Coxeter, HSM (1950), "Configuraciones autoduales y grafos regulares", Bulletin of the American Mathematical Society , 56 (5): 413–455 , doi : 10.1090/s0002-9904-1950-09407-5

[Pisanski158-13] Pisanski y Servatius 2013 , pág. 158

[

sinónimo

[ 3 ]

[ 4 ]

[ 5 ]

[ a ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]