{
  "id": "1310.4383",
  "version": "v3",
  "published": "2013-10-16T14:03:25.000Z",
  "updated": "2014-06-05T20:32:02.000Z",
  "title": "Two Approaches to Sidorenko's Conjecture",
  "authors": [
    "Jeong Han Kim",
    "Choongbum Lee",
    "Joonkyung Lee"
  ],
  "comment": "20 pages, 2 figures",
  "categories": [
    "math.CO",
    "math.FA"
  ],
  "abstract": "Sidorenko's conjecture states that for every bipartite graph $H$ on $\\{1,\\cdots,k\\}$, $\\int \\prod_{(i,j)\\in E(H)} h(x_i, y_j) d\\mu^{|V(H)|} \\ge \\left( \\int h(x,y) \\,d\\mu^2 \\right)^{|E(H)|}$ holds, where $\\mu$ is the Lebesgue measure on $[0,1]$ and $h$ is a bounded, non-negative, symmetric, measurable function on $[0,1]^2$. An equivalent discrete form of the conjecture is that the number of homomorphisms from a bipartite graph $H$ to a graph $G$ is asymptotically at least the expected number of homomorphisms from $H$ to the Erd\\H{o}s-R\\'{e}nyi random graph with the same expected edge density as $G$. In this paper, we present two approaches to the conjecture. First, we introduce the notion of tree-arrangeability, where a bipartite graph $H$ with bipartition $A \\cup B$ is tree-arrangeable if neighborhoods of vertices in $A$ have a certain tree-like structure. We show that Sidorenko's conjecture holds for all tree-arrangeable bipartite graphs. In particular, this implies that Sidorenko's conjecture holds if there are two vertices $a_1, a_2$ in $A$ such that each vertex $a \\in A$ satisfies $N(a) \\subseteq N(a_1)$ or $N(a) \\subseteq N(a_2)$, and also implies a recent result of Conlon, Fox, and Sudakov \\cite{CoFoSu}. Second, if $T$ is a tree and $H$ is a bipartite graph satisfying Sidorenko's conjecture, then it is shown that the Cartesian product $T \\Box H$ of $T$ and $H$ also satisfies Sidorenko's conjecture. This result implies that, for all $d \\ge 2$, the $d$-dimensional grid with arbitrary side lengths satisfies Sidorenko's conjecture.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2014-06-05T20:32:02.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "sidorenkos conjecture holds",
      "approaches",
      "arbitrary side lengths satisfies sidorenkos",
      "side lengths satisfies sidorenkos conjecture",
      "bipartite graph satisfying sidorenkos conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1310.4383K"
    }
  }
}