Sidorenko's conjecture, colorings and independent sets (Q510305)

Summary: 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)\geqslant 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 \(\mathrm{ch}(H,q)\) satisfies \[ \mathrm{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.