Flattening rank and its combinatorial applications

Given a $d$-dimensional tensor $T:A_1\times\dots\times A_d\rightarrow $\mathbb{F}$$(where$$\mathbb{F}$$isafield),the$i$-flatteningrankof$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)$\mathrm{.}Atensor$T:A^{d}\rightarrow$\mathbb{F}$$ is called semi-diagonal, if $T(a,\dots ,a)\mathrm{\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{\mathrm{\mid }A\mathrm{\mid }}{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{}{}{0px}{}{rt}{r}\right)$. This improves previous results of Alon and Glebov, Sudakov and Szab'o.