Containments of Tensor Network Varieties

Resumen Técnico: Contenciones de Variedades de Redes de Tensores

Planteamiento del Problema
El artículo aborda la pregunta fundamental de la contención entre variedades de redes de tensores. Dados dos formatos de tensores codificados mediante árboles binarios, los autores investigan si el conjunto de todos los tensores representables por una red (la variedad) está contenido dentro del conjunto representable por otra. Este problema generaliza la "Conjetura de Hackbusch", que fue resuelta previamente para pares específicos de árboles (árboles jerárquicos y de vía de tren) por Buczyńska et al. [BBM15]. Los autores pretenden establecer un marco general para comparar árboles binarios arbitrarios, prescindiendo de las incrustaciones planas, y cuantificar el "costo" de la contención. Específicamente, buscan determinar cuánto deben escalarse los parámetros de dimensión (el "impulso" o boost) de una red con respecto a otra para asegurar que la contención se cumpla.

Metodología
Los autores emplean un enfoque combinatorio basado en la estructura de los árboles binarios completos con raíz y las propiedades de sus estados de redes de tensores asociados (TNS).

1. Definiciones y Marco de Trabajo:

   • Redes de Tensores: Definidas como una terna $(T, \mathcal{V}, f)$, donde $T$ es un árbol binario completo, $\mathcal{V}$ es una familia de espacios vectoriales en las hojas, y $f$ es un vector de dimensión que asigna dimensiones a los subespacios en cada vértice.
   • Variedades: La variedad $TNS(T)$ es el lugar de tensores que satisfacen restricciones de rango en cada vértice, definida mediante subespacios lineales $U_v$ tales que $U_v \subseteq U_{v_1} \otimes U_{v_2}$.
   • Descripción Exterior: Los autores utilizan contracciones de tensores para caracterizar la variedad mediante condiciones de rango en mapas de "aplanamiento" (flattening). Un tensor pertenece a $TNS(T)$ si el rango de su contracción a través de cualquier división $(\downarrow v | \uparrow v)$ está acotado por $f(v)$.
   • Conjuntos Doad: Una herramienta combinatoria crucial introducida es el "conjunto doad" (hojas descendientes o anti-descendentes), denotado como $DOAD(T)$. Estos son subconjuntos de hojas $S$ tales que $S = \downarrow v$ o $S = \uparrow v$ para algún vértice $v$.

2. Criterios de Contención:

   • Contención Trivial: Una red $T$ está trivialmente contenida en $T'$ si cada conjunto doad de $T'$ puede ser cubierto por conjuntos doad de $T$ de tal manera que el producto de los parámetros de dimensión de los conjuntos de cobertura en $T$ sea menor o igual al parámetro en $T'$.
   • Contención Asintótica (Lema 2.11): Los autores establecen que si cada conjunto doad (o su complemento) de $T'$ puede ser cubierto por como máximo $c_0$ conjuntos doad de $T$, entonces para un factor de escala $r$ suficientemente grande, $TNS(rT) \subseteq TNS(r^{c_0}T')$. Esto conduce a la definición del exponente de contención.

3. El Exponente de Contención:

   • Definido como el número más pequeño $E$ tal que para todos los vectores de dimensión y para un $r$ suficientemente grande, $TNS(rT) \subseteq TNS(r^c T')$ se cumple para todo $c > E$.
   • Límites Combinatorios: Los autores derivan cotas basadas en la estructura de un orden parcial (poset) de los árboles. El Teorema 3.3 proporciona una fórmula para un exponente basado en el número de elementos máximos en sub-posets específicos derivados de las estructuras de los árboles.
   • Árboles Planos: Para árboles planos (donde las hojas están ordenadas), los autores explotan el hecho de que los conjuntos doad corresponden a intervalos. Introducen la "altura" y la "altura dual" de los vértices para derivar cotas específicas para la contención relativa al árbol de vía de tren ($TT_n$) y entre árboles planos arbitrarios (Teorema 4.4, Corolario 4.7).

4. Enfoque Computacional:

   • Los autores implementaron un algoritmo para calcular estos exponentes para un número pequeño de hojas ($n \le 8$).
   • Utilizaron el paquete de SageMath BinaryTree para generar todos los árboles binarios completos.
   • Para valores de $n$ más grandes, donde la búsqueda exhaustiva de coberturas de conjuntos doad resulta inviable, formularon un Programa Lineal Entero (ILP) para minimizar el número de conjuntos doad requeridos para cubrir las divisiones del árbol objetivo.

Contribuciones Claves y Resultados

• Generalización de la Conjetura de Hackbusch: El artículo extiende el análisis de contención desde pares específicos de árboles (jerárquico frente a vía de tren) hacia cualquier par de árboles binarios.
• Existencia y Definición de Exponentes de Contención: Los autores prueban la existencia de un exponente de contención finito para cualquier par de árboles y lo definen como una medida del escalamiento de parámetros entre diferentes formatos de redes de tensores.
• Límites Combinatorios:
  • Se proporciona una cota superior general de $\lfloor n/2 \rfloor$ (Proposición 3.2).
  • Se presenta una cota más ajustada basada en la estructura de orden parcial de los árboles en el Teorema 3.3.
  • Se derivan cotas específicas para árboles planos utilizando las alturas de los vértices, mostrando que el exponente de un árbol $T$ en el árbol de vía de tren $TT_n$ está relacionado con el máximo de $\min\{h_\ell, h^*_{\ell+1}\}$ (Corolario 4.5).
• Implementación Algorítmica: Los autores proporcionan un algoritmo y una formulación de ILP para calcular estos exponentes. Reportan sobre una búsqueda exhaustiva para árboles con hasta $n=8$ hojas, con resultados detallados recopilados en un conjunto de datos separado [GM25].
• No Agudeza de las Cotas: El artículo demuestra mediante ejemplos (por ejemplo, la Figura 6) que las cotas combinatorias derivadas no son necesariamente ajustadas (sharp). En algunos casos, el exponente de contención real es significativamente menor que la cota superior teórica proporcionada por las fórmulas de orden parcial o de altura.

Significancia y Reivindicaciones
Los autores posicionan este trabajo como un "primer paso" hacia una mejor comprensión de las contenciones de redes de tensores. Afirman haber:

1. Propuesto un marco general para la cuestión de la contención que se aplica a árboles binarios de forma arbitraria.
2. Introducido una nueva medida, el exponente de contención, que cuantifica la relación entre diferentes formatos de redes de tensores.
3. Proporcionado tanto límites teóricos (vía estructuras de orden parcial y programación entera) como datos experimentales para $n$ pequeño.

El artículo concluye de manera modesta, señalando que aunque las cotas son útiles, no siempre son ajustadas. Los autores identifican preguntas abiertas sobre si las cotas superiores del Lema 2.11 son siempre exactas y si las soluciones duales de la relajación de programación lineal pueden utilizarse para construir tensores que den límites inferiores para los exponentes. Sugieren que el exponente de contención ofrece una nueva medida de distancia no simétrica para los árboles, lo que justifica una mayor comparación con las métricas de árboles existentes en la literatura.