Sidorenko's conjecture, colorings and independent sets
Author(s)
Csikvari, Peter; Lin, Zhicong
DownloadSidorenko's conjecture.pdf (280.3Kb)
PUBLISHER_POLICY
Publisher Policy
Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use.
Terms of use
Metadata
Show full item recordAbstract
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.
Date issued
2017-01Department
Massachusetts Institute of Technology. Department of MathematicsJournal
Electronic Journal of Combinatorics
Publisher
European Mathematical Information Service (EMIS)
Citation
Csikvari, Peter and Zhicong Lin. "Sidorenko's conjecture, colorings and independent sets." The Electronic Journal of Combinatorics 24.1 (2017): n. pag.
Version: Final published version