Estructura de incidencia

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.

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)

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 $n$ -dimensionales, o superficies cónicas). 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$ es incidente con $l$ " o que " $l$ es incidente con $p$ " y se utiliza la notación $p I l$ con el mismo significado que $(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á la condición de estar contenido ( $p I l$ si y solo si $p$ es 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, se puede definir

I=\{(v,M):{\vec {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

Artículo principal: Geometría de incidencia

Algunos ejemplos de estructuras de incidencia

1. Plano de Fano

2. Estructura no uniforme

3. Cuadrángulo generalizado

4. Configuración de Möbius-Kantor

5. Configuración de Papus

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:

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

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

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

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

Redes

Un ejemplo más especializado es una $k$ -red, una estructura de incidencia en la que las líneas se clasifican 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 una $k$ -red es el conjunto de puntos de un plano afín junto con $k$ 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 $I$ . De la definición se desprende inmediatamente que:

C^{**}=C

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

Una estructura $C$ que es un isomorfismo con respecto a su dual $C *$ , 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

Artículo principal: Hipergrafo

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 " $\in$ ". 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

Artículo principal: Diseño de bloque

Un diseño de bloque (en 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 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 en $F$ tienen el mismo tamaño, el diseño del bloque se llama "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 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{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 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 $P$ y $L$ son finitos, estas representaciones pueden codificar de forma compacta toda la información relevante relativa a la estructura.

Matriz de incidencia

Artículo principal: 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 ${p i}$ y las columnas indexadas por las líneas ${l j}$ donde la entrada $ij$ -ésima es 1 si es $p i I l j$ y 0 en caso contrario.^[6] Una matriz de incidencia no está determinada 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:

{\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 coincide con la tabla de incidencia:

$I$	$l$	$m$	$n$	$o$	$p$	$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
$E$	1	0	0	0	0	0
$P$	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 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 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 $A, B, C, D, G, F, E$ y las líneas en el orden $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 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.^[7] 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.^[8] Por otra parte, los ejemplos 2 y 5 anteriores son realizables y las figuras de incidencia dadas lo demuestran. Steinitz (1894)^[9] demostró que las $n 3$ -configuraciones (estructuras de incidencia con $n$ puntos y $n$ 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.^[10] El plano de Fano es el único ejemplo del tipo ( $73$ ) y la configuración de Möbius-Kantor es la única del tipo ( $83$ ).

Grafo de incidencia (grafo de Levi)

Grafo de Heawood con etiquetas

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 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 $C$ . 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),^[11] pero Coxeter^[12] ha ampliado el término para referirse a un grafo de incidencia de cualquier estructura de incidencia.^[13]

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 $Π/4$ 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.

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, se definen como:

(k +1)

-tuplas

S = (P 1, P 2, ..., P k, I)

con

P i \cap P j = \emptyset

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

Referencias

↑ Colbourn y Dinitz, 2007
↑ ^a ^b Dembowski, 1968
↑ Biliotti, Jha y Johnson, 2001
↑ El término "espacio lineal" también se utiliza para referirse a espacios vectoriales, pero esto rara vez causará confusión.
↑ Moorhouse, 2014
↑ 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
↑ Pisanski y Servatius, 2013
↑ E. Steinitz (1894), Über die Construction der Configurationen $n 3$ , Dissertation, Breslau
↑ Gropp, Harald (1997), «Configurations and their realizations», Discrete Mathematics 174: 137-151, doi:10.1016/s0012-365x(96)00327-5 .
↑ Levi, F. W. (1942), Finite Geometrical Systems, Calcutta: University of Calcutta, MR 0006834 .
↑ Coxeter, H.S.M. (1950), «Self-dual configurations and regular graphs», Bulletin of the American Mathematical Society 56: 413-455, doi:10.1090/s0002-9904-1950-09407-5 .
↑ ^a ^b Pisanski y Servatius, 2013

Bibliografía

Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986), Design Theory, Cambridge University Press, ISBN 3-411-01675-2 .
Biliotti, Mauro; Jha, Vikram; Johnson, Norman L. (2001), Foundations of Translation Planes, Marcel Dekker, ISBN 0-8247-0609-9 .
Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd edición), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8 .
Dembowski, Peter (1968), Finite geometries, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44, Berlin, New York: Springer Science+Business Media, ISBN 3-540-61786-8, MR 0233275 .
Moorhouse, G. Eric (2014). «Incidence Geometry» – via John Baez at Universidad de California en Riverside.
Pisanski, Tomaž; Servatius, Brigitte (2013), Configurations from a Graphical Viewpoint, Springer, ISBN 978-0-8176-8363-4, doi:10.1007/978-0-8176-8364-1 .

Lecturas adicionales

CRC Press (2000). Handbook of discrete and combinatorial mathematics, (Chapter 12.2), ISBN 0-8493-0149-1
Harold L. Dorwart (1966) The Geometry of Incidence, Prentice Hall

Datos: Q367329

[1] Colbourn y Dinitz, 2007

[Demb1-2] Dembowski, 1968

[3] Biliotti, Jha y Johnson, 2001

[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

[6] La otra convención de indexar las filas por líneas y las columnas por puntos también se usa ampliamente.

[Beth17-7] Beth, Jungnickel y Lenz, 1986

[8] Pisanski y Servatius, 2013

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

[10] Gropp, Harald (1997), «Configurations and their realizations», Discrete Mathematics 174: 137-151, doi:10.1016/s0012-365x(96)00327-5 .

[11] Levi, F. W. (1942), Finite Geometrical Systems, Calcutta: University of Calcutta, MR 0006834 .

[12] Coxeter, H.S.M. (1950), «Self-dual configurations and regular graphs», Bulletin of the American Mathematical Society 56: 413-455, doi:10.1090/s0002-9904-1950-09407-5 .

[Pisanski158-13] Pisanski y Servatius, 2013

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]