کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777108 | 1632570 | 2017 | 7 صفحه PDF | دانلود رایگان |
A well-known conjecture of ErdÅs-Simonovits and Sidorenko states that, if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same number of vertices and edge density. A strengthening known as the forcing conjecture states that, if H is a bipartite graph with at least one cycle, then quasirandom graphs of density p are the only graphs of density p that asymptotically minimize the number of copies of H. Lovász proved a local version of Sidorenko's conjecture. We characterize those graphs for which Sidorenko's conjecture holds locally. Namely, it holds locally for H if and only if H has even girth or is a forest. Furthermore, a local version of the forcing conjecture holds precisely for graphs of even girth. As a corollary, we prove that for such H there is δH>0 such that Sidorenko's conjecture and the forcing conjecture holds for all p>1âδH.
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 459-465