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) > v(G)[superscript v(H)](hom(K[subscript 2], G)[superscript e(H)]/v(G)[superscript 2], where v(H), v(G) and e(H), e(G) deno...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
European Mathematical Information Service (EMIS)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110146 https://orcid.org/0000-0002-1594-9206 |
| 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) > v(G)[superscript v(H)](hom(K[subscript 2], G)[superscript e(H)]/v(G)[superscript 2], 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 K2 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 configurations of a graph H. For instance, for a bipartite graph H the number of q-colorings ch(H, q) satisfies ch(H, q) ≥ q[superscript v(H)](q − 1/q)[superscript e(H)].
In fact, we will prove that in the last two cases (independent sets and WidomRowlinson configurations) 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. |
|---|