Diferencia entre revisiones de «Estructura de incidencia»

Contenido eliminado Contenido añadido

En renglón

Revisión del 11:44 6 oct 2023

Ejemplos de estructuras de incidencia:
Ejemplo 1: puntos y rectas 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 point y los line de Plano (geometría) como los dos tipos de objetos e ignore todas las propiedades de esta geometría, excepto relation, 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, se generalizan (como affine, projective y Möbius plane), pero el concepto es muy amplio y no se limita a configuraciones geométricas. 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 (plane, solid, espacios $n$ , conics, 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 el incidence relation . 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 symmetric 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$ .^[2]

En algunas situaciones comunes, $L$ puede ser un conjunto de subconjuntos de $P$ , en cuyo caso la incidencia $I$ será la contención ( $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 square matrices, podemos definir $I=\{(v,M):{\vec {v}}{\text{is an eigenvector of matrix }}M\}.$ también muestra que si bien se utiliza el lenguaje geométrico de puntos y líneas, los tipos de objetos no necesitan ser estos objetos geométricos.

Ejemplos

Artículo principal: Geometría de incidencia

Some examples of incidence structures

1. Plano de Fano

A non-uniform incidence structure — 2. Non-uniform structure

2. Non-uniform structure

Generalized Quadrangle called the Doily — 3. Generalized quadrangle

3. Generalized quadrangle

8 point and 8 line configuration — 4. Möbius–Kantor configuration

4. Möbius–Kantor configuration

Configuration of Pappus theorem — 5. Pappus configuration

5. Pappus configuration

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 graph (que no tiene por qué ser simple; se permiten loops 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 partial linear space es una estructura de incidencia que satisface:

Dos puntos distintos cualesquiera inciden con como máximo 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:

Any two distinct points are incident with exactly one common line,

la estructura de incidencia se denomina linear space.^[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 una red $k$ es el conjunto de puntos de una affine plane junto con clases paralelas de líneas afines $k$ .

Estructura dual

Si intercambiamos el papel de "puntos" y "líneas" en $C=(P,L,I)$ estructura dual, $C^{*}=(L,P,I^{*})$ 'I^∗}} es el relación inversa de $I$ . De la definición se desprende inmediatamente que: $C^{**}=C$ versión abstracta de projective duality.^[2]

Una estructura $C$ que es isomorfismo con respecto a su dual $C *$ se denomina 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 graph theoretic se denominan hipergrafo y en términos teóricos del diseño se denominan block design. También se les conoce como "sistema de conjuntos" o family of sets en un contexto general.

Hipergrafos

Artículo principal: Hipergrafo

Seven points are elements of seven lines in the Plano de Fano

Cada hipergrafo o set system se puede considerar como una incidencia. estructura en la que el conjunto universal desempeña el papel de "puntos", el family of sets correspondiente desempeña el papel de "líneas" y la relación de incidencia es set membership " $\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

Artículo principal: Block design

Un diseño de bloque (general) es un conjunto $X$ junto con un family $F$ of subsets 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 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: avión Fano

Considere el diseño de bloque/hipergrafo dado por: La estructura ${\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}}$ ce se llama 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 nimber. Alternativamente, cada número, cuando se escribe en binary, se puede identificar con un vector distinto de cero de longitud tres sobre binary field. Tres vectores que generan un subspace 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

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: La matriz ${\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}}$ ce 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}}$ lleva a 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 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 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}}.$ a matriz simétrica, el plano de Fano es una estructura de incidencia autodual.

Representaciones pictóricas del

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 recta no está definido. Compárese esto con 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 graphs, 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 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 Plano (geometría) 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.^[8] Por otra parte, los ejemplos 2 y 5 anteriores son realizables y las cifras de incidencia allí dadas lo demuestran. Steinitz (1894)^[9] ha demostrado que $n 3$ -configurations (estructuras de incidencia con puntos $n$ y líneas $n$ , 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.^[10] 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 Levi graph 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 un vertex coloring 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 generalized quadrangle de orden dos (ejemplo 3 anterior),^[11], pero Harold Scott MacDonald Coxeter^[12] ha ampliado el término para referirse a un gráfico de incidencia.

de cualquier estructura de incidencia.^[13]

Levi graph of the Möbius–Kantor configuration (#4)

Ejemplos de gráficos de Levi

El gráfico de Levi del Plano de Fano es el Grafo de Heawood. Dado que el gráfico de Heawood es connected y figura isogonal, 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 $Plantilla:Pi /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 mapea los bordes. a los 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 tipos de objetos $k$ se denomina estructura de incidencia de rango $k$ o geometría de rango $k$ .^[13] 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}.$ ph para estas estructuras se define como multipartite graph con los vértices correspondientes a cada tipo con el mismo color.

Véase también

Notas

Referencias

↑ Colbourn y Dinitz, 2007
↑ ^a ^b Dembowski, 1968
↑ Biliotti, Jha y Johnson, 2001
↑ The term linear space is also used to refer to vector spaces, but this will rarely cause confusion.
↑ Moorhouse, 2014
↑ The other convention of indexing the rows by lines and the columns by points is also widely used.
↑ ^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] The term linear space is also used to refer to vector spaces, but this will rarely cause confusion.

[5] Moorhouse, 2014

[6] The other convention of indexing the rows by lines and the columns by points is also widely used.

[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]

@@ Línea 168: / Línea 168: @@
 *[[Incidencia (geometría)]]
 *[[Geometría de incidencia]]
+*[[Configuración proyectiva]]
-*[[ Projective configuration]]
 *[[Politopo abstracto]]