Conjunto de bloqueo

En geometría , específicamente en geometría proyectiva , un conjunto bloqueante es un conjunto de puntos en un plano proyectivo que interseca todas las líneas y que no contiene una línea completa. El concepto puede generalizarse de varias maneras. En lugar de hablar de puntos y líneas, se podría trabajar con subespacios n -dimensionales y m- dimensionales, o incluso, de forma más general, con 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 adentrarse en contextos más abstractos que la geometría proyectiva. Se puede definir un conjunto bloqueante de un hipergrafo como un conjunto que interseca todas las aristas del hipergrafo.

En un plano proyectivo finito π de orden n , un conjunto bloqueante es un conjunto de puntos de π que interseca toda recta y que no contiene ninguna recta por completo. Según esta definición, si B es un conjunto bloqueante, entonces el conjunto complementario de puntos, π\ B, también es 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ínimo se llama comité . Todo 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 ]}

En ocasiones, resulta útil omitir la condición de que un conjunto bloqueante no contenga una línea. Bajo esta definición extendida, y puesto que en un plano proyectivo cada par de líneas se intersecan, cada línea sería un conjunto bloqueante. En este contexto, los conjuntos bloqueantes que contuvieran líneas se denominarían conjuntos bloqueantes triviales .

En cualquier plano proyectivo de orden n (cada línea contiene n + 1 puntos), los puntos en las líneas 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 consiste en 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, de tal manera 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 las tres líneas concurrentes, de manera 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 no nulos 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 (3q + 2)/2. ^{[ 3 ]}

La construcción es similar a la anterior, pero dado que el cuerpo es de característica 2 , los cuadrados y los 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 recta X = 0 tienen coordenadas de la forma (0,1, a ), y los puntos en la recta Y = 0 tienen coordenadas de la forma (1,0, b ). Los puntos de la recta X = Y tienen coordenadas que pueden escribirse como (1,1, c ). Tres puntos, uno de cada una de estas rectas, son colineales si y solo si a = b + c . Al seleccionar todos los puntos en estas rectas donde a , b y c son 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 un primo, existe una tríada proyectiva de lado ( p + 1)/2 que es un conjunto bloqueante de tamaño (3p + 1)/2. ^{[ 4 ]}

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

En el plano proyectivo de Desarguesian de orden q , PG(2, q ), el tamaño de un conjunto bloqueante 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 alcanza 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 de bloqueo en un plano proyectivo π de orden n tiene al menos${\displaystyle n+{\sqrt {n}}+1}$puntos. Además, si se cumple este límite inferior, entonces n es necesariamente un cuadrado y el conjunto de bloqueo consiste en los puntos en algún subplano de Baer de π.

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

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

Cuando n no es un cuadrado, se puede decir menos sobre los conjuntos de bloqueo no triviales de tamaño más pequeño. Un resultado bien conocido debido a Aart Blokhuis es: ^{[ 4 ]}

Teorema : Un conjunto de bloqueo no trivial en PG(2, p ), donde p es un número primo, tiene un tamaño de al menos 3( p + 1)/2.

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

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 identificaron con puntos en un plano proyectivo finito y las coaliciones ganadoras mínimas fueron líneas. Una coalición de bloqueo se definió como un conjunto de puntos que no contenía ninguna línea pero que intersectaba 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${\displaystyle \leq 9}$en 1969. ^{[ 11 ]}

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

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

Una " coloración bicolor " de${\displaystyle H}$es una partición${\displaystyle \{C,D\}}$de${\displaystyle X}$ en dos subconjuntos (clases de color) de tal manera que ningún borde sea monocromático, es decir, ningún borde esté contenido completamente dentro${\displaystyle C}$o dentro${\displaystyle D}$. Ahora ambos${\displaystyle C}$y${\displaystyle D}$son conjuntos bloqueantes.

En un plano proyectivo, un k -arco completo es un conjunto de k puntos, sin tres puntos colineales , que no se puede extender a un arco mayor (por lo tanto, cada punto que no está en el arco está en una línea secante del arco , una línea que interseca 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 rectas secantes de K es un conjunto bloqueante, B , de tamaño k ( k -1)/2. ^{[ 12 ]}

En cualquier plano proyectivo de orden q , para cualquier conjunto bloqueante no trivial B (con b = | B |, el tamaño del conjunto bloqueante), consideremos una línea que interseca a B en n puntos. Dado que ninguna línea está contenida en B , debe haber un punto, P , en esta línea que no esté en B. Las otras q líneas que pasan por P deben contener cada una al menos un punto de B para ser bloqueadas. Por lo tanto,${\displaystyle b\geq n+q.}$Si para alguna línea se cumple la igualdad en esta relación, el conjunto de bloqueo se denomina conjunto de bloqueo de tipo Rédei y la línea, línea de Rédei del conjunto de bloqueo (nótese que n será el mayor número de puntos colineales en B ). ^{[ 13 ]} No todos los conjuntos de bloqueo 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 ]}

Un conjunto de puntos en el espacio afín finito de Desarguesian${\displaystyle AG(n,q)}$Un conjunto que interseca cada hiperplano de forma no trivial, es decir, cada hiperplano es incidente con algún punto del conjunto, se denomina conjunto bloqueante afín. Identifique el espacio con${\displaystyle \mathbb {F} _{q}^{n}}$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 bloqueante de tamaño${\displaystyle 1+n(q-1)}$Jean Doyen conjeturó en una conferencia de Oberwolfach en 1976 que este es el tamaño mínimo posible de un conjunto de bloqueo. Esto fue demostrado por R. E. Jamison en 1977 ^{[ 15 ]} e independientemente por A. E. Brouwer y A. Schrijver en 1978 ^{[ 16 ]} utilizando el llamado método polinomial . Jamison demostró el siguiente resultado general de recubrimiento del cual se deduce la cota para conjuntos de bloqueo afines mediante dualidad:

Dejar${\displaystyle V}$frijol${\displaystyle n}$espacio vectorial dimensional sobre${\displaystyle \mathbb {F} _{q}}$. Entonces el número de${\displaystyle k}$Los conjuntos laterales de dimensión necesarios para cubrir todos los vectores excepto el vector cero son al menos${\displaystyle q^{nk}-1+k(q-1)}$Además, este límite es preciso.

• 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-4ISSN 1439-7382​ 
• C. Berge , Grafos e hipergrafos, North-Holland, Ámsterdam, 1973. (Defines${\displaystyle \tau (H)}$.)
• P. Duchet, Hipergrafos, Capítulo 7 en: Manual de Combinatoria, North-Holland, Ámsterdam, 1995.
• Hirschfeld, JWP (1979), Geometrías proyectivas sobre cuerpos finitos , Oxford: Oxford University Press, ISBN 978-0-19-853526-3
• Holder, Leanne D. (2001), Bloqueo de conjuntos de cono, tesis doctoral , Universidad de Colorado 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-3Archivado del original el 29/01/2016 , consultado el 23/01/2016.