Gráfico de juegos

En teoría de grafos, el grafo de Games es el grafo localmente lineal fuertemente regular más grande conocido . Sus parámetros como grafo fuertemente regular son (729, 112, 1, 20). Esto significa que tiene 729 vértices y 40824 aristas (112 por vértice). Cada arista se encuentra en un triángulo único (es un grafo localmente lineal ) y cada par de vértices no adyacentes tiene exactamente 20 vecinos compartidos. Recibe su nombre de Richard A. Games, quien sugirió su construcción en una comunicación no publicada ^{[ 1 ]} y escribió sobre construcciones relacionadas ^{[ 2 ] .}

La construcción de este gráfico implica el límite de 56 puntos establecido en${\displaystyle PG(5,3)}$. Este es un subconjunto de puntos sin tres en línea en la geometría proyectiva pentadimensional sobre un campo de tres elementos, y es único salvo simetría. ^{[ 3 ]} La geometría proyectiva de seis dimensiones,${\displaystyle PG(6,3)}$, puede dividirse en un espacio afín de seis dimensiones${\displaystyle AG(6,3)}$y una copia de${\displaystyle PG(5,3)}$, que forma el conjunto de puntos en el infinito con respecto al espacio afín. El grafo de Juegos tiene como vértices los 729 puntos del espacio afín.${\displaystyle AG(6,3)}$Cada línea en el espacio afín pasa por tres de estos puntos y por un cuarto punto en el infinito. El grafo contiene un triángulo por cada línea de tres puntos afines que pasa por un punto del conjunto de la tapa. ^{[ 1 ]}

Varias de las propiedades del grafo se derivan inmediatamente de esta construcción. Tiene${\displaystyle 729=3^{6}}$vértices, porque el número de puntos en un espacio afín es el tamaño del campo base elevado a la potencia de la dimensión. Para cada punto afín, hay 56 líneas que pasan por los puntos del conjunto de tapas, 56 triángulos que contienen el vértice correspondiente y${\displaystyle 112=56\times 2}$vecinos del vértice. Y no puede haber otros triángulos aparte de los que provienen de la construcción, porque cualquier otro triángulo tendría que provenir de tres líneas diferentes que se encuentran en un plano común de${\displaystyle PG(6,3)}$y los tres puntos de ajuste de las tres líneas estarían todos en la intersección de este plano con${\displaystyle PG(5,3)}$, que es una línea. Pero esto violaría la propiedad definitoria de un conjunto de tapas, que es que no tiene tres puntos en una línea, por lo que no puede existir tal triángulo adicional. La propiedad restante de los grafos fuertemente regulares, que todos los pares de puntos no adyacentes tienen el mismo número de vecinos compartidos, depende de las propiedades específicas del conjunto de tapas de 5 dimensiones.

Con el${\displaystyle 3\times 3}$El grafo de Rook y el grafo de Brouwer-Haemers , el grafo de Games es uno de los tres únicos grafos fuertemente regulares posibles cuyos parámetros tienen la forma${\displaystyle {\bigl (}(n^{2}+3n-1)^{2},n^{2}(n+3),1,n(n+1){\bigr )}}$. ^{[ 4 ]}

Las mismas propiedades que producen un gráfico fuertemente regular a partir de un conjunto de tapas también se pueden usar con un conjunto de tapas de 11 puntos en${\displaystyle PG(4,3)}$, produciendo un grafo fuertemente regular más pequeño con parámetros (243,22,1,2). ^{[ 5 ]} Este grafo es el grafo de Berlekamp–Van Lint–Seidel . ^{[ 6 ]}