En matemáticas , un polígono generalizado es una estructura de incidencia introducida por Jacques Tits en 1959. Los n- gones generalizados abarcan como casos especiales planos proyectivos (triángulos generalizados, n = 3) y cuadrángulos generalizados ( n = 4). Muchos polígonos generalizados surgen de grupos de tipo Lie , pero también hay exóticos que no se pueden obtener de esta forma. Los polígonos generalizados que satisfacen una condición técnica conocida como propiedad Moufang han sido clasificados por completo por Tits y Weiss. Cada n -gon generalizado conn even también es un polígono cercano .
Definición
Un 2 -gon generalizado (o un digon) es una estructura de incidencia con al menos 2 puntos y 2 líneas donde cada punto es incidente a cada línea.
Para un n -gon generalizado es una estructura de incidencia (), dónde es el conjunto de puntos, es el conjunto de líneas y es la relación de incidencia , tal que:
- Es un espacio lineal parcial .
- No tiene gones m ordinarios como subgeometría para.
- Tiene un n -gon ordinario como subgeometría.
- Para cualquier existe una subgeometría) isomorfo a un n -gon ordinario tal que.
Una forma equivalente, pero a veces más sencilla, de expresar estas condiciones es: considere el gráfico de incidencia bipartito con el conjunto de vértices y los bordes 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.
A partir de esto, debe 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 gráfico de incidencia correspondientes a los elementos de tienen el mismo grado s + 1 para algunos números naturales s ; en otras palabras, cada línea contiene exactamente s + 1 puntos,
- todos los vértices del gráfico 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 al menos con tres líneas (puntos). Todos los polígonos generalizados gruesos tienen un orden.
El dual de un n- gón generalizado (), es la estructura de incidencia con la noción de puntos y líneas invertidas y la relación de incidencia se toma como la relación inversa de. Se puede demostrar fácilmente que se trata de nuevo de un n -gon generalizado .
Ejemplos de
- El gráfico de incidencia de un digón generalizado es un gráfico bipartito completo K s +1, t +1 .
- Para cualquier n natural ≥ 3, considere el límite del polígono ordinario con n lados. Declare los vértices del polígono como puntos y los lados como líneas, con inclusión de conjuntos como relación de incidencia. Esto da como resultado un n -gon generalizado con s = t = 1.
- Para cada grupo de Lie de tipo G de rango 2 hay un asociado generalizada n -gon X con n igual a 3, 4, 6 o 8 de tal manera que G actúa transitivamente en 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 retorcido 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 n -gones 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. Kilmoyer y Solomon dieron otra prueba del resultado de Feit-Higman.
Los gones "n" 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 = 3, la estructura es un plano proyectivo finito y s = t .
- Si n = 4, la estructura es un cuadrángulo generalizado finito y t 1/2 ≤ s ≤ t 2 .
- Si n = 6, entonces st es un cuadrado y t 1/3 ≤ s ≤ t 3 .
- Si n = 8, entonces el 2º es un cuadrado y t 1/2 ≤ s ≤ t 2 .
- Si s o t está permitido para ser 1 y la estructura no es el ordinario n -gon continuación, además de los valores de n ya enumeradas, solamente 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 Cayley divididos y sus duales,
- ( q 3 , q ): el hexágono de trialidad retorcido, o
- ( q , q 3 ): el hexágono de trialidad retorcido dual,
donde q es un poder primo.
Todo octágono generalizado finito conocido de orden ( s , t ) para s , t > 1 tiene orden
- ( q , q 2 ): el octágono 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 polígonos generalizados con uno de los parámetros finito (y mayor que 1 ) mientras que el otro es infinito (estos casos son llamado semifinito ). Peter Cameron demostró la inexistencia de cuadrángulos generalizados semifinitos con tres puntos en cada línea, mientras que Andries Brouwer y Bill Kantor probaron independientemente el caso de cuatro puntos en cada línea. G. Cherlin demostró el resultado de la inexistencia de cinco puntos en cada línea utilizando la teoría de modelos . [1] No se conocen tales resultados sin hacer suposiciones adicionales 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 -gon generalizado de orden (s, s) es una jaula (s + 1,2n) . También están relacionados con los gráficos de expansión, ya que tienen buenas propiedades de expansión. [2] Varias clases de gráficos de expansores extremos 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 en números de Ramsey fuera de la diagonal. [4]
Ver también
Referencias
- ^ Cherlin, Gregory (2005). "Cuadrángulos generalizados localmente finitos 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 de N-Gons generalizados". Revista SIAM de 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, Alexandr; Pudlák, Pavel; Rödl, Vojtech (2010). "Algunos límites constructivos en 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, 207 , Nueva York: Springer-Verlag, doi : 10.1007 / 978-1-4613-0163-9 , ISBN 978-0-387-95220-8, Señor 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, SCABs y GABs". Edificios y geometría de diagramas . Apuntes de clase en matemáticas. 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 en matemáticas, 93 , Basilea: Birkhäuser Verlag, doi : 10.1007 / 978-3-0348-0271-0 , ISBN 978-3-7643-5864-8, Señor 1725957.
- Stanton, Dennis (1983), " N -gones 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.
- Tetas, Jacques ; Weiss, Richard M. (2002), polígonos de Moufang , Springer Monographs in Mathematics, Berlín: Springer-Verlag, ISBN 978-3-540-43714-7, Señor 1938841.