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 estos tipos de objetos. 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 de los planos y, por lo tanto, los generalizan (como los planos afines , proyectivos y de Möbius ), pero 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 sólo 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 formal y terminología.

Una estructura de incidencia es una tripleta ( $P, L, I$ ) donde $P$ es un conjunto cuyos elementos se llaman puntos , $L$ es un conjunto distinto cuyos elementos se llaman líneas y $I \subseteq P \times 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$ "se encuentra 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$ incide con $l$ " o que " $l$ incide con $p$ " y utiliza la notación $p$ $I$ $l$ como sinónimo de $($ $p$ $,$ $l$ $)$ $\in$ I. . ^[2]

En algunas situaciones comunes, $L$ puede ser un conjunto de subconjuntos de $P,$ en cuyo caso la incidencia $I$ será contención ( $p I l$ si y solo si $p$ es miembro de $l$ ). Las estructuras de incidencia de este tipo se denominan 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\}.

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.

Graficos

Cualquier gráfico (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. 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 e incidencia significa que un vértice es un punto final de un borde.

Espacios lineales

Las estructuras de incidencia rara vez se estudian en toda su 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:

Dos puntos distintos cualesquiera inciden como máximo en una línea común, y
Cada línea incide con al menos dos puntos.

Si el primer axioma anterior se reemplaza por el más fuerte:

Dos puntos distintos cualesquiera inciden exactamente en una línea común,

la estructura de incidencia se llama espacio lineal . ^[4]^[5]

Redes

Un ejemplo más especializado es $k$ -net . Esta 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 diferentes clases tienen exactamente un punto común, y cada punto pertenece exactamente a una línea de 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)

estructura dual

C^{*}=(L,P,I^{*})

I *

relación inversa

I

C^{**}=C

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

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

Otra terminología

El concepto de estructura de incidencia es muy simple y ha surgido en varias disciplinas, cada una de las cuales introduce 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 hipergrafos y en términos de teoría de diseño se denominan diseños de bloques . También se les conoce como sistema de conjuntos o familia de conjuntos en un contexto general.

Hipergrafos

Cada hipergrafo o sistema de conjuntos puede considerarse como una estructura de incidencia en la que el conjunto universal desempeña el papel de "puntos", la familia de conjuntos correspondiente desempeña el papel de "líneas" y la relación de incidencia es la pertenencia al conjunto " $\in$ ". Por el contrario, cada estructura de incidencia se puede ver 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 bloques para 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, se dice que el diseño de bloques es regular . El dual de un diseño uniforme es un diseño regular y viceversa.

Ejemplo: avión Fano

Considere el diseño de bloque/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 nim . Alternativamente, cada número, cuando se escribe en binario , se puede identificar 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 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 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. ^[a] Una matriz de incidencia no está determinada de forma única ya que depende del ordenamiento 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}}

Una 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}}

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

Una estructura de incidencia es autodual si existe un ordenamiento de los puntos y líneas de modo 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 puntos ordenados $A, B, C, D, G, F, E$ y líneas ordenadas $l, p, n, s, r, m, q$ , el plano de Fano tiene la incidencia matriz:

{\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}}.

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 teniendo algún medio visual para unir los puntos para que correspondan a líneas. ^[6] Los puntos se pueden colocar de cualquier manera, no hay restricciones en cuanto a distancias entre puntos ni relaciones 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 recta no está definido. Compárese esto con la geometría ordenada , que sí tiene una noción de intermediación. Se pueden hacer las mismas afirmaciones sobre las representaciones de las líneas. En particular, no es necesario representar las líneas mediante "segmentos de línea recta" (véanse los ejemplos 1, 3 y 4 anteriores). Al igual que 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 significado en términos de la estructura de incidencia; es sólo un accidente de la representación. Estas cifras de incidencia pueden a veces 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 representación por puntos y líneas (rectas). Las estructuras que pueden serlo se denominan realizables . Si no se menciona ningún espacio ambiental, se supone 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í en el plano complejo . ^[7] Por otro lado, los ejemplos 2 y 5 anteriores son realizables y las cifras de incidencia allí dadas lo demuestran. Steinitz (1894) ^[8] ha demostrado que $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 una sola 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 gráfico bipartito llamado gráfico de Levi o gráfico de incidencia de la estructura. Como cualquier gráfico bipartito tiene dos colores, al gráfico de Levi se le puede dar una coloración de vértices en blanco y negro , donde los vértices negros corresponden a puntos y los vértices blancos corresponden a líneas de $C.$ Los bordes de este gráfico corresponden a las banderas (pares de puntos/líneas de incidente) de la estructura de incidencia. El gráfico de Levi original era el gráfico de incidencia del cuadrilátero generalizado de orden dos (ejemplo 3 anterior), ^{[10] pero}HSM Coxeter ^[11] amplió el término para referirse a un gráfico de incidencia de cualquier estructura de incidencia. ^[12]

Ejemplos de gráficos de Levi

La gráfica de Levi del plano de Fano es la gráfica de Heawood . Dado que el gráfico de Heawood es conexo y transitivo por 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 blancos y negros. Esto, a su vez, implica que el plano Fano es autodual.

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 el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj) del diagrama intercambia los vértices azul y rojo y asigna bordes a bordes. Es decir, existe un automorfismo de intercambio de colores en este gráfico. 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 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$ . ^[12] Formalmente estos 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 gráfico de Levi para estas estructuras se define como un gráfico multipartito con los vértices correspondientes a cada tipo coloreados del mismo modo.

Ver 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
^ ab 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, pag. 5
^ ab Beth, Jungnickel y Lenz 1986, pág. 17
^ Pisanski y Servatius 2013, pag. 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 autoduales y gráficos regulares", Boletín de la Sociedad Matemática Estadounidense , 56 : 413–455, doi : 10.1090/s0002-9904-1950-09407-5
^ ab Pisanski y Servatius 2013, p. 158

Bibliografía

Beth, Tomás; 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 Ratón: 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, SEÑOR 0233275
Moorhouse, G. Eric (2014). "Geometría de incidencia" (PDF) - a través de John Baez de 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