A reverse Sidorenko inequality

• 成果类型: Article
• 署名作者: Sah, Ashwin; Sawhney, Mehtaab; Stoner, David; Zhao, Yufei
• 署名单位: Massachusetts Institute of Technology (MIT); Stanford University; Massachusetts Institute of Technology (MIT)
• 刊物名称: INVENTIONES MATHEMATICAE
• ISSN/ISSBN: 0020-9910
• DOI: 10.1007/s00222-020-00956-9
• 发表日期: 2020
• 页码: 665-711
• 关键词: hard-core model; independent sets; regular graphs; number

摘要

LetHbe a graph allowing loops as well as vertex and edge weights. We prove that, for every triangle-free graphGwithout isolated vertices, the weighted number of graph homomorphismshom(G,H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hom (G, H)$$\end{document}satisfies the inequalityhom(G,H)<=& x220f;uv is an element of E(G)hom(Kdu,dv,H)1/(dudv),\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \hom (G, H ) \le \prod _{uv \in E(G)} \hom (K_{d_u,d_v}, H )<^>{1/(d_ud_v)}, \end{aligned}$$\end{document}wheredu\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d_u$$\end{document}denotes the degree of vertexuinG. In particular, one hashom(G,H)1/|E(G)|<= hom(Kd,d,H)1/d2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \hom (G, H )<^>{1/|E(G)|} \le \hom (K_{d,d}, H )<^>{1/d<^>2} \end{aligned}$$\end{document}for everyd-regular triangle-freeG. The triangle-free hypothesis onGis best possible. More generally, we prove a graphical Brascamp-Lieb type inequality, where every edge ofGis 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 toH=Kq\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H = K_q$$\end{document}, we show that the triangle-free hypothesis onGmay be dropped; this is also valid if some of the vertices ofKq\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_q$$\end{document}are looped. A corollary is that amongd-regular graphs,G=Kd,d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = K_{d,d}$$\end{document}maximizes the quantitycq(G)1/|V(G)|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_q(G)<^>{1/|V(G)|}$$\end{document}for everyqandd, wherecq(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_q(G)$$\end{document}counts properq-colorings ofG.Finally, we show that if the edge-weight matrix ofHis positive semidefinite, thenhom(G,H)<=& x220f;v is an element of V(G)hom(Kdv+1,H)1/(dv+1).\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \hom (G, H) \le \prod _{v \in V(G)} \hom (K_{d_v+1}, H )<^>{1/(d_v+1)}. \end{aligned}$$\end{document}This implies that amongd-regular graphs,G=Kd+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = K_{d+1}$$\end{document}maximizeshom(G,H)1/|V(G)|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hom (G, H)<^>{1/|V(G)|}$$\end{document}. 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-Csikvari-Perkins-Tetali, and provide an alternate proof to a conjecture by Kahn.