Moment Methods for Uniform Average Mixing on Strongly Regular Graphs

Resumen Técnico: Métodos de Momentos para la Mezcla Promedio Uniforme en Grafos Fuertemente Regulares

Planteamiento del Problema
El artículo investiga la existencia de la Mezcla Promedio Uniforme (UAM, por sus siglas en inglés) para caminatas cuánticas de tiempo continuo en grafos fuertemente regulares (SRG) conectados y no completos. La UAM se define por la existencia de una medida de probabilidad de Borel $\mu$ en $[0, \infty)$ tal que la matriz de mezcla promedio en el tiempo es igual a la matriz uniforme $\frac{1}{n}J$, donde $n$ es el número de vértices. Específicamente, el estudio busca determinar qué SRG admiten tal ley y caracterizar la naturaleza de estas leyes (por ejemplo, si pueden realizarse mediante densidades acotadas, medidas atómicas finitas o tiempos de observación únicos). El trabajo aborda la perspectiva de los momentos espectrales de los promedios de las caminatas cuánticas, un tema que anteriormente se planteaba como un problema abierto en la literatura.

Metodología
El autor emplea un enfoque de momentos espectrales, reduciendo el problema de dimensión infinente de encontrar una ley de tiempo a un problema de momentos de dimensión finita.

1. Reducción Espectral: Utilizando la estructura algebraica de los SRG (específicamente la identidad $A^2 = (\lambda - \nu)A + (k - \nu)I + \nu J$), la matriz de mezcla $M(t)$ se expresa en términos de tres momentos de coseno correspondientes a los autovalores restringidos del grafo.
2. Restricciones Afines: Se demuestra que la condición para la UAM es equivalente a satisfacer dos restricciones afines sobre estos tres momentos, lo que define una "línea de momentos" en $\mathbb{R}^3$.
3. Herramientas Geométicas y Algebraicas:
   • Teoremas de tipo Carathéodory: El autor utiliza refinamientos del teorema de Carathéodory para demostrar que cualquier matriz de mezcla promedio puede ser realizada por como máximo dos tiempos de observación (átomos), independientemente de la ley de tiempo original.
   • Problemas de Momentos: Para grafos con espectros no enteros, el autor construye densidades de tiempo explícitas, acotadas y de soporte compacto utilizando polinomios de Fejér e inversión de matrices de Gram. Para espectros enteros, proporciona condiciones necesarias y suficientes utilizando matrices semidefinidas de Toeplitz y Hankel finitas.
   • Matrices de Hadamard Complejas: Un paso clave consiste en vincular la existencia de un punto en la línea de momentos con una matriz de Gram semidefinida positiva a la existencia de matrices de Hadamard complejas dentro del álgebra de Bose–Mesner del grafo. Esto permite una clasificación de los conjuntos de parámetros sin depender de clasificaciones previas o cálculos computacionales.

Contribuciones Clave y Resultados

• Reducción a Dos Tiempos: El artículo demuestra que para cualquier SRG conectado y no completo, si existe una ley de UAM, esta puede realizarse mediante una medida discreta con como máximo dos átomos (tiempos de observación). Esto simplifica la búsqueda de la UAM al verificar pares específicos de tiempos.
• Construcciones Explícitas:
  • Para SRG con autovalores restringidos no enteros (grafos de conferencia de orden no cuadrado), el autor construye una densidad de probabilidad acotada explícita con soporte en un intervalo finito $[0, T]$.
  • Para espectros enteros, se proporciona un criterio semidefinido finito (de forma Toeplitz/Hankel) para determinar la existencia.
• Clasificación Completa: El artículo determina todos los SRG que admiten UAM. Aparte de los grafos con Mezcla Uniforme Instantánea (IUM) y los grafos de conferencia de orden no cuadrado, la UAM es admitida solo por:
  1. Grafos (o sus complementos) con parámetros $(4\theta^2 + 4\theta + 2, 2\theta^2 + \theta, \theta^2 - 1, \theta^2)$ para $\theta \ge 1$.
  2. Grafos (o sus complementos) con parámetros $(4\theta^2 - 1, 2\theta^2, \theta^2, \theta^2)$ para $\theta \ge 2$.
  • El grafo de Petersen y su complemento son identificados como los miembros más pequeños de estas familias.
• Densidad vs. Átomos: Se establece una dicotomía: un grafo con UAM admite una densidad de tiempo acotada si y solo si no admite mezcla uniforme instantánea. Si existe IUM, la ley de UAM debe concentrarse en un conjunto discreto.
• Corrección de Trabajo Previo: El artículo corrige la clasificación de la Mezcla Uniforme Instantánea en SRG de Godsil, Mullin y Roy. Identifica que sus condiciones de signo excluyeron incorrectamente al hipercubo de 5 dimensiones partido (que mezcla uniformemente en $t=\pi/4$) e incluyeron incorrectamente los parámetros $(36, 14, 4, 6)$, para los cuales no existe una ley de UAM. La clasificación corregida se basa en la divisibilidad de $n$ por 16 y la existencia de matrices de Hadamard específicas.

Significancia y Reivindicaciones
El artículo afirma proporcionar una clasificación completa y autónoma de los grafos fuertemente regulares que admiten mezcla promedio uniforme. Su significancia radica en:

• Unificación: Unifica el estudio de la UAM con la teoría de las matrices de Hadamard complejas en el álgebra de Bose–Mesner, ofreciendo una prueba corta y elemental de la clasificación de Chan para tales matrices en este contexto.
• Exactitud: Proporciona criterios exactos y no asintóticos (condiciones semidefinidas finitas) para el caso de espectro entero y construcciones explícitas para el caso no entero.
• Resolución de Problemas Abiertos: Responde a problemas abiertos específicos sobre la racionalidad de los tiempos de mezcla y las condiciones espectrales para la IUM dentro de la clase de los SRG.
• Rigor Metodológico: La clasificación se deriva sin depender de cálculos computacionales o clasificaciones previas, utilizando únicamente desigualdades elementales y la teoría de momentos.

El autor enfatiza que los resultados son definitivos para la clase de los SRG conectados y no completos, estableciendo límites precisos entre los grafos que admiten densidades continuas, aquellos que requieren leyes atómicas discretas y aquellos que no admiten ninguna mezcla promedio uniforme.