{
  "id": "2103.03217",
  "version": "v1",
  "published": "2021-03-04T18:44:24.000Z",
  "updated": "2021-03-04T18:44:24.000Z",
  "title": "Flattening rank and its combinatorial applications",
  "authors": [
    "David Munhá Correia",
    "Benny Sudakov",
    "István Tomon"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a $d$-dimensional tensor $T:A_1\\times\\dots\\times A_d\\rightarrow \\mathbb{F}$ (where $\\mathbb{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\\times\\dots\\times A_{i-1}\\times A_{i+1}\\times\\dots\\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)$. A tensor $T:A^{d}\\rightarrow\\mathbb{F}$ is called semi-diagonal, if $T(a,\\dots,a)\\neq 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}\\rightarrow\\mathbb{F}$ is semi-diagonal, then $\\text{mfrank}(T)\\geq \\frac{|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 $\\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)\\binom{rt}{r}$. This improves previous results of Alon and Glebov, Sudakov and Szab\\'o.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-03-04T18:44:24.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "combinatorial applications",
      "uniform multi-hypergraph",
      "dimensional tensor",
      "celebrated frankl-wilson theorem",
      "forbidden intersections"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}