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 |
| _version_ | 1826196491528568832 |
|---|---|
| author | Csikvari, Peter Lin, Zhicong |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Csikvari, Peter Lin, Zhicong |
| author_sort | Csikvari, Peter |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T10:27:48Z |
| format | Article |
| id | mit-1721.1/110146 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:27:48Z |
| publishDate | 2017 |
| publisher | European Mathematical Information Service (EMIS) |
| record_format | dspace |
| spelling | mit-1721.1/1101462022-09-27T09:39:02Z Sidorenko's conjecture, colorings and independent sets Csikvari, Peter Lin, Zhicong Massachusetts Institute of Technology. Department of Mathematics Csikvari, Peter 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. National Science Foundation (U.S.) (Grant DMS-1500219) European Research Council (Consolidator Grant 648017) Hungary. National Research, Development and Innovation Offfice (Grant NN114614) Hungary. National Research, Development and Innovation Offfice (Grant K109684) Hungarian Academy of Sciences 2017-06-21T18:31:37Z 2017-06-21T18:31:37Z 2017-01 2016-03 Article http://purl.org/eprint/type/JournalArticle http://hdl.handle.net/1721.1/110146 Csikvari, Peter and Zhicong Lin. "Sidorenko's conjecture, colorings and independent sets." The Electronic Journal of Combinatorics 24.1 (2017): n. pag. https://orcid.org/0000-0002-1594-9206 en_US http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p2/pdf Electronic Journal of Combinatorics 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. application/pdf European Mathematical Information Service (EMIS) Electronic Journal of Combinatorics |
| spellingShingle | Csikvari, Peter Lin, Zhicong Sidorenko's conjecture, colorings and independent sets |
| title | Sidorenko's conjecture, colorings and independent sets |
| title_full | Sidorenko's conjecture, colorings and independent sets |
| title_fullStr | Sidorenko's conjecture, colorings and independent sets |
| title_full_unstemmed | Sidorenko's conjecture, colorings and independent sets |
| title_short | Sidorenko's conjecture, colorings and independent sets |
| title_sort | sidorenko s conjecture colorings and independent sets |
| url | http://hdl.handle.net/1721.1/110146 https://orcid.org/0000-0002-1594-9206 |
| work_keys_str_mv | AT csikvaripeter sidorenkosconjecturecoloringsandindependentsets AT linzhicong sidorenkosconjecturecoloringsandindependentsets |