Sidorenko's conjecture, colorings and independent sets

Péter Csikvári¹ ; Zhicong Lin²

¹Massachusetts Institute of Technology, Department of Mathematics, Cambridge MA 02139 & Eötvös Loránd University, Department of Computer Science, H-1117 Budapest, Pázmány Péter sétány 1/C, Hungary
²School of Science, Jimei University, Xiamen 361021, P.R. China & CAMP, National Institute for Mathematical Sciences, Daejeon 305-811, Republic of Korea

The electronic journal of combinatorics, Tome 24 (2017) no. 1

Résumé

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 $\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.

Détail

DOI : 10.37236/6019

Classification : 05C15, 05C69
Mots-clés : colorings, independent sets, large girth graphs