Sidorenko's conjecture, colorings and independent sets

Abstract

Let $\mathrm{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 $$\mathrm{hom}(H,G)\ge v(G{)}^{v(H)}{\left(\frac{\mathrm{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 $\text{ch}(H,q)$ satisfies $$\text{ch}(H,q)\ge 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.

Two references added and Remark 2.1 is expanded

References in corpus (2)

• On the logarithimic calculus and Sidorenko's conjecture
• Subgraph densities in signed graphons and the local Sidorenko conjecture

Cited by in corpus (1)

• Extremal regular graphs: the case of the infinite regular tree