Resumen de platica

Primero las buenas nuevas: En trabajo conjunto con Claudia de la Cruz,hemos logrado mejorar cuatro cotas inferiores para el orden de jaulas.

n(8,5) >=68 (antes 67), n(5,7)>= 110 (antes 106) y n(4,9)>= 165 (antes 161) 

y n(3,14)>= 262 (antes 260)

Esto lo hemos logrado computacionalmente usando nuevas técnicas de búsqueda en espacios combinatorios. La principal innovación es un nuevo algoritmo que dado un conjunto S, un entero k y un grupo de permutaciones G que actúa en S, calcula todos los k-subconjuntos de S módulo la acción del grupo G.

Este nuevo algoritmo y las demás herramientas que hemos desarrollado se pueden aplicar a un amplio espectro de problemas de búsqueda en espacios combinatorios. Por ejemplo, problemas del tipo "Encuentre una(todas las) gráfica(s) G que cumpla(n) la propiedad P". Las técnicas son especialmente útiles cuando la propiedad P se puede descomponer como una conjunción de propiedades monótonas.

Cuando la gráfica que se busca existe, ella misma es un certificado de su propia existencia. Pero cuando no existe o cuando se quiere mostrar que las soluciones encontradas son todas las que existen, siempre

existe el problema de la verificabilidad de las pruebas asistidas por computadoras. ¿Cómo estar seguros de que el cálculo realizado es correcto? El mismo problema existe con las pruebas normales, pero ciertamente es en general mucho más fácil verificar que una demostración es correcta a verificar que un código es correcto.

En nuestro caso, nuestras técnicas admiten la generación de certificados sucintos de inexistencia (o de corrección) que pueden ser verificados por programas independientes, mucho más rápidos y simples

(y por ello mucho más fáciles de verificar). Esto provee por primera vez una manera confiable de verificar los resultados conocidos de jaulas. Estas ideas sobre certificados se pueden aplicar siempre que nuestras técnicas se puedan aplicar.

Definiciones: 

Una (r,g)-jaula es una gráfica r-regular de cuello g y mínimo orden. Las jaulas siempre existen para r>=2 y g>=3.  Denotamos por n(r,g) al orden de la (r,g)-jaula. Denotamos por G+e a la gráfica obtenida de G al agregar la arista e y por G-e a la gráfica que obtenemos de G al eliminar la arista e.  Una propiedad monótona de gráficas P es una que cumple P(G) => P(G+e) o que cumple P(G) => P(G-e). Un certificado es una cadena (de símbolos) que permite verificar la corrección de una afirmación matemática. Por ejemplo, una demostración es un certificado. Una gráfica G con una propiedad P es un certificado de la existencia de tales gráficas. La idea de los certificados es que sean razonablemente cortos y fáciles de verificar, a estos les llamamos (informalmente) certificados sucintos.