Conjunto de bloqueo

Concepto en geometría proyectiva

En geometría , específicamente en geometría proyectiva , un conjunto bloqueador es un conjunto de puntos en un plano proyectivo que cada línea interseca y que no contiene una línea entera. El concepto se puede generalizar de varias maneras. En lugar de hablar de puntos y líneas, se podría tratar con subespacios n -dimensionales y subespacios m -dimensionales, o incluso de manera más general, objetos de tipo 1 y objetos de tipo 2 cuando algún concepto de intersección tenga sentido para estos objetos. Una segunda forma de generalizar sería pasar a entornos más abstractos que la geometría proyectiva. Se puede definir un conjunto bloqueador de un hipergrafo como un conjunto que se encuentra con todos los bordes del hipergrafo.

Definición

En un plano proyectivo finito π de orden n , un conjunto bloqueante es un conjunto de puntos de π que cada línea interseca y que no contiene ninguna línea en su totalidad. Según esta definición, si B es un conjunto bloqueante, entonces el conjunto complementario de puntos, π\ B es también un conjunto bloqueante. Un conjunto bloqueante B es mínimo si la eliminación de cualquier punto de B deja un conjunto que no es un conjunto bloqueante. Un conjunto bloqueante de tamaño más pequeño se denomina comité . Cada comité es un conjunto bloqueante mínimo, pero no todos los conjuntos bloqueantes mínimos son comités. Los conjuntos bloqueantes existen en todos los planos proyectivos excepto en el plano proyectivo más pequeño de orden 2, el plano de Fano . ^[1]

A veces resulta útil descartar la condición de que un conjunto bloqueante no contenga una línea. Según esta definición ampliada, y puesto que en un plano proyectivo cada par de líneas se cruza, cada línea sería un conjunto bloqueante. Los conjuntos bloqueantes que contuvieran líneas se denominarían conjuntos bloqueantes triviales en este contexto.

Ejemplos

En cualquier plano proyectivo de orden n (cada recta contiene n + 1 puntos), los puntos de las rectas que forman un triángulo sin los vértices del triángulo (3( n - 1) puntos) forman un conjunto de bloqueo mínimo (si n = 2 este conjunto de bloqueo es trivial) que en general no es un comité.

Otra construcción general en un plano proyectivo arbitrario de orden n es tomar todos los puntos excepto uno, digamos P , en una línea dada y luego un punto en cada una de las otras líneas que pasan por P , asegurándose de que estos puntos no sean todos colineales (esta última condición no se puede satisfacer si n = 2). Esto produce un conjunto de bloqueo mínimo de tamaño 2 n .

Un triángulo proyectivo β de lado m en PG(2, q ) consta de 3( m - 1) puntos, m en cada lado de un triángulo, tales que los vértices A , B y C del triángulo están en β, y se satisface la siguiente condición: si el punto P en la línea AB y el punto Q en la línea BC están ambos en β, entonces el punto de intersección de PQ y AC está en β.

Una tríada proyectiva δ de lado m es un conjunto de 3 m - 2 puntos, m de los cuales se encuentran en cada una de tres líneas concurrentes tales que el punto de concurrencia C está en δ y se satisface la siguiente condición: si un punto P en una de las líneas y un punto Q en otra línea están en δ, entonces el punto de intersección de PQ con la tercera línea está en δ.

Teorema : En PG(2, q ) con q impar, existe un triángulo proyectivo de lado ( q + 3)/2 que es un conjunto bloqueante de tamaño 3( q + 1)/2. ^[2]

Utilizando coordenadas homogéneas , sean los vértices del triángulo A = (1,0,0), B = (0,1,0) y C = (0,0,1). Los puntos, distintos de los vértices, del lado AB tienen coordenadas de la forma (- c , 1, 0), los del lado BC tienen coordenadas (0,1, a ) y los del lado AC tienen coordenadas (1,0, b ) donde a , b y c son elementos del cuerpo finito GF( q ). Tres puntos, uno en cada uno de estos lados, son colineales si y solo si a = bc . Al elegir todos los puntos donde a , b y c son cuadrados distintos de cero de GF( q ), se satisface la condición de la definición de un triángulo proyectivo.

Teorema : En PG(2, q ) con q par, existe una tríada proyectiva de lado ( q + 2)/2 que es un conjunto bloqueante de tamaño (3 q + 2)/2. ^[3]

La construcción es similar a la anterior, pero como el cuerpo es de característica 2 , los cuadrados y no cuadrados deben reemplazarse por elementos de traza absoluta 0 y traza absoluta 1. Específicamente, sea C = (0,0,1). Los puntos en la línea X = 0 tienen coordenadas de la forma (0,1, a ), y aquellos en la línea Y = 0 tienen coordenadas de la forma (1,0, b ). Los puntos de la línea X = Y tienen coordenadas que pueden escribirse como (1,1, c ). Tres puntos, uno de cada una de estas líneas, son colineales si y solo si a = b + c . Al seleccionar todos los puntos en estas líneas donde a , b y c son los elementos del cuerpo con traza absoluta 0, se satisface la condición en la definición de una tríada proyectiva.

Teorema : En PG(2, p ), con p primo, existe una tríada proyectiva de lado ( p + 1)/2 que es un conjunto bloqueante de tamaño (3 p + 1)/2. ^[4]

Tamaño

Normalmente se buscan conjuntos de bloqueo pequeños. El tamaño mínimo de un conjunto de bloqueo se denomina . ${\displaystyle H}$ ${\displaystyle \tau (H)}$

En el plano proyectivo desarguesiano de orden q , PG(2, q ), el tamaño de un conjunto de bloqueo B está acotado: ^[5]

${\displaystyle q+{\sqrt {q}}+1\leq |B|\leq q^{2}-{\sqrt {q}}.}$

Cuando q es un cuadrado, el límite inferior se logra mediante cualquier subplano de Baer y el límite superior proviene del complemento de un subplano de Baer.

Se puede demostrar un resultado más general, ^[6]

Cualquier conjunto bloqueante en un plano proyectivo π de orden n tiene al menos puntos. Además, si se cumple este límite inferior, entonces n es necesariamente un cuadrado y el conjunto bloqueante consiste en los puntos en algún subplano de Baer de π. ${\displaystyle n+{\sqrt {n}}+1}$

Un límite superior para el tamaño de un conjunto de bloqueo mínimo tiene el mismo sabor, ^[7]

Cualquier conjunto bloqueante mínimo en un plano proyectivo π de orden n tiene como máximo puntos. Además, si se alcanza este límite superior, entonces n es necesariamente un cuadrado y el conjunto bloqueante consiste en los puntos de algún unital inserto en π. ${\displaystyle n{\sqrt {n}}+1}$

Cuando n no es un cuadrado, se puede decir menos acerca de los conjuntos bloqueantes no triviales de menor tamaño. Un resultado bien conocido debido a Aart Blokhuis es: ^[4]

Teorema : Un conjunto bloqueante no trivial en PG(2, p ), p un primo, tiene un tamaño al menos 3( p + 1)/2.

En estos planos existe un triángulo proyectivo que cumple este límite.

Historia

Los conjuntos de bloqueo se originaron ^[8] en el contexto de la teoría de juegos económicos en un artículo de 1956 de Moses Richardson. ^[9] Los jugadores se identificaban con puntos en un plano proyectivo finito y las coaliciones ganadoras mínimas eran líneas. Una coalición de bloqueo se definió como un conjunto de puntos que no contenían ninguna línea pero que intersecaban todas las líneas. En 1958, JR Isbell ^[10] estudió estos juegos desde un punto de vista no geométrico. Jane W. DiPaola estudió las coaliciones de bloqueo mínimas en todos los planos proyectivos de orden en 1969. ^[11] ${\displaystyle \leq 9}$

En hipergrafos

Sea un hipergrafo, de modo que es un conjunto de elementos, y es una colección de subconjuntos de , llamados (hiper)aristas. Un conjunto de bloqueo de es un subconjunto de que tiene una intersección no vacía con cada hiperarista. ${\displaystyle H=(X,E)}$ ${\displaystyle X}$ ${\displaystyle E}$ ${\displaystyle X}$ ${\displaystyle H}$ ${\displaystyle S}$ ${\displaystyle X}$

Los conjuntos de bloqueo a veces también se denominan " conjuntos de impacto " o " cobertura de vértices ". También se utiliza el término " transversal ", pero en algunos contextos una transversal de es un subconjunto de que se encuentra con cada hiperarista en exactamente un punto. ${\displaystyle H}$ ${\displaystyle T}$ ${\displaystyle X}$

Una " bicoloración " de es una partición de en dos subconjuntos (clases de color) de modo que ninguna arista sea monocromática, es decir, ninguna arista esté contenida completamente dentro de o dentro de . Ahora bien, tanto y son conjuntos bloqueantes. ${\displaystyle H}$ ${\displaystyle \{C,D\}}$ ${\displaystyle X}$ ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle C}$ ${\displaystyle D}$

Arcos k completos

En un plano proyectivo, un k -arco completo es un conjunto de k puntos, no tres colineales , que no se puede extender a un arco más grande (por lo tanto, cada punto que no está en el arco está en una línea secante del arco, una línea que se encuentra con el arco en dos puntos).

Teorema : Sea K un k -arco completo en Π = PG(2, q ) con k < q + 2. El dual en Π del conjunto de líneas secantes de K es un conjunto bloqueante, B , de tamaño k ( k - 1)/2. ^[12]

Bloqueos de conjuntos de Rédei

En cualquier plano proyectivo de orden q , para cualquier conjunto bloqueante no trivial B (con b = | B |, el tamaño del conjunto bloqueante) considérese una línea que corta a B en n puntos. Puesto que ninguna línea está contenida en B , debe haber un punto, P , en esta línea que no esté en B . Las q otras líneas, aunque P, deben contener cada una al menos un punto de B para estar bloqueadas. Por lo tanto, si para alguna línea se cumple la igualdad en esta relación, el conjunto bloqueante se denomina conjunto bloqueante de tipo Rédei y la línea una línea Rédei del conjunto bloqueante (nótese que n será el mayor número de puntos colineales en B ). ^[13] No todos los conjuntos bloqueantes son de tipo Rédei, pero muchos de los más pequeños sí lo son. Estos conjuntos reciben su nombre de László Rédei , cuya monografía sobre polinomios lacunares sobre cuerpos finitos influyó en el estudio de estos conjuntos. ^[14] ${\displaystyle b\geq n+q.}$

Conjuntos de bloqueo afines

Un conjunto de puntos en el espacio afín desarguesiano finito que interseca cada hiperplano de manera no trivial, es decir, cada hiperplano incide con algún punto del conjunto, se denomina conjunto bloqueador afín. Identifique el espacio con fijando un sistema de coordenadas. Entonces se demuestra fácilmente que el conjunto de puntos que se encuentran en los ejes de coordenadas forman un conjunto bloqueador de tamaño . Jean Doyen conjeturó en una conferencia de Oberwolfach de 1976 que este es el menor tamaño posible de un conjunto bloqueador. Esto fue demostrado por RE Jamison en 1977, ^[15] e independientemente por AE Brouwer , A. Schrijver en 1978 ^[16] utilizando el llamado método polinomial. Jamison demostró el siguiente resultado de cobertura general del cual se deduce el límite de los conjuntos bloqueadores afines utilizando dualidad: ${\displaystyle AG(n,q)}$ ${\displaystyle \mathbb {F} _{q}^{n}}$ ${\displaystyle 1+n(q-1)}$

Sea un espacio vectorial dimensional sobre . Entonces, la cantidad de clases laterales dimensionales requeridas para cubrir todos los vectores excepto el vector cero es al menos . Además, este límite es preciso. ${\displaystyle V}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle k}$ ${\displaystyle q^{n-k}-1+k(q-1)}$

Notas

1. Hirschfeld 1979, pág. 366
2. Hirschfeld 1979, pág. 376, Teorema 13.4.1
3. Hirschfeld 1979, pág. 377, Teorema 13.4.2
4. Blokhuis, Aart (1994), "Sobre el tamaño de un conjunto de bloqueo en PG(2,p)", Combinatorica , 14 : 111–114, doi :10.1007/bf01305953
5. Hirschfeld 1979, pág. 376, Teorema 13.3.3
6. Barwick y Ebert 2008, pág. 30, Teorema 2.15
7. Barwick y Ebert 2008, pág. 30, Teorema 2.16
8. Holder 2001, pág. 45
9. Richardson, Moses (1956), "Sobre juegos proyectivos finitos", Actas de la American Mathematical Society , 7 (3): 458–465, doi : 10.2307/2032754 , JSTOR  2032754
10. Isbell, JR (1958), "Una clase de juegos simples", Duke Mathematical Journal , 25 (3): 425–436, doi :10.1215/s0012-7094-58-02537-7
11. DiPaola, Jane W. (1969), "Sobre coaliciones de bloqueo mínimo en juegos de planos proyectivos pequeños", SIAM Journal on Applied Mathematics , 17 (2): 378–392, doi :10.1137/0117036
12. Hirschfeld 1979, pág. 366, Teorema 13.1.2
13. Szőnyi, Tamás (1997), "Conjuntos de bloqueo en planos afines y proyectivos desarguesianos", Campos finitos y sus aplicaciones , 3 (3): 187–202, doi : 10.1006/ffta.1996.0176
14. Szőnyi, Tamás (1999), "En torno al teorema de Rédei", Matemáticas discretas , 208/209: 557–575, doi : 10.1016/s0012-365x(99)00097-7
15. Jamison, Robert E. (1977), "Cobertura de campos finitos con clases laterales de subespacios", Journal of Combinatorial Theory , Serie A, 22 (3): 253–266, doi : 10.1016/0097-3165(77)90001-2
16. Brouwer, Andries; Schrijver, Alexander (1978), "El número de bloqueo de un espacio afín", Journal of Combinatorial Theory , Serie A, 24 (2): 251–253, doi : 10.1016/0097-3165(78)90013-4

Referencias

• Barwick, Susan; Ebert, Gary (2008), Unitales en planos proyectivos , Nueva York: Springer, doi :10.1007/978-0-387-76366-8, ISBN 978-0-387-76364-4, ISSN  1439-7382
• C. Berge , Gráficos e hipergráficos, Holanda Septentrional, Amsterdam, 1973. (Define .) ${\displaystyle \tau (H)}$
• P. Duchet, Hipergrafos, Capítulo 7 en: Handbook of Combinatorics, Holanda Septentrional, Amsterdam, 1995.
• Hirschfeld, JWP (1979), Geometrías proyectivas sobre campos finitos , Oxford: Oxford University Press, ISBN 978-0-19-853526-3
• Holder, Leanne D. (2001), Bloqueo de conjuntos de cónicas, tesis doctoral , Universidad de Colorado en Denver
• De Beule, enero; Storme, Leo (2011), Temas de investigación actuales en geometría de Galois, Nova Science Publishers, ISBN 978-1-61209-523-3, archivado desde el original el 29 de enero de 2016 , consultado el 23 de enero de 2016