Flattening rank and its combinatorial applications

2021 
Abstract Given a d-dimensional tensor T : A 1 × … × A d → F (where 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 × … × A i − 1 × A i + 1 × … × A d and whose entries are given by the corresponding values of T. The max-flattening rank of T is defined as mfrank ( T ) = max i ∈ [ d ] ⁡ frank i ( T ) . A tensor T : A d → F is called semi-diagonal, if T ( a , … , a ) ≠ 0 for every a ∈ A , and T ( a 1 , … , a d ) = 0 for every a 1 , … , a d ∈ A that are all distinct. In this paper we prove that if T : A d → F 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 color class is a matching of size t, then H contains a rainbow matching of size t provided z > ( t − 1 ) ( r t r ) . This improves previous results of Alon and Glebov, Sudakov, and Szabo.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    11
    References
    2
    Citations
    NaN
    KQI
    []