Límites Inferiores de Spanner Aditivo con Estructura de Grafo Interno Óptima

Construimos grafos de n nodos sobre los cuales cualquier spanner de tamaño O (n) tiene un error aditivo de al menos + (n^3/17), mejorando el anterior mejor límite inferior de (n^1/7) Bodwin-Hoppenworth FOCS '22. Nuestra construcción completa los primeros dos pasos de un programa de investigación particular de tres pasos, introducido en trabajos previos y resumido aquí, destinado a producir límites ajustados para el problema alineando aspectos de las construcciones de límites superior e inferior. Más específicamente, desarrollamos técnicas que permiten el uso de grafos internos en el marco del límite inferior cuyas propiedades técnicas son probadamente ajustadas con las suposiciones correspondientes hechas en los límites superiores. Como aplicación adicional de nuestras técnicas, mejoramos el límite inferior correspondiente para emuladores aditivos de tamaño O (n) a + (n^1/14).