Sidorenko's Conjecture, Colorings and Independent Sets

Let (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(H,G)≥ v(G)v(H)((K₂,G)/v(G)²)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 Kq on q vertices, for a K₂ 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 ch(H,q) satisfiesch(H,q)≥ qv(H)(q-1/q)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.