Concepto generalizado de estructura de incidencia de polígonos
En matemáticas , un polígono generalizado es una estructura de incidencia introducida por Jacques Tits en 1959. Los n -gonos generalizados engloban como casos especiales los planos proyectivos (triángulos generalizados, n = 3) y los cuadrángulos generalizados ( n = 4). Muchos polígonos generalizados surgen de grupos de tipo Lie , pero también los hay exóticos que no se pueden obtener de esta manera. Los polígonos generalizados que satisfacen una condición técnica conocida como propiedad de Moufang han sido completamente clasificados por Tits y Weiss. Todo n -gono generalizado con n pares es también un cuasi-polígono .
Definición
Un 2 -gono generalizado (o un dígono ) es una estructura de incidencia con al menos 2 puntos y 2 líneas donde cada punto incide en cada línea.
No tiene m -gonos ordinarios como subgeometría para .
Tiene un n -gono ordinario como subgeometría.
Para cualquier existe una subgeometría ( ) isomorfa a un n -gono ordinario tal que .
Una forma equivalente, pero a veces más sencilla, de expresar estas condiciones es: considerar el gráfico de incidencia bipartito con el conjunto de vértices y las aristas que conectan los pares de puntos y líneas incidentes.
La circunferencia del gráfico de incidencia es el doble del diámetro n del gráfico de incidencia.
De esto debería quedar claro que los gráficos de incidencia de polígonos generalizados son gráficos de Moore .
Un polígono generalizado es de orden (s,t) si:
todos los vértices del grafo de incidencia correspondientes a los elementos de tienen el mismo grado s + 1 para algún número natural s ; en otras palabras, cada línea contiene exactamente s + 1 puntos,
todos los vértices del grafo de incidencia correspondientes a los elementos de tienen el mismo grado t + 1 para algún número natural t ; en otras palabras, cada punto se encuentra exactamente en t + 1 líneas.
Decimos que un polígono generalizado es grueso si cada punto (línea) incide con al menos tres líneas (puntos). Todos los polígonos generalizados gruesos tienen un orden.
El dual de un n -gono generalizado ( ), es la estructura de incidencia con noción de puntos y líneas invertidas y la relación de incidencia tomada como la relación inversa de . Se puede demostrar fácilmente que se trata nuevamente de un n -gono generalizado.
Para cualquier n natural ≥ 3, considere el límite del polígono ordinario con n lados. Declare que los vértices del polígono son los puntos y los lados son las líneas, con la inclusión de conjuntos como la relación de incidencia. Esto da como resultado un n -gono generalizado con s = t = 1.
Para cada grupo de tipo Lie G de rango 2 hay asociado un n -gono generalizado X con n igual a 3, 4, 6 u 8 tal que G actúa transitivamente sobre el conjunto de banderas de X . En el caso finito, para n=6 , se obtiene el hexágono Split Cayley de orden ( q , q ) para G 2 ( q ) y el hexágono de trialidad torcida de orden ( q 3 , q ) para 3 D 4 ( q 3 ) , y para n=8 , se obtiene el octógono Ree-Tits de orden ( q , q 2 ) para 2 F 4 ( q ) con q = 2 2 n +1 . Hasta la dualidad, estos son los únicos hexágonos u octógonos generalizados finitos gruesos conocidos.
Restricción de parámetros
Walter Feit y Graham Higman demostraron que los n -gonos generalizados finitos de orden ( s , t ) con s ≥ 2, t ≥ 2 solo pueden existir para los siguientes valores de n :
2, 3, 4, 6 u 8. Otra prueba del resultado de Feit-Higman fue dada por Kilmoyer y Solomon.
Los "n"-gonos generalizados para estos valores se denominan digones, triángulos, cuadrángulos, hexágonos y octágonos generalizados.
Cuando el teorema de Feit-Higman se combina con las desigualdades de Haemers-Roos, obtenemos las siguientes restricciones,
Si n = 2, el gráfico de incidencia es un gráfico bipartito completo y, por lo tanto, "s", "t" pueden ser números enteros arbitrarios.
Si n = 6, entonces st es un cuadrado y t 1/3 ≤ s ≤ t 3 .
Si n = 8, entonces 2st es un cuadrado y t 1/2 ≤ s ≤ t 2 .
Si se permite que s o t sean 1 y la estructura no es el n -gono ordinario, entonces, además de los valores de n ya enumerados, solo n = 12 puede ser posible.
Todo hexágono generalizado finito conocido de orden ( s , t ) para s , t > 1 tiene orden
( q , q ): los hexágonos de Cayley divididos y sus duales,
( q 3 , q ): el hexágono de trialidad torcido, o
( q , q 3 ): el hexágono de trialidad doblemente torcido,
donde q es una potencia prima.
Todo octágono generalizado finito conocido de orden ( s , t ) para s , t > 1 tiene orden
( q , q 2 ): el octágono de Ree-Tits o
( q 2 , q ): el octágono dual Ree-Tits,
donde q es una potencia impar de 2.
Polígonos generalizados semifinitos
Si s y t son ambos infinitos entonces existen polígonos generalizados para cada n mayor o igual a 2. Se desconoce si existen o no polígonos generalizados con uno de los parámetros finito (y mayor que 1 ) mientras que el otro es infinito (estos casos se llaman semifinitos ). Peter Cameron demostró la no existencia de cuadrángulos generalizados semifinitos con tres puntos en cada línea, mientras que Andries Brouwer y Bill Kantor demostraron independientemente el caso de cuatro puntos en cada línea. El resultado de la no existencia para cinco puntos en cada línea fue demostrado por G. Cherlin usando la teoría de modelos . [1] No se conocen tales resultados sin hacer más suposiciones para hexágonos u octógonos generalizados, incluso para el caso más pequeño de tres puntos en cada línea.
Aplicaciones combinatorias
Como se señaló anteriormente, los gráficos de incidencia de polígonos generalizados tienen propiedades importantes. Por ejemplo, cada n -gono generalizado de orden (s,s) es una jaula (s+1,2n) . También están relacionados con los gráficos expansores ya que tienen buenas propiedades de expansión. [2] Varias clases de gráficos expansores extremales se obtienen a partir de polígonos generalizados. [3] En la teoría de Ramsey , los gráficos construidos utilizando polígonos generalizados nos dan algunos de los límites inferiores constructivos más conocidos para los números de Ramsey fuera de la diagonal. [4]
^ Cherlin, Gregory (2005). "Cuadrángulos generalizados finitos locales con un máximo de cinco puntos por línea". Matemáticas discretas . 291 (1–3): 73–79. doi : 10.1016/j.disc.2004.04.021 .
^ Tanner, R. Michael (1984). "Concentradores explícitos a partir de N-Gons generalizados". Revista SIAM sobre métodos algebraicos y discretos . 5 (3): 287–293. doi :10.1137/0605030. hdl : 10338.dmlcz/102386 .
^ Nozaki, Hiroshi (2014). "Límites de programación lineal para gráficos regulares". arXiv : 1407.4562 [math.CO].
^ Kostochka, Alejandro; Pudlák, Pavel; Rödl, Vojtech (2010). "Algunos límites constructivos a los números de Ramsey". Revista de teoría combinatoria, serie B. 100 (5): 439–445. doi : 10.1016/j.jctb.2010.01.003 .
Godsil, Chris ; Royle, Gordon (2001), Teoría de grafos algebraicos , Textos de posgrado en matemáticas, vol. 207, Nueva York: Springer-Verlag, doi :10.1007/978-1-4613-0163-9, ISBN 978-0-387-95220-8, Sr. 1829620.
Feit, Walter ; Higman, Graham (1964), "La inexistencia de ciertos polígonos generalizados", Journal of Algebra , 1 (2): 114–131, doi : 10.1016/0021-8693(64)90028-6 , MR 0170955.
Haemers, WH; Roos, C. (1981), "Una desigualdad para hexágonos generalizados", Geometriae Dedicata , 10 (1–4): 219–222, doi :10.1007/BF01447425, MR 0608143.
Kantor, WM (1986). "Polígonos generalizados, SCAB y GAB". Edificios y geometría de diagramas . Apuntes de clase de matemáticas. Vol. 1181. Springer-Verlag, Berlín. págs. 79–158. CiteSeerX 10.1.1.74.3986 . doi :10.1007/BFb0075513. ISBN .978-3-540-16466-1.
Kilmoyer, Robert; Solomon, Louis (1973), "Sobre el teorema de Feit-Higman", Journal of Combinatorial Theory, Serie A , 15 (3): 310–322, doi : 10.1016/0097-3165(73)90076-9 , MR 0357157
Van Maldeghem, Hendrik (1998), Polígonos generalizados , Monografías de Matemáticas, vol. 93, Basilea: Birkhäuser Verlag, doi :10.1007/978-3-0348-0271-0, ISBN 978-3-7643-5864-8, Sr. 1725957.
Stanton, Dennis (1983), " N -gonos generalizados y polinomios de Chebychev", Journal of Combinatorial Theory, Serie A , 34 (1): 15–27, doi : 10.1016/0097-3165(83)90036-5 , MR 0685208.
Tits, Jacques ; Weiss, Richard M. (2002), Polígonos de Moufang , Springer Monographs in Mathematics, Berlín: Springer-Verlag, ISBN 978-3-540-43714-7, Sr. 1938841.