En teoría de grafos, el grafo de Games es el mayor grafo localmente lineal fuertemente regular 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 está en un único triángulo (es un grafo localmente lineal ) y cada par de vértices no adyacentes tiene exactamente 20 vecinos compartidos. Recibe su nombre en honor a Richard A. Games, quien sugirió su construcción en una comunicación inédita [1] y escribió sobre construcciones relacionadas. [2]
La construcción de este grafo implica el conjunto de 56 puntos de la tapa en . Este es un subconjunto de puntos sin tres en línea en la geometría proyectiva de cinco dimensiones sobre un cuerpo de tres elementos, y es único hasta la simetría. [3] La geometría proyectiva de seis dimensiones, , se puede dividir en un espacio afín de seis dimensiones y una copia de , que forma el conjunto de puntos en el infinito con respecto al espacio afín. El grafo de Games tiene como vértices los 729 puntos del espacio afín . 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 para cada línea de tres puntos afines que pasa por un punto del conjunto de tapas. [1]
Varias de las propiedades del grafo se desprenden inmediatamente de esta construcción. Tiene vértices, porque el número de puntos en un espacio afín es el tamaño del cuerpo base elevado a 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 vecinos del vértice. Y no puede haber otros triángulos que 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 , y los tres puntos del conjunto de tapas de las tres líneas estarían todos en la intersección de este plano con , que es una línea. Pero esto violaría la propiedad definitoria de un conjunto de tapas de que no tiene tres puntos en una línea, por lo que no puede existir un triángulo adicional. La propiedad restante de los grafos fuertemente regulares, de 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 cinco dimensiones.
Con el gráfico de Rook y el gráfico de Brouwer-Haemers , el gráfico de Games es uno de los tres únicos gráficos fuertes y regulares posibles cuyos parámetros tienen la forma . [4]
Las mismas propiedades que producen un gráfico fuertemente regular a partir de un conjunto de caps también se pueden usar con un conjunto de caps de 11 puntos en , produciendo un gráfico fuertemente regular más pequeño con parámetros (243,22,1,2). [5] Este gráfico es el gráfico de Berlekamp–Van Lint–Seidel . [6]
