{
  "id": "1004.4236",
  "version": "v2",
  "published": "2010-04-23T22:35:25.000Z",
  "updated": "2010-06-08T07:43:50.000Z",
  "title": "An approximate version of Sidorenko's conjecture",
  "authors": [
    "David Conlon",
    "Jacob Fox",
    "Benny Sudakov"
  ],
  "comment": "12 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A beautiful conjecture of Erd\\H{o}s-Simonovits and Sidorenko states that if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same order and edge density. This conjecture also has an equivalent analytic form and has connections to a broad range of topics, such as matrix theory, Markov chains, graph limits, and quasirandomness. Here we prove the conjecture if H has a vertex complete to the other part, and deduce an approximate version of the conjecture for all H. Furthermore, for a large class of bipartite graphs, we prove a stronger stability result which answers a question of Chung, Graham, and Wilson on quasirandomness for these graphs.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-06-08T07:43:50.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05D40",
      "39B62"
    ],
    "keywords": [
      "approximate version",
      "sidorenkos conjecture",
      "bipartite graph",
      "edge density",
      "equivalent analytic form"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1004.4236C"
    }
  }
}