A reverse Sidorenko inequality
A reverse Sidorenko inequality
复制标题
逆 Sidorenko 不等式
DOI：
10.1007/s00222-020-00956-9
复制
发表时间：
2020
影响因子：
3.1
通讯作者：
Zhao, Yufei
中科院分区：
文献类型：
--
作者：
Sah, Ashwin;Sawhney, Mehtaab;Stoner, David;Zhao, Yufei
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 homomorphismshom ( G , H ) satisfies the inequality $$\begin{aligned} \hom (G, H ) \le \prod _{uv \in E(G)} \hom (K_{d_u,d_v}, H )^{1/(d_ud_v)}, \end{aligned}$$ hom ( G , H ) ≤ ∏ u v ∈ E ( G ) hom ( K d u , d v , H ) 1 / ( d u d v ) , whered u denotes the degree of vertex u in G. In particular, one has $$\begin{aligned} \hom (G, H )^{1/|E(G)|} \le \hom (K_{d,d}, H )^{1/d^2} \end{aligned}$$ hom ( G , H ) 1 / | E ( G ) | ≤ hom ( K d , d , H ) 1 / d 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 toH = K q , we show that the triangle-free hypothesis on G may be dropped; this is also valid if some of the vertices ofK q are looped. A corollary is that among d-regular graphs,G = K d , d maximizes the quantityc q ( G ) 1 / | V ( G ) | for every q and d, wherec q ( G ) counts proper q-colorings of G.Finally, we show that if the edge-weight matrix of H is positive semidefinite, then $$\begin{aligned} \hom (G, H) \le \prod _{v \in V(G)} \hom (K_{d_v+1}, H )^{1/(d_v+1)}. \end{aligned}$$ hom ( G , H ) ≤ ∏ v ∈ V ( G ) hom ( K d v + 1 , H ) 1 / ( d v + 1 ) . This implies that among d-regular graphs,G = K d + 1 maximizeshom ( G , H ) 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.
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 homomorphismshom ( G , H ) satisfies the inequality $$\begin{aligned} \hom (G, H ) \le \prod _{uv \in E(G)} \hom (K_{d_u,d_v}, H )^{1/(d_ud_v)}, \end{aligned}$$ hom ( G , H ) ≤ ∏ u v ∈ E ( G ) hom ( K d u , d v , H ) 1 / ( d u d v ) , whered u denotes the degree of vertex u in G. In particular, one has $$\begin{aligned} \hom (G, H )^{1/|E(G)|} \le \hom (K_{d,d}, H )^{1/d^2} \end{aligned}$$ hom ( G , H ) 1 / | E ( G ) | ≤ hom ( K d , d , H ) 1 / d 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 toH = K q , we show that the triangle-free hypothesis on G may be dropped; this is also valid if some of the vertices ofK q are looped. A corollary is that among d-regular graphs,G = K d , d maximizes the quantityc q ( G ) 1 / | V ( G ) | for every q and d, wherec q ( G ) counts proper q-colorings of G.Finally, we show that if the edge-weight matrix of H is positive semidefinite, then $$\begin{aligned} \hom (G, H) \le \prod _{v \in V(G)} \hom (K_{d_v+1}, H )^{1/(d_v+1)}. \end{aligned}$$ hom ( G , H ) ≤ ∏ v ∈ V ( G ) hom ( K d v + 1 , H ) 1 / ( d v + 1 ) . This implies that among d-regular graphs,G = K d + 1 maximizeshom ( G , H ) 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.
登录
查看更多内容
DOI：
10.1017/fms.2018.25
发表时间：
2019
期刊：
Forum of Mathematics, Sigma
影响因子：
--
作者：
JENSSEN M
通讯作者：
JENSSEN M
关于正则图中的 Widom-Rowlinson 占有率
DOI：
--
发表时间：
2015
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
E. Cohen;Will Perkins;P. Tetali
通讯作者：
P. Tetali
影响因子：
1.7
作者：
Conlon, David;Lee, Joonkyung
通讯作者：
Lee, Joonkyung
DOI：
--
发表时间：
2013
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Jonathan Cutler;A. J. Radcliffe
通讯作者：
A. J. Radcliffe
西多伦科猜想的两种方法
DOI：
10.1090/tran/6487
发表时间：
2013
期刊：
arXiv: Combinatorics
影响因子：
--
作者：
J. Kim;Choongbum Lee;Joonkyung Lee
通讯作者：
Joonkyung Lee