A reverse Sidorenko inequality
Abstract Let H be a graph allowing loops as well as vertex and edge weights. We prove that, for every triangle-free graph G without isolated vertices, the weighted number of graph homomorphisms hom(G, H) satisfies the inequality hom(G, H) ≤ ∏[subscript uv∈E(G)] hom(K[subscript du,dv,]H)[superscri...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Science and Business Media LLC
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129980 |
| _version_ | 1826213642691936256 |
|---|---|
| author | Sah, Ashwin Sawhney, Mehtaab Stoner, David Zhao, Yufei |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Sah, Ashwin Sawhney, Mehtaab Stoner, David Zhao, Yufei |
| author_sort | Sah, Ashwin |
| collection | MIT |
| description | Abstract
Let H be a graph allowing loops as well as vertex and edge weights. We prove that, for every triangle-free graph G without isolated vertices, the weighted number of graph homomorphisms hom(G, H) satisfies the inequality
hom(G, H) ≤ ∏[subscript uv∈E(G)] hom(K[subscript du,dv,]H)[superscript 1/(dudv)], where d[subscript u] denotes the degree of vertex u in G. In particular, one has hom(G,H)[superscript 1/|E(G)|] ≤ hom (K[subscript d,d,]H)[superscript 1/d[superscript 2]] for every d-regular triangle-free G. The triangle-free hypothesis on G is best possible. More generally, we prove a graphical Brascamp–Lieb type inequality, where every edge of G is assigned some two-variable function. These inequalities imply tight upper bounds on the partition function of various statistical models such as the Ising and Potts models, which includes independent sets and graph colorings. For graph colorings, corresponding to H = K[subscript q], we show that the triangle-free hypothesis on G may be dropped; this is also valid if some of the vertices of K[subscript q] are looped. A corollary is that among d-regular graphs, G = K[subscript d,d] maximizes the quantity c[subscript q](G)[superscript 1/|V(G)|] for every q and d, where
c[subscript q](G) counts proper q-colorings of G.Finally, we show that if the edge-weight matrix of H is positive semidefinite, then hom(G,H) ≤ ∏[subscript v∈V(G)] hom(K[subscript dv+1],H)[superscript 1/(dv+1)].This implies that among d-regular graphs, G = K[subscript d+1] maximizes hom(G,H)[superscript 1/|V(G)|]. For 2-spin Ising models, our results give a complete characterization of extremal graphs: complete bipartite graphs maximize the partition function of 2-spin antiferromagnetic models and cliques maximize the partition function of ferromagnetic models. These results settle a number of conjectures by Galvin–Tetali, Galvin, and Cohen–Csikvári–Perkins–Tetali, and provide an alternate proof to a conjecture by Kahn. |
| first_indexed | 2024-09-23T15:52:31Z |
| format | Article |
| id | mit-1721.1/129980 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:52:31Z |
| publishDate | 2021 |
| publisher | Springer Science and Business Media LLC |
| record_format | dspace |
| spelling | mit-1721.1/1299802022-09-29T16:43:47Z A reverse Sidorenko inequality Sah, Ashwin Sawhney, Mehtaab Stoner, David Zhao, Yufei Massachusetts Institute of Technology. Department of Mathematics Abstract Let H be a graph allowing loops as well as vertex and edge weights. We prove that, for every triangle-free graph G without isolated vertices, the weighted number of graph homomorphisms hom(G, H) satisfies the inequality hom(G, H) ≤ ∏[subscript uv∈E(G)] hom(K[subscript du,dv,]H)[superscript 1/(dudv)], where d[subscript u] denotes the degree of vertex u in G. In particular, one has hom(G,H)[superscript 1/|E(G)|] ≤ hom (K[subscript d,d,]H)[superscript 1/d[superscript 2]] for every d-regular triangle-free G. The triangle-free hypothesis on G is best possible. More generally, we prove a graphical Brascamp–Lieb type inequality, where every edge of G is assigned some two-variable function. These inequalities imply tight upper bounds on the partition function of various statistical models such as the Ising and Potts models, which includes independent sets and graph colorings. For graph colorings, corresponding to H = K[subscript q], we show that the triangle-free hypothesis on G may be dropped; this is also valid if some of the vertices of K[subscript q] are looped. A corollary is that among d-regular graphs, G = K[subscript d,d] maximizes the quantity c[subscript q](G)[superscript 1/|V(G)|] for every q and d, where c[subscript q](G) counts proper q-colorings of G.Finally, we show that if the edge-weight matrix of H is positive semidefinite, then hom(G,H) ≤ ∏[subscript v∈V(G)] hom(K[subscript dv+1],H)[superscript 1/(dv+1)].This implies that among d-regular graphs, G = K[subscript d+1] maximizes hom(G,H)[superscript 1/|V(G)|]. For 2-spin Ising models, our results give a complete characterization of extremal graphs: complete bipartite graphs maximize the partition function of 2-spin antiferromagnetic models and cliques maximize the partition function of ferromagnetic models. These results settle a number of conjectures by Galvin–Tetali, Galvin, and Cohen–Csikvári–Perkins–Tetali, and provide an alternate proof to a conjecture by Kahn. 2021-02-23T21:13:23Z 2021-02-23T21:13:23Z 2020-03 2019-03 2020-09-24T20:53:33Z Article http://purl.org/eprint/type/JournalArticle 0020-9910 1432-1297 https://hdl.handle.net/1721.1/129980 Sah, Ashwin et al. "A reverse Sidorenko inequality." Inventiones mathematicae 221, 2 (March 2020): 665–711 2020 Springer-Verlag GmbH Germany, part of Springer Nature en https://doi.org/10.1007/s00222-020-00956-9 Inventiones mathematicae Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag GmbH Germany, part of Springer Nature application/pdf Springer Science and Business Media LLC Springer Berlin Heidelberg |
| spellingShingle | Sah, Ashwin Sawhney, Mehtaab Stoner, David Zhao, Yufei A reverse Sidorenko inequality |
| title | A reverse Sidorenko inequality |
| title_full | A reverse Sidorenko inequality |
| title_fullStr | A reverse Sidorenko inequality |
| title_full_unstemmed | A reverse Sidorenko inequality |
| title_short | A reverse Sidorenko inequality |
| title_sort | reverse sidorenko inequality |
| url | https://hdl.handle.net/1721.1/129980 |
| work_keys_str_mv | AT sahashwin areversesidorenkoinequality AT sawhneymehtaab areversesidorenkoinequality AT stonerdavid areversesidorenkoinequality AT zhaoyufei areversesidorenkoinequality AT sahashwin reversesidorenkoinequality AT sawhneymehtaab reversesidorenkoinequality AT stonerdavid reversesidorenkoinequality AT zhaoyufei reversesidorenkoinequality |