New lower bounds for the degree/diameter problem via interaction with a browser-accessible LLM

Resumen Técnico: Nuevos límites inferiores para el problema del grado/diámetro mediante la interacción con un LLM accesible vía navegador

Planteamiento del problema
El artículo aborda el problema del grado/diámetro, que busca determinar $N(\Delta, D)$, el número máximo de vértices en un grafo conexo, simple y no dirigido con un grado máximo de como máximo $\Delta$ y un diámetro de como máximo $D$. Si bien la cota de Moore proporciona un límite superior para $N(\Delta, D)$, el valor exacto sigue siendo desconocido para la mayoría de los pares de parámetros. El enfoque específico de este trabajo es mejorar los límites inferiores conocidos para el diámetro $D=5$ con grados máximos $\Delta=12$ y $\Delta=16$.

Metodología
El estudio documenta un proceso de descubrimiento matemático realizado a través de un diálogo prolongado con un Modelo de Lenguaje Grande (LLM) accesible mediante un navegador (ChatGPT, identificado como gpt-5-5-pro en los metadatos) a través de su interfaz web estándar. Crucialmente, el autor no empleó ninguna capa de orquestación externa, marcos de agentes personalizados ni asistentes de prueba formales. La búsqueda se basó únicamente en las capacidades interactivas del LLM y en las intervenciones de nivel meta del autor.

El proceso de descubrimiento involucró:

1. Exploración inicial: El examen de la literatura y el intento de varios métodos de construcción (por ejemplo, elevaciones de permutación, grafos de voltaje, grafos regulares aleatorios), la mayoría de los cuales fallaron al no producir un certificado.
2. Cambio de abstracción: Se produjo una transición fundamental cuando el LLM propuso un principio de "elevación de tabla de rutas" (route-chart lift). Esto descomponió el problema en dos tareas de diseño finito independientes:
   • Problema del controlador: Construir un pequeño grafo auxiliar (el "controlador") donde cada par de vértices esté conectado por un camino sin retroceso (non-backtracking walk) de una longitud específica.
   • Problema de la tabla de fibras: Construir datos algebraico-lineales (una "tabla de rutas") sobre un cuerpo finito de tal manera que las matrices de controlabilidad específicas sean no singulares para todas las palabras reducidas de la longitud objetivo.
3. Intervenciones de nivel meta: El autor guió la búsqueda imponiendo restricciones (por ejemplo, evitar la búsqueda web, exigir ideas que no estuvieran esencialmente contenidas en la literatura existente y solicitar razones a priori del éxito) e interviniendo cuando la búsqueda derivaba hacia la reparación local o el ensayo y error.

Contribuciones clave
El artículo presenta dos contribuciones primarias:

1. Mejora de los límites inferiores matemáticos:
   Los autores presentan construcciones explícitas de grafos simples y no dirigidos que establecen nuevos límites inferiores:
   • $N(12, 5) \ge 34,992$ (mejorando el récord anterior de 29,621).
   • $N(16, 5) \ge 147,456$ (mejorando el récord anterior de 132,496).

Estos grafos se construyen elevando un grafo controlador específico de 144 vértices (derivado de un multigrafo de 6 vértices mediante una asignación de voltaje $C_4 \times C_6$) utilizando una tabla de rutas universal sobre los cuerpos finitos $\mathbb{F}_3$ y $\mathbb{F}_4$, respectivamente. Se demuestra que el diámetro es exactamente 5.

2. Análisis del proceso de colaboración Humano-IA:
   El artículo proporciona un análisis detallado basado en la transcripción de un proceso de descubrimiento matemático realizado sin automatización externa. Destaca cómo las intervenciones de nivel meta (como solicitar nuevos principios o detener los intentos de reparación local) ayudaron a dirigir al LLM hacia una abstracción exitosa (la elevación de la tabla de rutas) y una solución final. Los autores enfatizan que el LLM actuó como un motor de descubrimiento interactivo, mientras que el autor verificó todas las afirmaciones, códigos y certificados.

Resultados
Los grafos construidos $G_3$ (regular de grado 12, 34,992 vértices) y $G_4$ (regular de grado 16, 147,456 vértices) satisfacen la restricción de diámetro de 5. Las mejoras representan incrementos de aproximadamente 18.13% y 11.29% sobre los récords anteriores, respectivamente. Las construcciones se verifican mediante la computación finita de los caminos sin retroceso del controlador y la no singularidad de las matrices de controlabilidad para todas las palabras reducidas de longitud 5.

Significado y Reivindicaciones
El artículo reclama modestamente significancia en dos áreas:

• Matemática: Proporciona las primeras construcciones explícitas para estos parámetros específicos, acercando los límites inferiores conocidos a las cotas superiores de Moore.
• Metodológica: Sirve como un estudio de caso que demuestra que el descubrimiento matemático significativo es posible utilizando solo una interfaz de navegador estándar para un LLM, sin sistemas de agentes complejos. Los autores declaran explícitamente que no tratan al LLM como un autor o un probador autónomo; el investigador humano retiene la responsabilidad total de la validez matemática.

El artículo no pretende que esta estrategia específica sea generalmente efectiva o que el LLM posea capacidades de razonamiento matemático general más allá de este caso específico. Lo enmarca como un informe observacional de un caso exitoso único donde la guía humana y la generación del LLM se combinaron para resolver un problema abierto en la teoría de grafos.