Cuenta de juegos

El gráfico Games es el gráfico localmente lineal fuertemente regular más grande conocido . Sus parámetros como gráfico fuertemente regular son (729,112,1,20). Esto significa que el gráfico tiene 729 vértices y 40824 aristas (112 aristas por vértice). Cada borde está en un solo triángulo (este es un gráfico lineal local ) y cada par de vértices no adyacentes tiene exactamente 20 vecinos comunes. El gráfico lleva el nombre de Richard A. Games, quien propuso su construcción en una correspondencia inédita [1] y escribió sobre construcciones relacionadas [2] .

Edificio

La construcción de este gráfico utiliza un conjunto de límites único (hasta simetría) de 56 puntos ( conjunto de límites en inglés , subconjuntos de puntos, de los cuales tres no se encuentran en la misma línea) en geometría proyectiva de cinco dimensiones sobre un tres -campo de elemento [3] . Una geometría proyectiva de seis dimensiones, , se puede descomponer en un espacio afín de seis dimensiones y una copia ( puntos en el infinito dado el espacio afín). El grafo Games tiene 729 puntos del espacio afín como vértices . Cada línea en el espacio afín pasa por tres de estos puntos y un cuarto punto en el infinito. El gráfico contiene un triángulo para cualquier línea de tres puntos afines que pasa por un punto del cap-set [1] .  

Propiedades

Algunas de las propiedades del gráfico se derivan inmediatamente de la construcción. El gráfico tiene vértices porque el número de puntos en un espacio afín es igual al tamaño del campo base elevado a la potencia de la dimensión. Para cada punto afín, hay 56 líneas a través de los puntos del cap-set, 56 triángulos que contienen el vértice correspondiente y vecinos del vértice. Y no puede haber más triángulos que los obtenidos durante la construcción, ya que cualquier otro triángulo se obtendría de tres rectas diferentes que se cortan en un plano común , y tres puntos del conjunto cap de tres rectas estarían en la intersección de este plano con , que da una línea. Sin embargo, esto violaría la propiedad del conjunto de mayúsculas de que tres de sus puntos no se encuentran en la misma línea, por lo que no puede existir ningún triángulo adicional. La propiedad restante de la regularidad gráfica fuerte, que todos los pares de vértices no adyacentes tienen el mismo número de vecinos comunes, depende de las propiedades del conjunto de límites de 5 dimensiones.

Gráficos relacionados

Junto con el gráfico de torre y el gráfico de Brouwer-Hemers , el gráfico de Games es uno de los tres posibles gráficos fuertemente regulares cuyos parámetros tienen la forma [4] .

Las mismas propiedades que dan un gráfico fuertemente regular de un conjunto de límites se pueden usar con un conjunto de límites de 11 puntos en , lo que da el gráfico fuertemente regular más pequeño con parámetros (243,22,1,2) [5] . Este es el Conde Conde Berlekamp-van Lint-Seidel [6] .

Notas

  1. ↑ 1 2 van Lint JH, Brouwer AE Gráficos fuertemente regulares y geometrías parciales // Enumeración y diseño: artículos de la conferencia sobre combinatoria celebrada en la Universidad de Waterloo, Waterloo, Ontario, del 14 de junio al 2 de julio de 1982 / David M. Jackson, Scott A. Vanstone. - Londres: Academic Press, 1984. - S. 85-122. . Véanse en particular las págs. 114-115.
  2. ↑ Richard A. Juegos. El problema de empaquetamiento para geometrías proyectivas sobre GF(3) con dimensión mayor a cinco // Journal of Combinatorial Theory . - 1983. - T. 35 , núm. 2 . — S. 126–144 . -doi : 10.1016 / 0097-3165(83)90002-X . . Véase en particular la Tabla VII, página 139, líneas y .
  3. ↑ Raymond Hill. Mayúsculas y códigos // Matemáticas discretas . - 1978. - T. 22 , núm. 2 . — págs. 111–137 . - doi : 10.1016/0012-365X(78)90120-6 .
  4. ↑ Bondarenko Andriy V., Radchenko Danylo V. Sobre una familia de gráficos fuertemente regulares con  // Journal of Combinatorial Theory . - 2013. - T. 103 , núm. 4 . — S. 521–531 . -doi : 10.1016/ j.jctb.2013.05.005 .
  5. ↑ Peter J. Cameron. Cuadrángulos parciales // The Quarterly Journal of Mathematics. - 1975. - T. 26 . — S. 61–73 . -doi : 10.1093 / qmath/26.1.61 .
  6. ↑ Berlekamp ER, van Lint JH, Seidel JJ Un gráfico fuertemente regular derivado del código Golay ternario perfecto // Un estudio de la teoría combinatoria (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). - Ámsterdam: Holanda Septentrional, 1973. - S. 25–30 . -doi : 10.1016/ B978-0-7204-2262-7.50008-9 .