Muchos problemas combinatorios vienen en familias parametrizadas por dos números naturales que juegan papeles distintos. Por ejemplo, ¿cuantas particiones hay del número n en q partes? ¿Cuántas coloraciones propias hay del grafo de un retículo de q x q con n colores? ¿Cuantos conjuntos hay de q números entre 1 y n tales que todas las diferencias de pares de los números son distintos? ¿Cuántas formas hay de colocar q reinas en una tabla de n x n tal que ningún par de reinas se atacan entre sí?
Chaiken, Hanusa, y Zaslavsky demostraron que la respuesta a la última pregunta es una función del siguiente estilo. Para cada valor fijo de q, es un cuasi-polinomio (es decir, oscila periódicamente entre finitos polinomios) en n de grado 2q. Y para cada r fijo, ¡el coeficiente de n^{2q - r} también es un polinomio en q!
Definimos una clase de funciones de este estilo que llamamos polinomios o cuasi-polinomios de dos niveles. Mostramos varias propiedades algebraicas de esta clase, y usamos dichas propiedades para demostrar que la respuesta a cada problema anteriormente mencionado es un polinomio de dos niveles. Estos resultados son un trabajo conjunto con Kevin Woods.
El modelo de Kronig-Penney, basado en operadores de Schrödinger con interacciones delta, es una herramienta fundamental para describir electrones en potenciales periódicos, como los que aparecen en sólidos cristalinos, redes artificiales y sistemas de átomos fríos en redes ópticas. En esta charla, exploramos la formulación matemática de estos operadores, con énfasis en su espectro, y presentamos algunos resultados recientes de los problemas relacionados a estas interacciones singulares.
La anti-unificación, o generalización, es el problema de determinar los puntos en común entre dos expresiones. Es un problema dual al problema de unificación y es crucial en raciocinio ecuacional. Sus aplicaciones incluyen la búsqueda de regularidades en código y la detección de elementos comunes en datos. Los algoritmos de anti-unificación se utilizan en herramientas industriales dedicadas a computación paralela eficiente, detección de plagio y corrección dinámica de código. Esta charla explicará el problema de anti-unificación y presentará una verificación mecánica de un algoritmo sintáctico de anti-unificación mecanizado en el probador de teoremas interactivo PVS.