Containments of Tensor Network Varieties

Technical Summary: Containments of Tensor Network Varieties

Problem Statement
The paper addresses the fundamental question of containment between tensor network varieties. Given two tensor formats encoded by binary trees, the authors investigate whether the set of all tensors representable by one network (the variety) is contained within the set representable by another. This problem generalizes the "Hackbusch Conjecture," which was previously resolved for specific pairs of trees (hierarchical and train track trees) by Buczyńska et al. [BBM15]. The authors aim to establish a general framework for comparing arbitrary binary trees, disregarding planar embeddings, and to quantify the "cost" of containment. Specifically, they seek to determine how much the dimension parameters (the "boost") of one network must be scaled relative to another to ensure containment holds.

Methodology
The authors employ a combinatorial approach rooted in the structure of full binary rooted trees and the properties of their associated tensor network states (TNS).

1. Definitions and Framework:

   • Tensor Networks: Defined as a triple $(T, \mathcal{V}, f)$, where $T$ is a full binary tree, $\mathcal{V}$ is a family of vector spaces at the leaves, and $f$ is a dimension vector assigning dimensions to subspaces at each vertex.
   • Varieties: The TNS variety $TNS(T)$ is the locus of tensors satisfying rank constraints at every vertex, defined via linear subspaces $U_v$ such that $U_v \subseteq U_{v_1} \otimes U_{v_2}$.
   • Outer Description: The authors utilize tensor contractions to characterize the variety via rank conditions on "flattening" maps. A tensor belongs to $TNS(T)$ if the rank of its contraction across any split $(\downarrow v | \uparrow v)$ is bounded by $f(v)$.
   • Doad Sets: A crucial combinatorial tool introduced is the "doad set" (descendant or anti-descendant leaves), denoted $DOAD(T)$. These are subsets of leaves $S$ such that $S = \downarrow v$ or $S = \uparrow v$ for some vertex $v$.

2. Containment Criteria:

   • Trivial Containment: A network $T$ is trivially contained in $T'$ if every doad set of $T'$ can be covered by doad sets of $T$ such that the product of the dimension parameters of the covering sets in $T$ is less than or equal to the parameter in $T'$.
   • Asymptotic Containment (Lemma 2.11): The authors establish that if every doad set (or its complement) of $T'$ can be covered by at most $c_0$ doad sets of $T$, then for sufficiently large scaling factor $r$, $TNS(rT) \subseteq TNS(r^{c_0}T')$. This leads to the definition of the containment exponent.

3. The Containment Exponent:

   • Defined as the smallest number $E$ such that for all dimension vectors and sufficiently large $r$, $TNS(rT) \subseteq TNS(r^c T')$ holds for all $c > E$.
   • Combinatorial Bounds: The authors derive bounds based on the poset structure of the trees. Theorem 3.3 provides a formula for an exponent based on the number of maximal elements in specific sub-posets derived from the tree structures.
   • Plane Trees: For plane trees (where leaves are ordered), the authors exploit the fact that doad sets correspond to intervals. They introduce "height" and "dual height" of vertices to derive specific bounds for containment relative to the train track tree ($TT_n$) and between arbitrary plane trees (Theorem 4.4, Corollary 4.7).

4. Computational Approach:

   • The authors implemented an algorithm to compute these exponents for small numbers of leaves ($n \le 8$).
   • They utilized the SageMath package BinaryTree to generate all full binary trees.
   • For larger $n$, where exhaustive search of doad set coverings becomes infeasible, they formulated an Integer Linear Program (ILP) to minimize the number of doad sets required to cover the splits of the target tree.

Key Contributions and Results

• Generalization of the Hackbusch Conjecture: The paper extends the containment analysis from specific tree pairs (hierarchical vs. train track) to any pair of binary trees.
• Existence and Definition of Containment Exponents: The authors prove the existence of a finite containment exponent for any pair of trees and define it as a measure of the parameter scaling required for containment.
• Combinatorial Bounds:
  • A general upper bound of $\lfloor n/2 \rfloor$ is provided (Proposition 3.2).
  • A tighter bound based on the poset structure of the trees is presented in Theorem 3.3.
  • Specific bounds for plane trees are derived using vertex heights, showing that the exponent for a tree $T$ in the train track tree $TT_n$ is related to the maximum of $\min\{h_\ell, h^*_{\ell+1}\}$ (Corollary 4.5).
• Algorithmic Implementation: The authors provide an algorithm and an ILP formulation to compute these exponents. They report on an exhaustive search for trees with up to $n=8$ leaves, with detailed results collected in a separate dataset [GM25].
• Non-Sharpness of Bounds: The paper demonstrates through examples (e.g., Figure 6) that the derived combinatorial bounds are not necessarily sharp. In some cases, the actual containment exponent is significantly lower than the theoretical upper bound provided by the poset or height-based formulas.

Significance and Claims
The authors position this work as a "first step" toward a better understanding of tensor network containments. They claim to have:

1. Proposed a general framework for the containment question that applies to arbitrarily shaped binary trees.
2. Introduced a new measure, the containment exponent, which quantifies the relationship between different tensor network formats.
3. Provided both theoretical bounds (via poset structures and integer programming) and experimental data for small $n$.

The paper concludes modestly, noting that while the bounds are useful, they are not always tight. The authors identify open questions regarding whether the upper bounds from Lemma 2.11 are always tight and whether dual solutions to the linear programming relaxation can be used to construct tensors that yield lower bounds for the exponents. They suggest that the containment exponent offers a new, non-symmetric distance measure for trees, warranting further comparison with existing tree metrics in the literature.