Sidorenko's Conjecture, Colorings and Independent Sets

[摘要] 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 $

[学科分类] 离散数学和组合数学

[关键词] Colorings;Independent sets;Large girth graphs