Flattening rank and its combinatorial applications

Abstract

Given a $d$-dimensional tensor $T:A_1\times \cdots \times A_d\to \mathbb{F}$ (where $\mathbb{F}$ is a field), the $i$-flattening rank of $T$ is the rank of the matrix whose rows are indexed by $A_i$, columns are indexed by $B_i=A_1\times \cdots \times A_{i-1}\times A_{i+1}\times \cdots \times A_d$ and whose entries are given by the corresponding values of $T$. The max-flattening rank of $T$ is defined as $\text{mfrank}(T)={\max }_{i\in [d]}{\text{frank}}_i(T)$. A tensor $T:A^d\to \mathbb{F}$ is called semi-diagonal, if $T(a,\dots ,a)\ne 0$ for every $a\in A$, and $T(a_1,\dots ,a_d)=0$ for every $a_1,\dots ,a_d\in A$ that are all distinct. In this paper we prove that if $T:A^d\to \mathbb{F}$ is semi-diagonal, then $\text{mfrank}(T)\ge \frac{|A|}{d-1}$, and this bound is the best possible. We give several applications of this result, including a generalization of the celebrated Frankl-Wilson theorem on forbidden intersections. Also, addressing a conjecture of Aharoni and Berger, we show that if the edges of an $r$-uniform multi-hypergraph $\mathcal{H}$ are colored with $z$ colors such that each colorclass is a matching of size $t$, then $\mathcal{H}$ contains a rainbow matching of size $t$ provided $z>(t-1)\left(\genfrac{}{}{0ex}{}{rt}{r}\right)$. This improves previous results of Alon and Glebov, Sudakov and Szabó.