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.
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics
- Forcing Conjecture
- Sidorenko's Conjecture