{
  "id": "1910.11048",
  "version": "v1",
  "published": "2019-10-24T12:22:28.000Z",
  "updated": "2019-10-24T12:22:28.000Z",
  "title": "Turán number of bipartite graphs with no $K_{t,t}$",
  "authors": [
    "Benny Sudakov",
    "István Tomon"
  ],
  "comment": "8 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The extremal number of a graph $H$, denoted by $\\mbox{ex}(n,H)$, is the maximum number of edges in a graph on $n$ vertices that does not contain $H$. The celebrated K\\H{o}v\\'ari-S\\'os-Tur\\'an theorem says that for a complete bipartite graph with parts of size $t\\leq s$ the extremal number is $\\mbox{ex}(K_{s,t})=O(n^{2-1/t})$. It is also known that this bound is sharp if $s>(t-1)!$. In this paper, we prove that if $H$ is a bipartite graph such that all vertices in one of its parts have degree at most $t$, but $H$ contains no copy of $K_{t,t}$, then $\\mbox{ex}(n,H)=o(n^{2-1/t})$. This verifies a conjecture of Conlon, Janzer and Lee.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-10-24T12:22:28.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "turán number",
      "extremal number",
      "complete bipartite graph",
      "theorem says",
      "maximum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}