Es fácil si lo intentas...

En una bitácora del Departamento de Álgebra de la Universidad de Sevilla propusieron un problema de un clasificatorio olímpico eslovaco, que se reduce a buscar cierto grafo fuertemente regular. Dicen que si es asequible para chavos de 17 años sin preparación universitaria, entonces basta con "echarle imaginación" para resolverlo.

Parece, sin embargo, que la clasificación o búsqueda de grafos fuertemente regulares no es tan fácil en general (ni siquiera para valores no muy grandes de sus parámetros), y la página de Ted Spence nos revela que en un artículo de 1995 él encontró 32,548 soluciones al grafos que satisfacen las restricciones del problema propuesto por los españoles. La solución de los sevillanos ha de estar muy emocionante, porque por la forma en que está enunciado el problema seguramente demostrarán que no hay otras soluciones. Esta caracterización parcial ha de ser una del Libro, pues Peter Cameron menciona que "una caracterización completa de los parámetros de los grafos fuertemente regulares no se conoce".

Sabiendo esto ya duermo un poco más tranquilo. En mis intentos fallidos, primero demostré que la solución debiera tener cierto número de aristas, y mi cota estaba mal. Luego me pareció encontrar una cota superior que descartaba ¡justamente las soluciones calculadas por Spence! Se imaginarán mi sorpresa al enterarme de que no solo sí hay soluciones de ese tipo, sino que encima hay varios miles de ellas. Al parecer, si las clasificaciones para números pequeños de vértices está completa, no existen las soluciones pequeñas que trataba de construir. Me imaginé que podría ser un grafo de Harary, pero no me atreví a preguntar si cierto parámetro en el problema era una cota inferior o un valor exacto que debía alcanzar el grafo buscado.

Me hace falta muchísima más imaginación :(.

P. D.: Los sevillanos publicaron dos soluciones, una de Alberto Castaño y otra "al más puro estilo de Warren Sánchez" (¡qué simpáticos!). La de Castaño está muy bien y me convence plenamente, no así la que ellos proponen. Castaño reduce el problema a un conteo doble de aristas para obtener un polinomio cuadrático que hay que resolver diofánticamente, y que bien demuestra que las soluciones de Spence son las únicas posibles.