Sidorenko's Conjecture for Blow-ups
Sidorenko's Conjecture for Blow-ups
复制标题
DOI：
10.19086/da.21472
复制
发表时间：
2021-03-30
影响因子：
1.1
通讯作者：
Lee, Joonkyung
中科院分区：
文献类型：
--
作者：
Conlon, David;Lee, Joonkyung
Sidorenko和Erdos-Simonovits的一个著名猜想指出，对于所有二部图H，准随机图包含了所有具有相同阶数和边密度的图上H的渐近最小拷贝数。这个猜想在过去十年中引起了相当大的兴趣，现在已知它适用于广泛的二部图，总的趋势是，如果一个图可以用简单的构建块（如树）以某种递归的方式构建，那么它就满足这个猜想。我们在这里的贡献，超越了这个范例，是为了证明这个猜想适用于任何双分A布尔或B的二部图H，其中B中k次的顶点个数满足每个k的一定可除性条件。作为推论，我们有对于每一个双分A布尔或B的二部图H，存在一个正整数p，使得膨胀的H- a (p)由取p个顶点不相交的H副本，并将a的所有副本沿相应的顶点粘合而成，满足这个猜想。另一种看待后一个结果的方式是，对于每一个二部H，存在一个正整数p，使得Sidorenko猜想的l -p版本对H成立。
A celebrated conjecture of Sidorenko and Erdos-Simonovits states that, for all bipartite graphs H, quasirandom graphs contain asymptotically the minimum number of copies of H taken over all graphs with the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs, with the overall trend saying that a graph satisfies the conjecture if it can be built from simple building blocks such as trees in a certain recursive fashion.Our contribution here, which goes beyond this paradigm, is to show that the conjecture holds for any bipartite graph H with bipartition A boolean OR B where the number of vertices in B of degree k satisfies a certain divisibility condition for each k. As a corollary, we have that for every bipartite graph H with bipartition A boolean OR B, there is a positive integer p such that the blow-up H-A(p) formed by taking p vertex-disjoint copies of H and gluing all copies of A along corresponding vertices satisfies the conjecture. Another way of viewing this latter result is that for every bipartite H there is a positive integer p such that an L-p-version of Sidorenko's conjecture holds for H.