🔢 mathematics

Exact Zarankiewicz Values On Two Finite Frontier Slices

Este artículo presenta una prueba asistida por computadora combinada y basada en certificados que establece los números de Zarankiewicz exactos para rebanadas finitas específicas y una frontera vecina del problema Z(m,n,3,3), utilizando certificados de órbita, lemas de eliminación y verificación aritmética rigurosa para confirmar valores tales como Z(12,n,3,3)=6n para 18≤n≤22 y Z(13,22,3,3)=137.

Autores originales: Koyar Afrasyab

Publicado 2026-08-11

📖 4 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Koyar Afrasyab

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que eres un planificador urbano intentando construir la red de carreteras más eficiente posible. Tienes dos grupos de ubicaciones: un conjunto de "Centros" en un lado y un conjunto de "Destinos" en el otro. Tu objetivo es dibujar tantas carreteras (conexiones) como puedas entre ellos para mantener el flujo del tráfico. Sin embargo, existe una estricta ley de zonificación: se te prohíbe construir un patrón de intersección específico y desordenado. En el lenguaje matemático, este patrón prohibido es un "subgrafo bipartito completo", o simplemente, no puedes tener una situación en la que tres Centros estén todos conectados a los mismos tres Destinos. Si lo haces, habrás roto la regla.

Este rompecabezas es conocido como el problema de Zarankiewicz. Es un clásico acertijo de la combinatoria, que es la rama de las matemáticas dedicada a contar, organizar y disponer cosas. Mientras que los matemáticos han descubierto cómo resolver esto para ciudades masivas y teóricas, el verdadero desafío reside en las ciudades de "tamaño medio". Para estos tamaños específicos, el número de mapas de carreteras posibles es tan enorme que no puedes revisarlos todos a mano, pero también son demasiado complejos para las fórmulas simples que funcionan para ciudades infinitas. Es una zona de dificultad de "punto justo": demasiado grande para una demostración de lápiz y papel, pero demasiado pequeña para los atajos "asintóticos" que funcionan para ciudades infinitas. Resolver estos números exactos importa porque revelan los límites ocultos de la eficiencia en las redes, desde chips de computadora hasta conexiones en redes sociales.

Entra Koyar Afrasyab, un investigador que acaba de abrir un conjunto particularmente obstinado de estos rompecabezas de tamaño medio. Piensa en el problema como intentar encontrar el número máximo absoluto de carreteras que puedes dibujar en una cuadrícula sin crear ese atasco de tráfico prohibido de "tres por tres". Afrasyab no solo adivinó; construyó una agencia de detectives digital para cazar la respuesta. El artículo se centra en dos "rebanadas" específicas de este problema: cuadrículas con 12 filas y cuadrículas con 13 filas, emparejadas con varios números de columnas.

El principal descubrimiento es una lista de "límites de velocidad" exactos para estas cuadrículas. Para una cuadrícula con 12 filas y cualquier número de 18 a 22 columnas, el número máximo de carreteras (aristas) que puedes tener sin romper la regla es exactamente $6n$ (donde $n$ es el número de columnas). Por ejemplo, una cuadrícula de 12 por 18 puede albergar exactamente 108 carreteras, y una cuadrícula de 12 por 22 puede albergar exactamente 132. El artículo demuestra esto mostrando que si intentas añadir una sola carretera más a estas cuadrículas, inevitablemente crearás el atasco de tráfico prohibido.

La parte más dramática de la historia involucra una cuadrícula de 13 por 22. Las suposiciones previas sugerían que el límite podría ser tan alto como 140 carreteras. La prueba asistida por computadora de Afrasyab actúa como un tamiz, filtrando cada arreglo imposible. Comenzaron asumiendo que alguien podría construir una cuadrícula con 138 carreteras sin romper las reglas. A través de un proceso inteligente de eliminación —revisando los "perfiles" de cuántas carreteras se conectan a cada punto— demostraron que 138 es imposible. Redujeron el margen hasta que encontraron el verdadero techo: 137 carreteras. Incluso proporcionaron un mapa específico y verificado de 137 carreteras que funciona, demostrando que puedes alcanzar ese número pero no ir más allá.

El artículo también fija el mapa para varias cuadrículas vecinas, determinando los límites exactos para tamaños como 13 por 18, 14 por 17 y 15 por 18. Para un caso complicado, una cuadrícula de 16 por 17, la prueba confirma que definitivamente puedes construir 132 carreteras, pero el límite superior sigue siendo un rango estrecho entre 132 y 133.

Lo que hace que este trabajo sea especial es cómo se hizo. El autor no solo ejecutó un programa de computadora de "caja negra" que dijera "No se encontró solución". En su lugar, creó una prueba "basada en certificados". Imagina a un detective dejando un rastro de migas de pan: para cada escenario imposible que descartó, dejó un "recibo" matemático (un certificado) que cualquiera puede verificar con una calculadora simple para comprobar el error. El artículo incluye un paquete digital donde puedes ejecutar un solo comando para volver a reproducir toda la investigación, verificando millones de estos recibos para asegurar que no se cometieron errores. Es una victoria rigurosa, transparente y totalmente reproducible para la comunidad matemática, convirtiendo un conjunto de respuestas de "tal vez" en un conjunto de hechos de "definitivamente".

Resumen Técnico: Valores Exactos de Zarankiewicz en Dos Fronteras Finitas

Planteamiento del Problema
El artículo aborda el problema de Zarankiewicz, que busca el número máximo de aristas, denotado como $Z(m, n, s, t)$ , en un grafo bipartito con partes de tamaño $m$ y $n$ que no contiene un subgrafo bipartito completo $K_{s,t}$ . Específicamente, el autor se centra en el caso $s=t=3$ (evitando $K_{3,3}$ ) para parámetros finitos moderados. Si bien la teoría asintótica está bien desarrollada, los valores exactos para dimensiones finitas específicas siguen siendo difíciles debido a una severa simetría y al alto costo de la certificación de pruebas. El artículo apunta a una "frontera finita" de valores previamente no resueltos o parcialmente resueltos, incluyendo la franja $Z(12, n, 3, 3)$ para $18 \le n \le 22$ , el caso específico $Z(13, 22, 3, 3)$ , y un grupo de valores vecinos alrededor de $13 \times 18$ y $16 \times 17$ .

Metodología
La prueba es asistida por computadora pero es estrictamente basada en certificados, lo que la distingue de los métodos que dependen únicamente de resolvedores de programación lineal entera mixta (MILP) que devuelven "infactible" o de resolvedores SAT sin testigos explícitos. La verificación se basa en aritmética exacta de enteros y racionales (utilizando Fraction de Python y librerías estándar), con la optimización de punto flotante utilizada únicamente para el descubrimiento inicial de los certificados.

La metodología emplea una estrategia de reducción multicapa:

Relajación Global y Perfiles de Grado: Para el caso $13 \times 22$ , el autor asume una matriz hipotética con 138 aristas. Al analizar la función de "penalización" $p(d) = \binom{d}{3} - 15d + 70$ asociada con los grados de las columnas, el espacio de búsqueda se reduce de todas las matrices posibles a solo 83 perfiles de grado distintos (histogramas de grados de columna).
Certificados de Farkas: Para 77 de estos 83 perfiles, el autor construye certificados de Farkas racionales exactos. Estos certificados demuestran la infactibilidad al demostrar que las restricciones lineales impuestas por la condición libre de $K_{3,3}$ (específicamente, que cada terna de filas aparece en como máximo 2 columnas) no pueden ser satisfechas por ninguna solución entera no negativa para ese perfil.
Enumeración de Filas Marcadas y Restos: Los seis perfiles restantes se excluyen mediante técnicas más granulares. El autor fija una "fila marcada", la elimina y analiza el "multigrafo de resto" resultante en los 12 puntos restantes. Esto implica:
- Argumentos de Congruencia: Uso de aritmética modular sobre los déficits de fila para descartar configuraciones específicas (por ejemplo, el perfil 6187391).
- Restricciones de Matriz de Gram: Verificación de condiciones de rango y determinante de la matriz de incidencia de los bloques residuales.
- Enumeración Exacta: Enumeración exhaustiva de diseños de bloques residuales y aplicación de certificados de Farkas escalados a enteros para los sistemas de factorización restantes.
Lemas de Deletción y Testigos: Para la franja $12 \times n$ y el cierre de la frontera, el autor utiliza "lemas de deletción" (que relacionan $Z(m, n)$ con $Z(m, n-1)$ ) combinados con testigos constructivos explícitos (matrices que alcanzan los límites inferiores) para establecer igualdades exactas.

Contribuciones Clave y Resultados
El artículo proporciona una prueba combinada, basada en certificados, para los siguientes valores exactos y límites:

La Franja $12 \times n$ : Demuestra que $Z(12, n, 3, 3) = 6n$ para $18 \le n \le 22$ . Esto se establece mediante un certificado exacto para $Z(12, 18, 3, 3) = 108$ y argumentos de deletción subsecuentes apoyados por testigos explícitos para $n=19, 20, 21, 22$ .
El Caso $13 \times 22$ : Demuestra que $Z(13, 22, 3, 3) = 137$ . El límite superior de 138 es eliminado mediante el análisis de perfiles descrito anteriormente. Un límite inferior de 137 se confirma mediante una construcción explícita (una matriz binaria de $13 \times 22$ con 137 unos y sin $K_{3,3}$ ).
Cierre de la Frontera: Establece valores exactos para cuatro celdas vecinas:
- $Z(13, 18, 3, 3) = 116$
- $Z(14, 17, 3, 3) = 118$
- $Z(14, 18, 3, 3) = 124$
- $Z(15, 17, 3, 3) = 126$
- $Z(15, 18, 3, 3) = 132$
El Intervalo $16 \times 17$ : Reporta el intervalo $132 \le Z(16, 17, 3, 3) \le 133$ . El límite inferior está respaldado por un nuevo testigo de 132 aristas; el límite superior de 133 se toma de la literatura previa (Collins et al.). El artículo señala explícitamente que el valor exacto para esta celda específica no se determina dentro de este trabajo.

Significancia y Reivindicaciones
El autor afirma que este trabajo proporciona una prueba completa, reproducible y basada en certificados para estos valores específicos de Zarankiewicz. La significancia radica en la separación rigurosa del descubrimiento (donde se pueden usar heurísticas de punto flotante) de la verificación (que utiliza únicamente aritmética exacta).

Reproducibilidad: El artículo incluye una "puerta de verificación de un solo comando" que reproduce todos los 5.7 millones de comprobaciones de no negatividad exacta, incluyendo la regeneración de perfiles de grado, la ejecución de certificados de Farkas y la enumeración exhaustiva de diseños de bloques residuales.
Modestia: El autor establece explícitamente que estos resultados deben considerarse "nuevas pruebas asistidas por computadora pendientes de reproducción independiente y revisión por pares". El artículo no pretende resolver el problema general de Zarankiewicz ni proporcionar un algoritmo universal, sino que demuestra una división del trabajo para problemas extremos finitos: utilizar relajaciones globales gruesas para eliminar la mayoría de los casos y reservar la enumeración exacta e intensiva computacionalmente para los pocos perfiles residuales "difíciles".
Arte Previo: El autor observa que, aunque la construcción de 137 aristas para $13 \times 22$ fue reportada previamente, el límite superior exacto es una nueva contribución. Del mismo modo, los valores específicos para la franja $12 \times n$ ( $n=18$ a $21$) y los valores de cierre de la frontera se reportan como nuevos resultados exactos no encontrados en la literatura indexada previa a la fecha del artículo (agosto de 2026).

El artículo concluye enfatizando que no se utilizan reclamos DRAT no verificados, tiempos de espera de SAT, ni estados de resolvedores de punto flotante como premisas para los teoremas, asegurando que las afirmaciones matemáticas descansen enteramente sobre datos finitos explícitos y aritmética exacta.

Más como este