Flattening rank and its combinatorial applications
OPEN ACCESS
Loading...
Author / Producer
Date
2021-09-15
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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ó.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
625
Pages / Article No.
113 - 125
Publisher
Elsevier
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Tensor; Rank; Algebraic methods; Extremal problems
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
02500 - Forschungsinstitut für Mathematik / Institute for Mathematical Research
Notes
Funding
196965 - Problems in Extremal and Probabilistic Combinatorics (SNF)