## Abstract

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}.

Original language | English (US) |
---|---|

Pages (from-to) | 459-465 |

Number of pages | 7 |

Journal | Electronic Notes in Discrete Mathematics |

Volume | 61 |

DOIs | |

State | Published - Aug 2017 |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Applied Mathematics

## Keywords

- Forcing Conjecture
- Graphon
- Sidorenko's Conjecture