Flattening rank and its combinatorial applications

Abstract

Given a d-dimensional tensor T:A ×…×A →F (where F is a field), the i-flattening rank of T is the rank of the matrix whose rows are indexed by A , columns are indexed by B =A ×…×A ×A ×…×A and whose entries are given by the corresponding values of T. The max-flattening rank of T is defined as mfrank(T)=max frank (T). A tensor T:A →F is called semi-diagonal, if T(a,…,a)≠0 for every a∈A, and T(a ,…,a )=0 for every a ,…,a ∈A that are all distinct. In this paper we prove that if T:A →F is semi-diagonal, then mfrank(T)≥[Formula presented], 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 H are colored with z colors such that each color class is a matching of size t, then H contains a rainbow matching of size t provided z>(t−1)(rtr). This improves previous results of Alon and Glebov, Sudakov, and Szabó.