2021/03/04 by Correia, David Munhá, Sudakov, Benny, Tomon, István
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2103.03217
Given a d-dimensional tensor T:A1×…× Ad→ \mathbbF (where \mathbbF is a field), the i-flattening rank of T is the rank of the matrix whose rows are indexed by Ai, columns are indexed by Bi=A1×…× Ai-1× Ai+1×…× Ad and whose entries are given by the corresponding values of T. The max-flattening rank of T is defined as mfrank(T)=maxi∈ [d]franki(T). A tensor T:Ad→\mathbbF is called semi-diagonal, if T(a,…,a)≠ 0 for every a∈ A, and T(a1,…,ad)=0 for every a1,…,ad∈ A that are all distinct. In this paper we prove that if T:Ad→\mathbbF is semi-diagonal, then mfrank(T)≥ (|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 H are colored with z colors such that each colorclass is a matching of size t, then H contains a rainbow matching of size t provided z>(t-1)\binomrtr. This improves previous results of Alon and Glebov, Sudakov and Szabó.