Session I.3 - Graph Theory and Combinatorics
Wednesday, June 14, 15:30 ~ 16:00
The fragmentation technique on the ranks of tensors and its applications.
Thomas Karam
University of Oxford, United Kingdom - This email address is being protected from spambots. You need JavaScript enabled to view it.
The notion of rank on matrices has been extended in several ways to notions of rank on higher-dimensional tensors. Well-known among these generalisations are in particular the tensor rank, the slice rank, and the partition rank. The most relevant notion of rank heavily depends on one's motivation and context, and in particular no notion of rank is viewed as a canonical generalisation of matrix rank. However, the definitions of many of them (and in particular the three which we have previously mentioned) can be unified, as follows. For $d \ge 2$ an integer and $\mathrm{R}$ a non-empty set of partitions of $[d]$ we say that an order-$d$ tensor $T$ has $\mathrm{R}$-rank at most $1$ if we can write the entries of $T$ as a product of functions \[T(x_1, \dots, x_d) = \prod_{I \in P} a_I(x_i: i \in I)\] for some partition $P \in \mathrm{R}$. We then define the $\mathrm{R}$-rank of $T$ as the smallest nonnegative integer $k$ such that we can write $T$ as a sum of $k$ tensors with $\mathrm{R}$-rank at most $1$. For instance, the tensor rank corresponds to the case where $\mathrm{R}$ contains only the discrete partition of $[d]$, whereas the partition rank allows $\mathrm{R}$ to contain all bipartitions of $[d]$.
Rather than studying any of these notions of rank individually, we will heavily involve the relations between them. We will focus on and answer the following question: given positive integers $d$,$s$ and some sets of partitions $\mathrm{R}_1, \dots, \mathrm{R}_s$ of $[d]$, for which sets $\mathrm{R}$ of partitions of $[d]$ is it true that if an order-$d$ tensor has bounded $\mathrm{R}_i$-rank for each $i=1,\dots,s$, then it must have bounded $\mathrm{R}$-rank ? Settling the case $s=1$ will involve making some progress on a related question of Naslund. Then, in the case $s=2$ (which suffices to conclude for all $s$) the converse implication will involve its own difficulties.
In both parts, the central tool involved will be a fragmentation result allowing us to pass from a statement that the $\mathrm{R}$-rank of a tensor $T$ is bounded for some set $\mathrm{R}$ to a statement that the $\mathrm{R}'$-rank of $T$ is bounded, for some set $\mathrm{R}'$ corresponding to a notion of rank which is finer than that of $\mathrm{R}$, under the assumption that in some direction, all slices of $T$ with some fixed lower dimension than $d$ have bounded partition rank. For instance, it will say that if an order-$3$ tensor $T$ is such that all its order-$2$ slices have bounded rank, then it is equivalent to say that its tensor rank and slice rank of $T$ are bounded.