{
  "id": "1907.11909",
  "version": "v1",
  "published": "2019-07-27T13:47:54.000Z",
  "updated": "2019-07-27T13:47:54.000Z",
  "title": "Some tight lower bounds for Turán problems via constructions of multi-hypergraphs",
  "authors": [
    "Zixiang Xu",
    "Tao Zhang",
    "Gennian Ge"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Recently, several Tur\\'{a}n type problems were solved by the powerful random algebraic method. In this paper, we use this tool to construct various multi-hypergraphs to obtain some tight lower bounds and determine the dependence on some specified large constant for different Tur\\'{a}n problems. We investigate three important objects including complete $r$-partite $r$-uniform hypergraphs, complete bipartite hypergraphs and Berge theta hypergraphs. More specifically, for complete $r$-partite $r$-uniform hypergraphs, we show that if $s_{r}$ is sufficiently larger than $s_{1},s_{2},\\ldots,s_{r-1},$ then $$ \\text{ex}_{r}(n,K_{s_{1},s_{2},\\ldots,s_{r}}^{(r)})=\\Theta(s_{r}^{\\frac{1}{s_{1}s_{2}\\cdots s_{r-1}}}n^{r-\\frac{1}{s_{1}s_{2}\\cdots s_{r-1}}}).$$ For complete bipartite hypergraphs, we prove that if $s$ is sufficiently larger than $t,$ we have $$ \\text{ex}_{r}(n,K_{s,t}^{(r)})=\\Theta(s^{\\frac{1}{t}}n^{r-\\frac{1}{t}}).$$ In particular, our results imply that the famous K\\\"{o}vari-S\\'{o}s-Tur\\'{a}n's upper bound $\\text{ex}(n,K_{s,t})=O(t^{\\frac{1}{s}}n^{2-\\frac{1}{s}})$ is tight when $t$ is large.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-07-27T13:47:54.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C65",
      "05C80"
    ],
    "keywords": [
      "tight lower bounds",
      "turán problems",
      "complete bipartite hypergraphs",
      "multi-hypergraphs",
      "uniform hypergraphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}