On the Local Approach to Sidorenko's Conjecture

Jacob Fox, Fan Wei

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

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 languageEnglish (US)
Pages (from-to)459-465
Number of pages7
JournalElectronic Notes in Discrete Mathematics
Volume61
DOIs
StatePublished - Aug 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Forcing Conjecture
  • Graphon
  • Sidorenko's Conjecture

Fingerprint

Dive into the research topics of 'On the Local Approach to Sidorenko's Conjecture'. Together they form a unique fingerprint.

Cite this