Two Approaches to Sidorenko's Conjecture
Two Approaches to Sidorenko's Conjecture
复制标题
西多伦科猜想的两种方法
DOI：
10.1090/tran/6487
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Joonkyung Lee
中科院分区：
文献类型：
--
作者：
J. Kim;Choongbum Lee;Joonkyung Lee
sidorenko的猜想指出，对于$ \ {1，\ cdots，k \} $，$ \ int \ prod _ {（i，j）\ in E（h）} h（x_i，y_j）d \ mu^{| v（h）|} \ ge \ left（\ int H（x，y）\，d \ mu^2 \ right）^{| e（h）|} $ holds，其中$ \ mu $是$ [0,1] $的Lebesgue测量值，$ h $是$ [0,1]^2 $的有限，非阴性，对称的，可测量的功能。猜想是，来自双分图$ h $到图$ g $的同构数量至少是不对称的，至少是从$ h $到Erdős-renyi随机图的预期同构数量，其预期的边缘密度与$ g $相同在本文中，我们提出了两种协议的方法。 $ A $的顶点具有某种类似树状的结构。 a $使每个顶点$ a \ a $满意$ n（a）\ subseteq n（a_1）$或$ n（a）\ subseteq n（a_2）$，也意味着最近的结果Conlon，Fox和Sudakov \ cite {cofosu}。 $和$ h $也满足了Sidorenko的签约，这意味着，对于所有$ d \ ge 2 $，$ d $二维网格带有任意侧面的长度满足了Sidorenko的缔约方。
Sidorenko's conjecture states that for every bipartite graph $H$ on $\{1,\cdots,k\}$, $\int \prod_{(i,j)\in E(H)} h(x_i, y_j) d\mu^{|V(H)|} \ge \left( \int h(x,y) \,d\mu^2 \right)^{|E(H)|}$ holds, where $\mu$ is the Lebesgue measure on $[0,1]$ and $h$ is a bounded, non-negative, symmetric, measurable function on $[0,1]^2$. An equivalent discrete form of the conjecture is that the number of homomorphisms from a bipartite graph $H$ to a graph $G$ is asymptotically at least the expected number of homomorphisms from $H$ to the Erdős-Renyi random graph with the same expected edge density as $G$. In this paper, we present two approaches to the conjecture. First, we introduce the notion of tree-arrangeability, where a bipartite graph $H$ with bipartition $A \cup B$ is tree-arrangeable if neighborhoods of vertices in $A$ have a certain tree-like structure. We show that Sidorenko's conjecture holds for all tree-arrangeable bipartite graphs. In particular, this implies that Sidorenko's conjecture holds if there are two vertices $a_1, a_2$ in $A$ such that each vertex $a \in A$ satisfies $N(a) \subseteq N(a_1)$ or $N(a) \subseteq N(a_2)$, and also implies a recent result of Conlon, Fox, and Sudakov \cite{CoFoSu}. Second, if $T$ is a tree and $H$ is a bipartite graph satisfying Sidorenko's conjecture, then it is shown that the Cartesian product $T \Box H$ of $T$ and $H$ also satisfies Sidorenko's conjecture. This result implies that, for all $d \ge 2$, the $d$-dimensional grid with arbitrary side lengths satisfies Sidorenko's conjecture.