{
  "id": "1603.05888",
  "version": "v1",
  "published": "2016-03-18T14:50:42.000Z",
  "updated": "2016-03-18T14:50:42.000Z",
  "title": "Sidorenko's conjecture, colorings and independent sets",
  "authors": [
    "Péter Csikvári",
    "Zhicong Lin"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\hom(H,G)$ denote the number of homomorphisms from a graph $H$ to a graph $G$. Sidorenko's conjecture asserts that for any bipartite graph $H$, and a graph $G$ we have $$\\hom(H,G)\\geq v(G)^{v(H)}\\left(\\frac{\\hom(K_2,G)}{v(G)^2}\\right)^{e(H)},$$ where $v(H),v(G)$ and $e(H),e(G)$ denote the number of vertices and edges of the graph $H$ and $G$, respectively. In this paper we prove Sidorenko's conjecture for certain special graphs $G$: for the complete graph $K_q$ on $q$ vertices, for a $K_2$ with a loop added at one of the end vertices, and for a path on $3$ vertices with a loop added at each vertex. These cases correspond to counting colorings, independent sets and Widom-Rowlinson colorings of a graph $H$. For instance, for a bipartite graph $H$ the number of $q$-colorings $\\textrm{ch}(H,q)$ satisfies $$\\textrm{ch}(H,q)\\geq q^{v(H)}\\left(\\frac{q-1}{q}\\right)^{e(H)}.$$ In fact, we will prove that in the last two cases (independent sets and Widom-Rowlinson colorings) the graph $H$ does not need to be bipartite. In all cases, we first prove a certain correlation inequality which implies Sidorenko's conjecture in a stronger form.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-03-18T14:50:42.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35"
    ],
    "keywords": [
      "independent sets",
      "bipartite graph",
      "widom-rowlinson colorings",
      "implies sidorenkos conjecture",
      "sidorenkos conjecture asserts"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160305888C"
    }
  }
}