Estructura de incidencia

Ejemplos de estructuras de incidencia:
Ejemplo 1: puntos y rectas del plano euclidiano (arriba)
Ejemplo 2: puntos y circunferencias (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. Considérense los puntos y las rectas de un plano como los dos tipos de objetos, e ignórense todas las propiedades de esta geometría, excepto el criterio de relación, es decir, establecer qué puntos están en qué rectas para todos los puntos y rectas definidos. Lo que queda es la estructura de incidencia en un plano euclídeo.

Las estructuras de incidencia se consideran con mayor frecuencia en el contexto geométrico, donde se trabaja sobre planos (como el plano afín, el plano proyectivo o el plano de Möbius), pero el concepto es muy amplio y no se fija exclusivamente en las configuraciones geométricas. Incluso en un entorno geométrico, las estructuras de incidencia no se limitan solo a puntos y rectas; y se pueden utilizar objetos de dimensiones superiores (planos, sólidos, espacios Plantilla:Mvar-dimensionales, o superficies cónicas). El estudio de estructuras finitas a veces se denomina geometría finita.

Definición formal y terminología

Una estructura de incidencia es una tripleta (Plantilla:Math) donde Plantilla:Mvar es un conjunto cuyos elementos se llaman puntos, Plantilla:Mvar es un conjunto distinto cuyos elementos se llaman líneas y Plantilla:Math es la relación de incidencia. Los elementos de Plantilla:Mvar se llaman banderas. Si (Plantilla:Math) está en Plantilla:Mvar, entonces se puede decir que el punto Plantilla:Mvar "se encuentra en" la línea Plantilla:Mvar o que la línea Plantilla:Mvar "pasa por" el punto Plantilla:Mvar. Una terminología más "simétrica", para reflejar la naturaleza simétrica de esta relación, es que "Plantilla:Mvar es incidente con Plantilla:Mvar" o que "Plantilla:Mvar es incidente con Plantilla:Mvar" y se utiliza la notación Plantilla:Math con el mismo significado que Plantilla:Math.

En algunas situaciones comunes, Plantilla:Mvar puede ser un conjunto de subconjuntos de Plantilla:Mvar, en cuyo caso la incidencia Plantilla:Mvar será la condición de estar contenido (Plantilla:Math si y solo si Plantilla:Mvar es miembro de Plantilla:Mvar). Las estructuras de incidencia de este tipo se denominan "teóricas de conjuntos". Este no es siempre el caso, por ejemplo, si Plantilla:Mvar es un conjunto de vectores y Plantilla:Mvar un conjunto de matrices cuadradas, se puede definir

$I=\{(v,M):\overrightarrow{v}\text{es un vector propio de la matriz }M\}$

lo que demuestra que, si bien se utiliza el lenguaje geométrico de puntos y rectas, los tipos de objetos no necesitan ser estos objetos geométricos.

Ejemplos

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).

Grafos

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. Para estos ejemplos, los vértices del grafo forman el conjunto de puntos, los vínculos del grafo forman el conjunto de líneas, e incidencia significa que un vértice es un punto final de un vínculo.

Espacios lineales

Las estructuras de incidencia rara vez se estudian en toda su generalidad, y es típico centrarse en aquellas que satisfacen algunos axiomas adicionales. Por ejemplo, un espacio lineal parcial es una estructura de incidencia que satisface:

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

Si el primer axioma anterior se reemplaza por la condición más fuerte:

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

la estructura de incidencia resultante se denomina espacio lineal.

Redes

Un ejemplo más especializado es una Plantilla:Mvar-red, una estructura de incidencia en la que las líneas se clasifican en Plantilla:Mvar 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 una Plantilla:Mvar-red es el conjunto de puntos de un plano afín junto con Plantilla:Mvar clases de rectas afines paralelas.

Estructura dual

Si se intercambia el papel de "puntos" y "líneas" en

$C=(P,L,I)$

se obtien una estructura dual,

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

donde I^∗ es la relación inversa de Plantilla:Mvar. De la definición se desprende inmediatamente que:

$C^{**}=C$

versión abstracta de la dualidad proyectiva.

Una estructura Plantilla:Mvar que es un isomorfismo con respecto a su dual Plantilla:Math, se denomina autodual. Por ejemplo, el plano de Fano es una estructura de incidencia autodual.

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 cuestiones que normalmente se hacen sobre estas estructuras. Las estructuras de incidencia utilizan una terminología geométrica, pero en términos de la teoría de grafos se denominan hipergrafos y en términos de la teoría de diseño se denominan diseño de bloque. También se conocen como "sistema de conjuntos" o familia de conjuntos en un contexto general.

Hipergrafos

Siete puntos son los elementos de siete líneas en el plano de Fano

Cada hipergrafo o sistema de conjuntos se puede considerar 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 a un conjunto "Plantilla:Math". Por el contrario, cada estructura de incidencia se puede ver como un hipergrafo identificando las líneas con los conjuntos de puntos que inciden en ellas.

Diseños de bloque

Plantilla:AP Un diseño de bloque (en general) es un conjunto Plantilla:Mvar junto con una [[Familia de conjuntos|familia Plantilla:Mvar de subconjuntos]] de Plantilla:Mvar (se permiten subconjuntos repetidos). Normalmente se requiere un diseño de bloque para satisfacer condiciones de regularidad numérica. Como estructura de incidencia, Plantilla:Mvar es el conjunto de puntos y Plantilla:Mvar es el conjunto de líneas, generalmente llamados bloques en este contexto (los bloques repetidos deben tener nombres distintos, por lo que Plantilla:Mvar es en realidad un conjunto y no un conjunto múltiple). Si todos los subconjuntos en Plantilla:Mvar tienen el mismo tamaño, el diseño del bloque se llama "uniforme". Si cada elemento de Plantilla:Mvar aparece en el mismo número de subconjuntos, se dice que el diseño del bloque es "regular". El dual de un diseño uniforme es un diseño regular y viceversa.

Ejemplo: plano de Fano

Considérese el diseño de bloque/hipergrafo dado por

$\begin{array}{cc}P& =\{1,2,3,4,5,6,7\},\\ L& =\left\{\begin{array}{cc}\{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{array}$

Esta estructura 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 que constan de tres puntos cuyas etiquetas suman cero usando nimber. Alternativamente, cada número, cuando se escribe en el sistema 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; lo que en este caso equivale a que su suma vectorial sea el vector cero.

Representaciones

Las estructuras de incidencia pueden representarse de muchas maneras. Si los conjuntos Plantilla:Mvar y Plantilla:Mvar 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 booleana que tiene sus filas indexadas por los puntos Plantilla:Mvar y las columnas indexadas por las líneas Plantilla:Math donde la entrada Plantilla:Mvar-ésima es 1 si es Plantilla:Math y 0 en caso contrario.Plantilla:Efn Una matriz de incidencia no está determinada de forma única, ya que depende del orden arbitrario de los puntos y las líneas.

La estructura de incidencia no uniforme que se muestra arriba (ejemplo número 2) viene dada por:

$\begin{array}{cc}P& =\{A,B,C,D,E,P\}\\ L& =\left\{\begin{array}{cc}l=\{C,P,E\},& m=\{P\},\\ n=\{P,D\},& o=\{P,A\},\\ p=\{A,B\},& q=\{P,B\}\end{array}\right\}\end{array}$

La matriz de incidencia para esta estructura es:

$\left(\begin{array}{cccccc}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{array}\right)$

que coincide con la tabla de incidencia:

Plantilla:Math	Plantilla:Mvar	Plantilla:Mvar	Plantilla:Mvar	Plantilla:Mvar	Plantilla:Mvar	Plantilla:Mvar
Plantilla:Mvar	0	0	0	1	1	0
Plantilla:Mvar	0	0	0	0	1	1
Plantilla:Mvar	1	0	0	0	0	0
Plantilla:Mvar	0	0	1	0	0	0
Plantilla:Mvar	1	0	0	0	0	0
Plantilla:Mvar	1	1	1	1	0	1

Si una estructura de incidencia Plantilla:Mvar tiene una matriz de incidencia Plantilla:Mvar, entonces la estructura dual Plantilla:Math tiene la matriz transpuesta Plantilla:Mvar^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 de las líneas de modo que la matriz de incidencia construida con ese ordenamiento sea una matriz simétrica.

Con las etiquetas como se muestra en el ejemplo número 1 anterior y con los puntos en el orden Plantilla:Math y las líneas en el orden Plantilla:Math, el plano de Fano tiene la matriz de incidencia:

$\left(\begin{array}{ccccccc}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{array}\right).$

Dado que se trata de una matriz simétrica, el plano de Fano es una estructura de incidencia autodual.

Representaciones gráficas

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. 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 línea no está definido. Compárese esto con la geometría ordenada, donde sí existe el concepto de posición intermedia. Se pueden hacer las mismas afirmaciones sobre las representaciones de las líneas. En particular, no es necesario representalas mediante "segmentos de recta" (véanse los ejemplos 1, 3 y 4 anteriores). Al igual que con la representación pictórica de grafos, 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 solo un accidente de la representación. Estas figuras de incidencia pueden a veces parecerse a grafos, pero no lo son a menos que la estructura de incidencia reúna las propiedades de un grafo.

Factibilidad

Las estructuras de incidencia se pueden modelar mediante puntos y curvas en un plano 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 serlo se denominan "factibles" o "realizables". Si no se menciona ningún espacio de contorno, se supone el plano euclídeo. El plano de Fano (ejemplo 1 anterior) no es factible, ya que necesita al menos una curva. La configuración de Möbius-Kantor (ejemplo 4 anterior) no es realizable en el plano euclídeo, pero sí en el plano complejo. Por otra parte, los ejemplos 2 y 5 anteriores son realizables y las figuras de incidencia dadas lo demuestran. Steinitz (1894) demostró que las Plantilla:Nowrap (estructuras de incidencia con Plantilla:Mvar puntos y Plantilla:Mvar rectas, tres puntos por recta y tres rectas que pasan por cada punto) son realizables o requieren el uso de una sola línea curva en sus representaciones. El plano de Fano es el único ejemplo del tipo (Plantilla:Math) y la configuración de Möbius-Kantor es la única del tipo (Plantilla:Math).

Grafo de incidencia (grafo de Levi)

Grafo de Heawood con etiquetas

Cada estructura de incidencia Plantilla:Mvar corresponde a un grafo bipartito llamado grafo de Levi o grafo de incidencia de la estructura. Como cualquier grafo bipartito tiene dos colores, al grafo 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 Plantilla:Mvar. Los vínculos de este grafo corresponden a las banderas (pares de puntos/líneas incidentes) de la estructura de incidencia. El grafo de Levi original era el grafo de incidencia del cuadrángulo generalizado de orden dos (ejemplo 3 anterior), pero Coxeter ha ampliado el término para referirse a un grafo de incidencia de cualquier estructura de incidencia.

Grafo de Levi de la configuración de Möbius–Kantor (#4)

Ejemplos de grafos de Levi

El grafo de Levi del plano de Fano es el grafo de Heawood. Dado que el grafo de Heawood es conexo e isogonal, existe un automorfismo (como el definido por una reflexión sobre el eje vertical en la figura del grafo 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 grafo de Levi de la configuración de Möbius-Kantor (ejemplo 4 de arriba) ilustra que una rotación del diagrama de Plantilla:Math alrededor del centro (ya sea en el sentido de las agujas del reloj o en el sentido contrario) intercambia los vértices azules y rojos y hace corresponder vínculos con vínculos. 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.Plantilla:Clear

Generalización

Es posible generalizar la noción de estructura de incidencia para incluir más de dos tipos de objetos. Una estructura con Plantilla:Mvar tipos de objetos se denomina estructura de incidencia de rango Plantilla:Mvar o geometría de rango Plantilla:Mvar. Formalmente, se definen como:

Plantilla:Math-tuplas Plantilla:Math con Plantilla:Math e $I\subseteq \bigcup _{i<j}{P}_i\times P_j.$

Estas estructuras se definen como grafos multipartitos, y se suelen representar con los vértices correspondientes a cada tipo del mismo color.

Temas relacionados

Estructuras de incidencia

Representación   • Matriz de incidencia • Grafo de incidencia

Campos   • Combinatoria  (Diseño de bloques · Sistema de Steiner) • Geometría  (Incidencia · Plano proyectivo) • Teoría de grafos  (Hipergrafo) • Estadística  (Bloqueado)

Configuración   • Cuadrángulo completo • Plano de Fano • Configuración de Möbius-Kantor • Configuración de Papus • Configuración de Hesse • Configuración de Desargues • Configuración de Reye • Seis doble de Schläfli • Configuración de Cremona-Richmond • Configuración de Kummer • Configuración de Grünbaum-Rigby • Configuración de Klein • Dualidad

Teoremas   • Teorema de Sylvester-Gallai • Teorema de De Bruijn-Erdos • Teorema de Szemerédi-Trotter • Teorema de Beck • Teorema de Bruck-Ryser-Chowla

Aplicaciones   • Diseño experimental • Problema de las colegialas de Kirkman

Véase también

• Incidencia
• Geometría de incidencia
• Configuración proyectiva
• Politopo abstracto

Bibliografía

• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Cite web
• Plantilla:Citation

Lecturas adicionales

• CRC Press (2000). Handbook of discrete and combinatorial mathematics, (Chapter 12.2), Plantilla:ISBN
• Harold L. Dorwart (1966) The Geometry of Incidence, Prentice Hall